Salut !! Nu stiti un site,articol etc. unde este explicat Minimum Dominating Set,eventual si un algoritm implementat?Am gasit pe Wikipedia,dar doar pentru grafuri neorientate.

P.S.:Imi trebuie pt. olimpiada.(s-a dat la locala anul trecut)

Multumesc.

Ok,scuze.Pai algoritmul de cel mai lung subsir e cel clasic.La reconstituire eu pornesc de la lungimea maxima k pana la 1 si caut poz i,j pe care X[ i ] ==Y [ j ] si SC[ i] [ j ] == k si daca X[ i ] e mai mare decat max-ul gasit pana atunci inlocuiesc maximul si retin pozitiile i,j in pmx2 respectiv pmy2.Cand caut un alt element maxim incep de la pozitia maxima gasita anterior pmx,pmy pt. a nu lua o valore maxima din alt subsir in cel curent. Aici e problema ca imi pune pune alte valori maxime din alte subsiruri cu conditia curenta, si nu-mi dau seama unde gresesc si cum as putea pune conditia astfel incat sa le ia corect.

Apropo problema e aceasta : http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=948
Multumesc.

Salut! Am doua siruri cu cifre X,Y de lungime n respectiv m si vreau sa aflu cel mai lung subsir comun de valoare maxima.Am facut cel mai lung subsir comun cu algoritmul clasic ,dar nu stiu cum pot reconstitui cel mai lung subsir cu valoare maxima. .Am incercat urmatoarea varianta dar nu merge in toate cazurile.Cum as putea face sa mearga ??

Cod:

    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++)
            if(X[i]==Y[j])
                SC[i][j]=1+SC[i-1][j-1];//cel mai lung
            else
                SC[i][j]=max(SC[i][j-1],SC[i-1][j]);//subsir comun
    }
pmx=n;pmy=m;
    for(k=SC[n][m];k>=1;k--){//caut pozitia de lungime k cu cea mai mare cifra
        mx=-1;
        for(i=pmx;i>=1;i--)
            for(j=pmy;j>=1;j--)
                if(SC[i][j]==k && X[i]==Y[j] && X[i]>mx){
                    mx=X[i];pmx2=i;pmy2=j;
                }
       sol[++sol[0]]=mx;//retin maximul
       pmx=pmx2;pmy=pmy2;
    }
    for(i=sol[0];i>=1;i--)
        printf("%d",sol[i]);
    printf("\n");

Salut !! Am incercat sa rezolv urmatoarea problema : http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=683
Am rezolvat problema prin programare dinamica ,dar nu stiu de ce iau 90.Am retinut toate cifrele care apar in numerele citite in ordine in sirul v dupa care am facut dinamica pentru a afla suma maxima pt. un prefix de lungime 1,2,3 ... , L.Am retinut doar 4 linii in matrice.Problema e ca iau WA pe ultimul test si nu vad ce caz as fi putut uita.

Ma poate ajuta cineva ?
Multumesc.

Sursa mea:

Cod:

#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 2000
long S[4][maxn],nou;
int v[maxn],n,L;
char snr[16],sir[maxn];
int main(){
    int i,j;
    freopen("suma2.in","r",stdin);
    scanf("%d",&n);
    for(i=1;i<=n;++i){
        scanf("%s",&snr);
        strcat(sir,snr);
    }
    L=strlen(sir);
    for(i=1;i<=L;++i)
        v[i]=sir[i-1]-'0';
    fclose(stdin);
    for(i=0;i<4;++i)
        for(j=0;j<=n;++j)
            S[i][j]=-1;
    S[0][0]=0;S[1][1]=v[1];S[2][1]=v[1]*10+v[2];
    if(v[2])S[2][2]=v[1]+v[2];
    S[3][1]=v[1]*100+v[2]*10+v[3];
    if(v[2])S[3][2]=v[1]+v[2]*10+v[3];
    if(v[3] && S[3][2]<v[1]*10+v[2]+v[3]) S[3][2]=v[1]*10+v[2]+v[3];
    if(v[2] && v[3])S[3][3]=v[1]+v[2]+v[3];
    for(i=4;i<=L;i++){
        S[i%4][0]=-1;S[i%4][1]=-1;
        for(j=2;j<=i;j++){
            if(v[i]==0)S[i%4][j]=-1;
            else{
                if(S[(i-1+4)%4][j-1]!=-1){
                    nou=S[(i-1+4)%4][j-1]+v[i];
                    S[i%4][j]=nou;
                }
            }
            if(v[i-1]>0)
                if(S[(i-2+4)%4][j-1]!=-1){
                    nou=S[(i-2+4)%4][j-1]+v[i-1]*10+v[i];
                    if(nou>S[i%4][j])
                        S[i%4][j]=nou;
                }
            if(v[i-2]>0)
                if(S[(i-3+4)%4][j-1]!=-1){
                    nou=S[(i-3+4)%4][j-1]+v[i-2]*100+v[i-1]*10+v[i];
                    if(nou>S[i%4][j])
                        S[i%4][j]=nou;
                }
        }
    }
    freopen("suma2.out","w",stdout);
    printf("%ld\n",S[L%4][n]);
    fclose(stdout);
    return 0;
}

Iau 0p si imi scrie Eroare in configurarea problemei.Si la raport evaluator imi scrie urmatorea:
Raport evaluator

Contactează autorul problemei:
Evaluatorul nu a returnat un număr la stdout pe testul 1 (se ignoră spaţii, newline, etc) 

Ce inseamna asta?Ma poate ajuta cineva?
Multumesc.

Aici e sursa mea:

Cod:

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
struct nod{
    int index,lowlink;
}v[256];
vector <int> g[256],ctc[256];
bool viz[256],inS[256],gi[256],go[256],viz2[256];
int n,ind,nr,ni,no;
int nrc[256],S[256],X[256],Y[256];
queue < int > Q;
void strongconnect(int x){
    int i,vf;
    ind++;viz[x]=1;
    v[x].index=ind;
    v[x].lowlink=ind;
    S[++S[0]]=x;inS[x]=1;
    for(i=0;i<(int)g[x].size();i++){
        vf=g[x][i];
        if(!viz[vf]){
            strongconnect(vf);
            v[x].lowlink=min(v[x].lowlink,v[vf].lowlink);
        }
        else if(inS[vf])
            v[x].lowlink=min(v[x].lowlink,v[vf].lowlink);
    }
    if(v[x].index==v[x].lowlink){
        nr++;
        while(S[S[0]]!=x){
            nrc[S[S[0]]]=nr;
            inS[S[S[0]]]=0;
            --S[0];
        }
        nrc[x]=nr;
        inS[x]=0;
        --S[0];
        }
}
void Tarjan(){
    for(int i=1;i<=n;i++)
        if(!viz[i])
            strongconnect(i);
}
void gctc(){
    for(int i=1;i<=n;i++)
        for(int j=0;j<(int)g[i].size();j++){
            if(nrc[i]!=nrc[g[i][j]]){
                ctc[nrc[i]].push_back(nrc[g[i][j]]);
                gi[nrc[g[i][j]]]=1;
                go[nrc[i]]=1;
            }
        }
}
void BFS(int x){
    int curr,i;
    for(i=1;i<=nr;i++)
        viz[i]=0;
    while(!Q.empty())
        Q.pop();
    Q.push(x);
    viz[x]=1;
    while(!Q.empty()){
        curr=Q.front();
        for(i=0;i<(int)ctc[curr].size();i++){
            if(!viz[ctc[curr][i]]){
                Q.push(ctc[curr][i]);
                viz[ctc[curr][i]]=1;
                if(!viz2[ctc[curr][i]] && !go[ctc[curr][i]]){
                    Y[++Y[0]]=ctc[curr][i];
                    X[Y[0]]=x;viz[ctc[curr][i]]=1;
                    return ;
                }
            }
        }
        Q.pop();
    }
}
void add(int y,int x){
    int i;
    for(i=1;i<=n;i++)
        if(nrc[i]==y){
            printf("\n%d ",i);
            break;}
    for(i=1;i<=n;i++)
        if(nrc[i]==x){
            printf("%d",i);
            break;}
}
int main(){
    int i,m,x,y,j;
    freopen("plan.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
    }
    fclose(stdin);
    Tarjan();
    freopen("plan.out","w",stdout);
    if(nr==1)
        printf("0\n");
    else {
        gctc();
        for(i=1;i<=nr;i++){
            if(!gi[i]){
                ni++;
                BFS(i);
            }
            if(!go[i])
                no++;
        }
        printf("%d",max(ni,no));
        for(i=1;i<=min(ni,no);i++){
            if(i==min(ni,no)){
                add(Y[i],X[1]);
                go[Y[i]]=1;
                gi[X[1]]=1;}
            else{
                add(Y[i],X[i+1]);
                go[Y[i]]=1;
                gi[X[i+1]]=1;
            }
        }
        if(ni<no){
            for(i=1;i<=nr;i++)
                if(!gi[i])
                    add(X[1],gi[i]);
        }
        else if(no>ni){
            for(i=1;i<=nr;i++)
                if(!go[i])
                    add(go[i],X[1]);
        }
    fclose(stdout);
    }
    return 0;
}

Saut ! Nu am inteles la solutia oficiala partea cu construirea grafului componentelor tare conexe.Cand construiesc graful raman doar muchiile din componentele tare conexe ? Adica pentru exemplul din problema sunt 2 componente tare conexe: prima:nodurile 1 si 2 cu muchiile 1->2,2->1 si a doua nodul 3.Atunci nodul 3 ar trebui sa apartina si lui X si lui Y.

Sau ar trebui sa ramana muchia 2->3 ?Si atunci as avea 3 apartine lui Y si X e vida.Deci nu am cum sa duc muchie la x1 sau sa fac parcurgerea pentru construirea perechilor  (x1, y1), (x2, y2) ... (xk, yk).

Imi poate explica cineva , va rog ?
Mutumesc.

Salut!!Am downlodat noul pachet cel cu CodeBlocks,Mingw si STL documentation (de aici:http://infoarena.ro/schimbare-borland/pachet) si le-am instalat pe toate 3.Problema e ca nu pot deschide mingw-ul,nu-mi apare iconita de la mingw nici pe desktop nici in dosarul mingw,doar cea de la CodeBlocks .Se poate cumva deschide si mingw-ul sau doar CodeBlocks-ul?
O explicatie va rog.

Salut!Cum pot afisa un numar folosind cout cu exact 2 zecimale chiar daca ele sunt 00 ?
De exemplu:

Cod:

double a=95.00,b=126.50,c=146.00
cout<<a<<'\n'<<b<<'\n'<<c;
OUT:
95.00
126.50
146.00

Am incercat cu setprecision dar nu merge nu imi afiseaza zero-urile.

Poti incerca si cu Roy-Floyd,ai algoritmul descris aici:https://infoarena.ro/problema/royfloyd
Doar trebuie modificat putin pt. ca el gaseste costu minim,iar tie iti trebuie costul maxim.
Ca alternative poti incerca si:
1)Algoritmul lui Dijkstra:https://infoarena.ro/problema/dijkstra
2)Algoritmul Bellman-Ford:https://infoarena.ro/problema/bellmanford
Succes!

Imi poate explica si mie cineva ce face si la ce se foloseste urmatoarea declarare:

Cod:

struct nod{
nod *p;
}

Eu stiam ca in interiorul structuri se pot declara doar campuri de tipul int,float,string etc.Dar am observat in unele surse aceasta declarare.Numai pointeri se pot declara in acest fel sau as putea sa zic si :

Cod:

struct nod{
nod p;
}

As dori o explicatie cum functioneaza,daca se poate.
Multumesc.

Cum as putea sa optimizez urmatoarea varianta de rezolvare(iau 60p).Functioneaza corect da pica la timp.Am considerat pe rand ultimele n-i secvente si am facut maximul din pe cele 3 cazuri daca max e in secv 1 ,2 sau 3.Imi puteti da o idee de optimizare a cautarii?
Codul:

Cod:

#include<cstdio>
using namespace std;
int n,v[30001];
int caut(int x,int y){
	int max=-10001,i;
	for(i=x;i<=y;i++)
		if(v[i]>max)
			max=v[i];
	return max;
}
int main(){
	int max=-10001,p,i,smin=0x3f3f3f3f,p1,p2,aux;
	freopen("secv.in","r",stdin);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&v[i]),v[i]>max ? max=v[i],p=i:0;
	fclose(stdin);
	for(i=1;i<=n-2;i++){
		if(p>=n-i+1){
			aux=max+v[n-i]+caut(1,n-i-1);
			if(aux<smin)
				smin=aux,p2=n-i,p1=n-i-1;
		}
		else if(p==n-i){
			aux=max+v[1]+v[n];
			if(aux<smin)
				smin=aux,p1=1,p2=n-1;
		}
		else if(p<n-i){
			aux=max+v[n-i]+caut(n-i+1,n);
			if(aux<smin)
				smin=aux,p2=n-i,p1=n-i-1;
		}
	}
	freopen("secv.out","w",stdout);
	printf("%d\n%d %d",smin,p1,p2);
	fclose(stdout);
	return 0;
}

Salut!Imi poate explica si mie cineva ce face operatul " -> " in C++.Am observat ca se foloseste la liste,dar nu prea am inteles ce face.
Daca se poate sa-mi explicati rolul lui si utilizarea lui in liste,sau sa-mi dati un articol despre liste in care se explica acest lucru.
Multumesc.

P.S.:Am mai implementat liste dar folosind STL(ex:vector<int> list[100] )si cred ca ar fi de folos sa le stiu implementa si cu pointeri.

Multumesc foarte mult Tiplea Tudor!!!Am facut cum ai spus tu si am pus 5*10^11 la inf si a mers.
Totusi mi se pare ciudat ca merge deoarece mie pe Mingw nu-mi compileaza cu 5*10^11,pentru ca spune ca imi da error: integer constant is too large for "long" type,dar totusi pe site merge.
Multumesc inca o data nu mi-as fi dat seama niciodata.

Ok nu stiam ca testele nu se fac publice.
Am mai incercat sa gasesc greseala si cred ca este la reconstituirea drumului.Eu am atribuit -1 pozitiei nodul din care pornesc si la restul pozitiilor varful  din care s-a ajuns in nodul curent i.Exemplu pentru reconstituirea drumului din A am facut urmatoarea:

Cod:

j=ind;i=0;//ind e varful un suma distantelor e minima
	while(j!=pa[A]){//pa retine varful din care s-a ajuns in nodul i
		sol[++i]=j;
		j=pa[j];
	}
	printf("\n%d",i);
	for(k=1;k<=i;k++)
		printf(" %d",sol[k]);

Daca in while in loc de j!=pa[A] care este -1 puneam j>0 nu mai luam  Killed by signal 11(SIGSEGV),dar luam ca drum trebuie sa se termine cu A,B sau C.Nu imi dau seama ce operatie  face reconstituirea incat sa ia  Killed by signal 11(SIGSEGV) pt. ca la memorie e ok.
Aici e sursa completa:

Cod:

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define pp pair<int,int>
#define ff first
#define ss second
#define inf 100000000
#define nmax 100005
vector <pp> v[nmax];
int da[nmax],db[nmax],dc[nmax],n;
int pa[nmax],pb[nmax],pc[nmax];
int H[nmax],poz[nmax],sol[nmax];
inline int left_son(int k){
    return 2*k;
}
inline int right_son(int k){
    return 2*k+1;
}
inline int father(int k){
    return k/2;
}
void percolate(int k,int d[]){
    while(k>1 && d[H[k]]<d[H[father(k)]]){
        swap(poz[H[k]],poz[H[father(k)]]);
        swap(H[k],H[father(k)]);
        k=father(k);
    }
}
void sift(int k,int d[],int hp){
    int son;
    do{
        son=0;
        if(left_son(k)<=hp)
            son=left_son(k);
        if(right_son(k)<=hp && d[H[right_son(k)]]<d[H[son]])
            son=right_son(k);
        if(d[H[son]]>d[H[k]])
            son=0;
        if(son){
            swap(poz[H[k]],poz[H[son]]);
            swap(H[k],H[son]);
            k=son;
        }
    }while(son);
}
int minimum(int& hp,int d[] ){
    int key;
    key=H[1];
    swap(poz[H[1]],poz[H[hp]]);
    H[1]=H[hp--];
    sift(1,d,hp);
    return key;
}
void build_heap(int k,int hp){
    int i;
    for(i=1;i<=hp;i++)
        H[i]=poz[i]=i;
    if(poz[k]!=1){
        swap(poz[H[1]],poz[H[k]]);
        swap(H[1],H[k]);
    }
}
void Dijkstra(int nod,int d[],int p[]){
    pp aux;
    int vfmin,dmin,hp,i;
    unsigned j;
    hp=n;
    for(i=1;i<=n;i++)
        d[i]=inf;
    d[nod]=0;
    build_heap(nod,hp);
    p[nod]=-1;
    for(i=1;i<=n;i++){
        vfmin=minimum(hp,d);
        dmin=d[vfmin];
        for(j=0;j<v[vfmin].size();j++){
            aux=v[vfmin][j];
            if(dmin+aux.ss<d[aux.ff]){
                d[aux.ff]=dmin+aux.ss;
				p[aux.ff]=vfmin;
                percolate(poz[aux.ff],d);
            }
        }
    }
}
int main(){
    int m,A,B,C,i,p,q,t,trmin,sum,ind=0,j,k;
    freopen("trilant.in","r",stdin);
    scanf("%d%d",&n,&m);
    scanf("%d%d%d",&A,&B,&C);
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&p,&q,&t);
        v[p].push_back(make_pair(q,t));
        v[q].push_back(make_pair(p,t));
    }
    fclose(stdin);
    Dijkstra(A,da,pa);
    Dijkstra(B,db,pb);
    Dijkstra(C,dc,pc);
	trmin=da[1]+db[1]+dc[1];ind=1;
    for(i=2;i<=n;i++){
        sum=da[i]+db[i]+dc[i];
        if(sum<trmin){
            trmin=sum;
			ind=i;
		}
    }
    freopen("trilant.out","w",stdout);
    printf("%d",trmin);
	j=ind;i=0;
	while(j!=pa[A]){
		sol[++i]=j;
		j=pa[j];
	}
	printf("\n%d",i);
	for(k=1;k<=i;k++)
		printf(" %d",sol[k]);
	j=ind;i=0;
	while(j!=pb[B]){
		sol[++i]=j;
		j=pb[j];
	}
	printf("\n%d",i);
	for(k=1;k<=i;k++)
		printf(" %d",sol[k]);
	j=ind;i=0;
	while(j!=pc[C]){
		sol[++i]=j;
		j=pc[j];
	}
	printf("\n%d",i);
	for(k=1;k<=i;k++)
		printf(" %d",sol[k]);
    fclose(stdout);
    return 0;
}

Se poate sa-mi trimiteti unul din testele 18,19,20 fisierul in si out ?Orice modificare am facut tot Killed by signal 11(SIGSEGV) iau .(desi evaluatoru imi arata ca folosesc mai putina memorie ca la alte teste si nu vad nici o greseala)

Iau 0p dar nu inteleg ce gresesc.Am facut un Dijkstra din fiecare nod A,B,C si am retinut distantele  minime in 3 vector da,db,dc si varful de pe unde s-a trecut pt. a ajunge in varful curent l-am retinut in pa,pb,pc.Am parcurs nodurile si am retinut cea mai mica suma da+db+dc(solutia) si nodul in care este suma minima pt. reconstituire.Pe exemplu merge bine,dar pe testele celelate primesc cost prea mare,drumurile au noduri comune,muchii invalide sau    Killed by signal 11.

Multumesc.

Sursa mea:

Cod:

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define pp pair<int,int>
#define ff first
#define ss second
#define inf 4000000*10
#define nmax 100005
vector <pp> v[nmax];
int da[nmax],db[nmax],dc[nmax],n;
int pa[nmax],pb[nmax],pc[nmax];
int H[nmax],poz[nmax],sol[nmax];
inline int left_son(int k){
    return 2*k;
}
inline int right_son(int k){
    return 2*k+1;
}
inline int father(int k){
    return k/2;
}
void percolate(int k,int d[]){
    while(k>1 && d[H[k]]<d[H[father(k)]]){
        swap(poz[H[k]],poz[H[father(k)]]);
        swap(H[k],H[father(k)]);
        k=father(k);
    }
}
void sift(int k,int d[],int hp){
    int son;
    do{
        son=0;
        if(left_son(k)<=hp)
            son=left_son(k);
        if(right_son(k)<=hp && d[H[right_son(k)]]<d[H[son]])
            son=right_son(k);
        if(d[H[son]]>d[H[k]])
            son=0;
        if(son){
            swap(poz[H[k]],poz[H[son]]);
            swap(H[k],H[son]);
            k=son;
        }
    }while(son);
}
int minimum(int& hp,int d[] ){
    int key;
    key=H[1];
    swap(poz[H[1]],poz[H[hp]]);
    H[1]=H[hp--];
    sift(1,d,hp);
    return key;
}
void build_heap(int k,int hp){
    int i;
    for(i=1;i<=hp;i++)
        H[i]=poz[i]=i;
    if(poz[k]!=1){
        swap(poz[H[1]],poz[H[k]]);
        swap(H[1],H[k]);
    }
}
void Dijkstra(int nod,int d[],int p[]){
    pp aux;
    int vfmin,dmin,hp,i;
    unsigned j;
    hp=n;
    for(i=1;i<=n;i++)
        d[i]=inf;
    d[nod]=0;
    build_heap(nod,hp);
    p[nod]=-1;
    for(i=1;i<=n;i++){
        vfmin=minimum(hp,d);
        dmin=d[vfmin];
        for(j=0;j<v[vfmin].size();j++){
            aux=v[vfmin][j];
            if(dmin+aux.ss<d[aux.ff]){
                d[aux.ff]=dmin+aux.ss;
                percolate(poz[aux.ff],d);
                p[aux.ff]=vfmin;
            }
        }
    }
}
int main(){
    int m,A,B,C,i,p,q,t,trmin=inf,sum,ind,j;
    freopen("trilant.in","r",stdin);
    scanf("%d%d",&n,&m);
    scanf("%d%d%d",&A,&B,&C);
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&p,&q,&t);
        v[p].push_back(make_pair(q,t));
        v[q].push_back(make_pair(p,t));
    }
    fclose(stdin);
    Dijkstra(A,da,pa);
    Dijkstra(B,db,pb);
    Dijkstra(C,dc,pc);
    for(i=1;i<=n;i++){
        sum=da[i]+db[i]+dc[i];
        if(sum<trmin)
            trmin=sum,ind=i;
    }
	j=ind;i=0;
	do{
		sol[++i]=j;
		j=pa[j];
	}while(j!=-1);
    freopen("trilant.out","w",stdout);
    printf("%d",trmin);
	printf("\n%d ",i);
	for(int k=1;k<=i;k++)
		printf("%d ",sol[k]);
	j=ind;i=0;
	do{
		sol[++i]=j;
		j=pb[j];
	}while(j!=-1);
	printf("\n%d ",i);
	for(int k=1;k<=i;k++)
		printf("%d ",sol[k]);
	j=ind;i=0;
	do{
		sol[++i]=j;
		j=pc[j];
	}while(j!=-1);
	printf("\n%d ",i);
	for(int k=1;k<=i;k++)
		printf("%d ",sol[k]);
    fclose(stdout);
    return 0;
}

Pai gandestete un pic tu faci urmatoarea chestie.Daca a<c rezulta x:=c dar pentru exemplu a>c(5>4) si atunci lui x nu i se atribuie nici o valoare pana cand il citesti pe 2.Si astfel tie iti ramane multimea de la 2 la 9 in loc sa fie de la  5 la 9.Ai putea face un else la primele if-uri sau sa citesti doar valorile a si b la inceput dupa care x:=a , y:=b si faci for-ul la fel doar ca pana la n-1. (sper ca am fost de ajutor)

Salut!Am urmatoarea problema:http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=1398
Problema e relativ simpla,dar sursa mea ia doar 20p.Dupa ce am verificat primul test la care da un raspuns incorect am observat ca greseala e la timpul in care incepe frame-ul si cel in care se termina la una din sectiuni.Acesta e mai mic cu 1 fata de raspunsul pe care il dau iei.
Pentru urmatoarea sectiune:

Cod:

73
00:10:30,680 --> 00:10:31,680
Doctor, forgive me.

Mie imi da:

Cod:

{15767}{15792}Doctor, forgive me.

Iar lor le da:

Cod:

{15766}{15791}Doctor, forgive me.

Nu inteleg de ce lor le da asa pt ca: (10*60+30+0.680)*25=630.68*25=15767 exact rezultatul meu(puteti verifica).
Apropo nu am vazut pe nimeni inafara de autoare sa ia 100p in cpp doar in pascal s-au mai luat 100p.

Credeti ca sunt testele gresite sau care e problema?
Aici e sursa mea:

Cod:

#include<cstdio>
using namespace std;
int n,nr;
int t1,t2;
int sum;
char s[256];
int main(){
    char a,b,c,d,e;
    freopen("subtitrare.in","r",stdin);
	freopen("subtitrare.out","w",stdout);
    while(!feof(stdin)){
        t1=t2=sum=0;
        scanf("%d\n",&n);
        scanf("%c%c%c",&a,&b,&c);
        t1+=3600*((a-'0')*10+(b-'0'));
        scanf("%c%c%c",&a,&b,&c);
        t1+=60*((a-'0')*10+(b-'0'));
        scanf("%c%c%c",&a,&b,&c);
        t1+=(a-'0')*10+(b-'0');
		scanf("%c%c%c",&a,&b,&c);
		sum=(a-'0')*100+(b-'0')*10+(c-'0');
		sum*=25;sum/=1000;
		t1*=25;t1+=sum;sum=0;
		scanf("%c%c%c%c%c",&a,&b,&c,&d,&e);
		scanf("%c%c%c",&a,&b,&c);
        t2+=3600*((a-'0')*10+(b-'0'));
        scanf("%c%c%c",&a,&b,&c);
        t2+=60*((a-'0')*10+(b-'0'));
        scanf("%c%c%c",&a,&b,&c);
        t2+=(a-'0')*10+(b-'0');
		scanf("%c%c%c\n",&a,&b,&c);
		sum=(a-'0')*100+(b-'0')*10+(c-'0');
		sum*=25;sum/=1000;
		t2*=25;t2+=sum;
		printf("{%d}{%d}",t1,t2);
		nr=0;
		while(!feof(stdin)){
			scanf("%c",&c);
			if(c>='0' && c<='9'){
				ungetc(c,stdin);
				break;}
			else if(c!=' '){
				nr++;
				ungetc(c,stdin);
				gets(s);
				scanf("\n");
				if(nr>=2)
					printf("|");
				printf("%s",s);
			}
			else if(c==' ')
				continue;
		}
		printf("\n");
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}

Multumesc

Salut !Am urmatoarea problemahttp://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=1196.
Am incercat o rezolvare cu backtracking in care cabanele sun nodurile unui graf si am retinut vecinii in liste.Dupa asta am luat fiecare varf l-am pus pe prima poz in sirul de solutii sol si fiecare vecin al nodului de pe sol[1] l-am pus pe pozitia M astfel incat sa existe poteca de intoarcere.Dupa care fac un backtracking recursiv in care determin drumurile posibile care au si un izvor(pt a vedea daca e izvor sau nu am folosit sirul ok).Sursa mea merge bine problema e ca pica la timp un test si ia doar 90p.
Imi puteti da ceva idei de optimizare pt. a lua 100p.
Am incercat 2 implementari una cu liste de adiacenta una cu matrice de adiacenta amandoua iau 90p ,dar mi se pare ca cea cu matrice merge mai repede(trece doar cu putin 1.2s la testul cel mai mare).
Aici e sursa cu liste:

Cod:

#include<cstdio>
#include<vector>
#include<iostream>
using namespace std;
#define ff first
#define ss second
vector < pair<int,int> > v[101];
int sol[30];
bool viz[22],ok[22];
int N,M,P,nr;
int find(int x,int y){
	unsigned i;
	for(i=0;i<v[x].size();i++){
		if(y==v[x][i].ff){
			if(v[x][i].ss==1)
				ok[M]=1;
			return 1;
		}
	}
	return 0;
}
void back(int k){
	unsigned i;
	int izvor;
	izvor=0;
    if(k==M){
		/*for(i=1;i<=k;i++)
			cout<<sol[i]<<" ";
		cout<<'\n';
		for(i=1;i<=k;i++)
			cout<<ok[i]<<" ";
		cout<<'\n';*/
		if(find(sol[k-1],sol[k])){
		for(i=1;i<=k;i++){
			if(ok[i]==1){
				izvor=1;
				break;
			}
		}
		ok[M]=0;
		if(izvor)
			nr++;
	}
	}
    else{
        for(i=0;i<v[sol[k-1]].size();i++){
            if(!viz[v[sol[k-1]][i].ff]){
				sol[k]=v[sol[k-1]][i].ff;
				viz[v[sol[k-1]][i].ff]=1;
				if(v[sol[k-1]][i].ss==1)
					ok[k]=1;
				back(k+1);
				ok[k]=0;
				viz[v[sol[k-1]][i].ff]=0;
			}
		}
	}
}
int main(){
    int i,x,y,z;
	unsigned j;
    freopen("izvor.in","r",stdin);
    scanf("%d%d%d",&N,&P,&M);
    for(i=1;i<=P;i++){
        scanf("%d%d%d",&x,&y,&z);
        v[x].push_back(make_pair(y,z));
        v[y].push_back(make_pair(x,z));
    }
    fclose(stdin);
    for(i=1;i<=N;i++){
        if(v[i].size()>=2){
            sol[1]=i;
			viz[i]=1;
            for(j=0;j<v[i].size();j++){
                sol[M]=v[i][j].ff;
				viz[v[i][j].ff]=1;
                back(2);
				viz[v[i][j].ff]=0;
            }
			viz[i]=0;
        }
    }
	freopen("izvor.out","w",stdout);
	printf("%d\n",nr);
	fclose(stdout);
	return 0;
}

Si aici e sursa cu matrice:

Cod:

#include<cstdio>
#include<iostream>
using namespace std;
int N,P,M;
int mat[21][21],nr,sol[10];
bool viz[21],ok[10];
void back(int k){
	int i,izvor=0;
	if(k==M){
		izvor=0;
		for(i=1;i<=M;i++){
			if(ok[i]){
				izvor=1;
				break;
			}
		}
		if(izvor)
			nr++;
	}
	else{
		for(i=1;i<=N;i++){
			if(mat[sol[k-1]][i] && !viz[i] && k<M-1){
				sol[k]=i;
				viz[i]=1;
				if(mat[sol[k-1]][i]==2)
					ok[k]=1;
				back(k+1);
				viz[i]=0;
				ok[k]=0;
			}
			else if(k==M-1){
				if(!viz[i] && mat[sol[k-1]][i] && mat[i][sol[M]]){
					sol[k]=i;
					viz[i]=1;
					if(mat[sol[k-1]][i]==2)
						ok[k]=1;
					if(mat[i][sol[M]]==2)
						ok[k+1]=1;
					back(k+1);
					viz[i]=0;
					ok[k]=0;
                                        ok[M]=0;
				}
			}
		}
	}
}
int main(){
	int i,x,y,z,j;
	freopen("izvor.in","r",stdin);
	scanf("%d%d%d",&N,&P,&M);
	for(i=1;i<=P;i++){
		scanf("%d%d%d",&x,&y,&z);
		mat[x][y]=mat[y][x]=z+1;
	}
	fclose(stdin);
	for(i=1;i<=N;i++){
		sol[1]=i;
		viz[i]=1;
		for(j=1;j<=N;j++){
			if(mat[i][j]){
				sol[M]=j;
				viz[j]=1;
				back(2);
				viz[j]=0;
			}
		}
		viz[i]=0;
	}
	freopen("izvor.out","w",stdout);
	printf("%d\n",nr);
	fclose(stdout);
	return 0;
}

Multumesc.

Buna!!Imi puteti recomanda un articol bun cu exemple sau probleme rezolvate sau ceva asemanator de unde as putea invata calumea Backtracking (inafara de wikipedia)??si eventual ceva probleme

Buna!Imi puteti explica un pic mai detaliat rezolvarea problemei.Am citit solutia oficiala,dar nu am inteles prea bine cum se face acea parcurgere folosind cele 5 cozi si matricea D cu cele 3 dimensiuni  .
Multumesc.

Salut! Am o intrebare. Cum as putea citi o matrice patratica in urmatoarul fel? (nu neaparat cu aceleasi numere am pus aceste numere ca sa vedeti ordinea parcurgerii)

Cod:

1  3  6  10  
2  5  9  13  
4  8  12  15  
7  11  14  16  

Multumesc,am reusit sa fac acea structura.
As mai avea o intrebare pot face un vector < bool > VIZ pt.vizitati.Am incercat sa dau de exemplu VIZ[n]=1 si imi da eroare....
Daca nu se poate asa cum se poate cu alocare dinamica??

Salut!!Am o problema eu vreau sa retin pentru a face un algoritmul lui Prim pt. APM intr-o structura extremitatile si costul.Pentru asta am nevoie de o structura cu 3 campuri.Deoarece nu sunt foarte sigur cat de mare sa declar vectorul din structura as vrea sa folosesc un vector din STL care aloca memorie dinamic.Problema e ca nu stiu cum fac un vector din STL cu 3 campuri.(stiu numai asa de 2 campuri vector < pair< int , int > > V )
Ceva idei??

Salut!!!Am nevoie de un program pentru a converti niste expresii din infix in prefix.Am tot cautat pe net dar nu gasesc unul care sa functioneze corect.Ma puteti ajuta??:>