Functioneaza perfect cum ai zis tu .Mersi de ajutor

Am niste intrebari la urmatoarea problema:http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=570.
1.De ce pentru testul 2 imi da 2 inloc de 1.(nu vad greseala pt. ca eu vizitez nodul 1in BF).
2.Cum pot rezolva problema altfel decat cu matrice de adiacenta??(am incercat cu o matrice bool da pica la memorie e prea mare 10000*10000,am auzit ca se poate cu ceva liste de vecini dar nu stiu sigur ce sunt).
In programul meu eu dau marchez arc intre i si i+1 daca citesc comanda "EXECUTA" si arc intre i si nr daca citesc comanda "SALT".
Dupa care fac o parcurgere BF si nodurile care raman nevizitate reprezinta instructiunile care nu se executa niciodata.

Cod:

#include<fstream>
#include<string>
#include<queue>
using namespace std;
string cmd[10001],aux;
bool graf[10001][10001],viz[10001];
int nr,rez;
queue <int> Q;
void BF(int n){
    int nod,i;
    Q.push(1);
    viz[1]=1;
    while(!Q.empty()){
        nod=Q.front();
        for(i=1;i<=n;i++){
            if(graf[nod][i] && !viz[i]){
                Q.push(i);
				viz[i]=1;
            }
        }
        Q.pop();
    }
}
int main(){
	int i=1,j;
	ifstream f("program1.in");
	f>>cmd[i];
	while(cmd[i]!="."){
		if(cmd[i]=="EXECUTA"){
			graf[i][i+1]=1;
		}
		else if(cmd[i]=="SALT"){
			f>>nr;
			graf[i][nr]=1;
			f>>aux;
			if(aux=="SAU"){
				f>>nr;
				graf[i][nr]=1;
			}
			else{
				i++;
				cmd[i]=aux;
				continue;
			}
		}
		i++;
		f>>cmd[i];
	}
	BF(i);
	ofstream g("program1.out");
	for(j=1;j<=i;j++)
		if(!viz[j])
			rez++;
	g<<rez;
	return 0;
}

Pai matricea mea poate fi si mai mare depinde de numarul nodurilot din graf.Am atasat un exemplu la ce folosesc matricea ca sa fie mai clar. (eu nu stiu cum au obtinut matricea a 2-a si a 3-a,cum au ridicat la putere sa ajunga la acelea)

Mersi!!Dar nu este si un algoritm mai usor pentru a ridica matricea la o putere pe foaie??Imi trebuie la partea de short problems unde nu poti folosi calculatorul,doar o foaie si un pix.(cred ca am uitat sa mentionez )

Cum pot sa ridic la o anumita putere  n  o matrice?? Am nevoie pt. ACSL pt. problemele cu grafuri in care se cer sa se gaseasca numarul drumurilor de lungime  n  dintr-un nod sau din toate nodurile.Am vazut ca se poate afla numarul lor prin ridicarea matricii de adiacenta la putere(puterea=lungimea unui drumului) si mi se pare mai usor si mai sigur decat sa  numeri drumurile pt. ca poti gresi foarte usor asa.

Imi puteti spune de ce iau WA inafara de 2 teste .Am facut o structura in care am retinut lungimea,greutatea si indicele initial.Am sortat crescator structura dupa latura sau daca e latura egala dupa greutate .Dupa am facut subsir crescator maximal de la capat incoace si dupa reconstitui solutia,pe care o afisez in ordine inversa.

Cod:

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
struct cub{
	int l,g,ind;
}v[4001];
bool comp(cub x,cub y){
	if(x.l==y.l)
		return (x.g<y.g);
	else 
		return (x.l<y.l);
}
vector < int > w;
int best[4001],poz[4001],nr[4001];
int main(){
	int n,i,p,j,mx=0;
	freopen("cuburi3.in","r",stdin);
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d%d",&v[i].l,&v[i].g);
		v[i].ind=i;
	}
	fclose(stdin);
	sort(v+1,v+n+1,comp);
	freopen("cuburi3.out","w",stdout);
	best[n]=v[n].l;
	poz[n]=-1;
	mx=v[n].l;
	p=n;
	nr[n]=1;
	for(i=n-1;i>=1;i--){
		poz[i]=-1;
		best[i]=v[i].l;
		for(j=i+1;j<=n;j++){
			if(v[i].g<v[j].g && best[i]<best[j]+v[i].l){
				best[i]=best[j]+v[i].l;
				poz[i]=j;
				nr[i]=nr[j]+1;
				if(best[i]>mx)
					mx=best[i],p=i;
			}
		}
	}
	printf("%d %d\n",nr[p],mx);
	i=p;
	while(i!=-1){
		w.push_back(v[i].ind);
		i=poz[i];
	}
	for(i=w.size()-1;i>=0;i--)
		printf("%d\n",w[i]);
	fclose(stdout);
	return 0;
}

Pt. intersesctie iei fiecare element din a si il cauti in b daca il gasesti il salvezi in alt vector c.
Pt. reuniune iei fiecare element din b si daca nu il gasesti in a il introduci la capat.
Ma gandesc ca daca e pentru tema nu  trebuie timp de executie.

Eu am facut simplu cu o coada din stl in care am introdus la citire toate zonele cu 0 si dupaia am facut un fel de Lee care adauga in coada fiecare zona inundabila si o variabila care creste cand se introduce un element in coada.Cred ca merge si cu o coada simpla ( sir),ideea este ca trebuie facut iterativ pt. ca dupa cum a explicat Boaca Cosmin daca faci revursiv depaseste 16 mb stiva .

Deci nu inteleg de ce nu functioneaza.... .AM determinat vectorul V cu cat creste suma daca incrementezi cu 1.Dupa am facut rucsacul sa vad daca se poate obtine suma.Am retinut intr-o matrice bool daca b[ i ] [ j ] 1 sau 0 daca DP[j]=DP[ j - V[ i ] ]+V[ i ] sau din DP[ j ].Si daca suma de pe DP[ s ]==s suma care o citesc atunci am pornit de la capat si am daca b[ x ][ y ]==1 atunci icrementez poz x de la baza cu unu si y=y-V[ x ],altfel x=x-1.Pe exemplu merge ,dar per total iau doar 10 pct cu 2 teste TLE si restul wrong answer.
P.S.:In triunghiu pe care il afisez apar si 0-uri ,nu am reusit sa fac altcumva.

Cod:

#include<fstream>
using namespace std;
int tri[20][20],V[20],DP[1000001];
bool B[19][1000001];
int nr;
void back(int n,int x){
	nr++;
	if(x-1>=1 && x-1<=n-1 && n-1>=1)
		back(n-1,x-1);
	if(x>=1 && x<=n-1 && n-1>=1)
		back(n-1,x);
}
int main(){
	int n,s,i,j,x,y;
	ifstream f("triunghi.in");
	f>>n>>s;
	f.close();
	V[1]=V[n]=n;
	for(i=2;i<=n-1;i++){
		nr=0;
		back(n,i);
		V[i]=nr;
	}
	for(i=1;i<=n;i++){
		for(j=1;j<=s;j++){
			if(DP[j-V[i]]+V[i]>=DP[j])
				B[i][j]=1;
			if(j>=V[i])
				DP[j]=max(DP[j],DP[j-V[i]]+V[i]);
		}
	}
	ofstream g("triunghi.out");
	if(DP[s]!=s)
		g<<"imposibil"<<"\n";
	else{
	x=n;y=s;
	while(x!=1 && y!=1){
		if(B[x][y]==1){
			y=y-V[x];
			tri[n][x]++;
		}
		else{
			x--;}
	}
	for(i=n-1;i>=1;i--)
		for(j=1;j<=i;j++)
			tri[i][j]=tri[i+1][j]+tri[i+1][j+1];
	for(i=1;i<=n;i++){
		for(j=1;j<=i;j++){
			g<<tri[i][j]<<" ";
		}
		g<<"\n";
	}
	}
	return 0;
}

Am o intrebare.Nu prea am inteles cum faci cu formula de la baza.Deci am un sir V care reprezinta numerele de la baza.Sa presupunem ca avem asa: n=3 si la inceput am pe V la baza numa valori de 1 pe toate pozitiile.O sa am:

Cod:

4
2 2
1 1 1

acestea au suma 11
daca incrementez cu unu pozitia 2:

Cod:

6
3 3
1 2 1

suma este 16,iar tu ai zis ca,creste cu x(adica 1)*V[2]==> creste cu 1,dar creste cu 5
Asta nu inteleg nu ar trebui sa conteze daca numarul care il incrementez i pe pozitia 1 sau n pt.ca atunci nu ar intra in suma finala de acelasi numar de ori ca si un numar care este pe poz dintre 1 si n.

Si daca am determinat poz de la baza de ce mai trebuie sa fac rucsacu pe ele nu ar trebui sa calculez numai liniile de mai sus??(cum determin triughiu doar cu rucsacu??)
Scuze ca tot intreb,dar chiar nu am inteles.
Multumesc pt. ajutor

Salut!!!Ma puteti ajuta cu o explicatie mai detaliata la problema Triunghi(http://infoarena.ro/problema/triunghi).Nu reusesc nici cum sa-mi dau seama cum se rezolva (sunt incepator la dinamica).
Multumesc.

Edit: are ceva daca nu folosesc programele din tutoriale? Eu am fost obisnuit cu Code:Blocks

Deci in tutorialul pe care ti l-am dat explica cum sa faci grafica in Mingw Developer Studio.Deoarece Mingw-ul nu are libraria aceea de grafica(ea exista in Borlan C++ de acolo e luata) iti da acolo pe site niste fisiere care trebuie copiate in dosarul Mingw si inca cateva chestii care trebuie facute ca sa functioneze grafica in Mingw.Din cate stiu eu Code:Blocks nu e foarte diferit de Mingw,dar nu stiu exact daca poti face grafica(nu am incercat).Dar poti face in Borland C++ sau Mingw nu e mare diferenta.

Nu poti sa imi decrii un pic mai detaliat rezolvarea problemei??Chiar nu imi dau seama cum as putea gasi numerele acelea de la baza.( nu sunt grozav la dinamica)

Ai putea incerca sa faci grafica in mingw ,daca chiar te plictiseste asa tare sa faci probleme.Desi prima data ar trebui sa rezolvi probleme pt. ca nu cred ca esti asa avansat daca nu ai auzit de alta librarie inafara de <iostream>.
Uite ai aici pe acest site un tutorial de grafica:http://www.infobits.ro/medii-mingw-developer-studio3.php
Sigur acesta e numai un exemplu sa vezi cum functioneaza,dar daca vrei poti cauta pe net sunt o gramda de functii cu care poti face grafica(lineto,circle etc.) si poti chiar sa creezi un joculet(de ex:pacman,snake).
Sper ca asta e destul de avansat !

Uite, ai aici un tutorial in romana de unde ai putea incepe sa inveti c++.Dar nu cred ca poti incepe sa faci direct jocuri ,ar trebui sa incepi cu ceva probleme mai simple  (foarte bine ar fi sa iei un manual de cls a IX-a unde e explicat tot de la inceput din pseudocod)
Acesta e tutorialu in romana:http://www.worldit.info/articole/tutoriale-video-c-in-limba-romana/
Si mai ai aici un site care explica foarte bine(acesta e in engleza) : http://www.cplusplus.com/info/

Nu m-am prins ca mergea cu o sigura linie 
Mersi mult

O ultima intrebare : Cum as putea sa retin si numere din care e formata fiecare suma?? (48=28+11+9 si 49=7+8+7+27)

Am facut cum mi-a sugerat scipianus cu problema rucsacului si merge tot inafara de ultimul test la care iau TLE.Ce optimizare pot sa-i mai fac??Am incercat citirea si scriere si cu fstream si cu cstdio aceealasi lucru TLE  : http://infoarena.ro/job_detail/670732
P.S.:Cum as putea face ca sa afisez si din ce numere este formata fiecare suma ca si in exemplu ?? (la jocul se cerea numai cele doua sume)

Cod:

#include<fstream>
using namespace std;
int G[1001],S;
int D[2][100002],s1,s2;
int main(){
	ifstream f("jocul.in");
	int n,i,j;
	int l=0;
	f>>n;
	for(i=1;i<=n;i++){
		f>>G[i];
		S+=G[i];
	}
	for(i=1;i<=n;i++,l=1-l){
		for(j=0;j<=S/2;j++){
			D[1-l][j] = D[l][j];
			if(j>=G[i])
				D[1-l][j]=max(D[1-l][j],D[l][j-G[i]]+G[i]);
		}
	}
	s1=D[l][S/2];
	s2=S-D[l][S/2];
	ofstream g("jocul.out");
	g<<min(s1,s2)<<" "<<max(s1,s2)<<"\n";
	return 0;
}

Buna!!!Ma puteti ajuta cu niste indicatii de rezolvare la problema urmatoare:

La sfarsitul noptii de Craciun, Mosul a poposit la bradul a doi frati, unde si-a golit sacul. Cand s-au trezit, fratii au intrat intr-o mare dilema: cum isi vor imparti ei cadourile mosului? Stiind ca fiecare cadou are o valoare (cuprinsa intre 1 si 100 inclusiv) si ca sunt maxim 100 de cadouri scrieti un program care sa determine sumele cadourilor fratilor, precum si modul de impartire, astfel incat sumele obtinute sa fie cele mai apropiate posibil.

Date de intrare:
In fisierul CADOURI.IN se gasesc informaţiile referitoare la cadouri: pe prima linie numarul total de cadouri, pe urmatoarea linie valorile lor.

Date de iesire: In fişierul CADOURI.OUT trebuie scrise doua sume care sunt cele mai apropiate corespunzătoare unei impartiri a cadourilor, pe a doua linie valorile corespunzătoare cadourilor care însumează prima suma găsită, pe a treia linie, valorile corespunzătoare cadourilor care însumează a doua suma găsită.
Exemplu:

CADOURI.IN
7
28 7 11 8 9 7 27

CADOURI.OUT
48 49
28 11 9
7 8 7 27

Buna!!!Ma puteti ajuta si pe mine cu o idee de rezolvare??Am observat ca trebuie sa descompun acea suma in n*(n+1)/2 numere ,dar nu imi dau seama cum pot afla acele numere cu propritatea din enunt...

Nu stiu de ce iau killed by signal 11   la testul 3 si 10.Va puteti uita putin peste sursa??Chiar nu imi dau seama ce am gresit.

Cod:

#include<cstdio>
using namespace std;
#define MAX 1002
int n,m,h,nr=0;
int mat[MAX][MAX];
bool q[MAX][MAX];
int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0};
void fill(int x,int y){
	int xnou,ynou,d;
	q[x][y]=1;
	if(mat[x][y]){
		mat[x][y]=0;
		nr++;
	}
	for(d=0;d<4;d++){
		xnou=x+dx[d];
		ynou=y+dy[d];
		if((mat[xnou][ynou]<h)&& !q[xnou][ynou] && xnou>=1 && xnou<=n && ynou>=1 && ynou<=m)
			fill(xnou,ynou);
	}
}
int main(){
	freopen("tsunami.in","r",stdin);
	freopen("tsunami.out","w",stdout);
	int i,j;
	scanf("%d%d%d",&n,&m,&h);
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++)
			scanf("%d",&mat[i][j]);
	}
	fclose(stdin);
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			if(mat[i][j]==0 && !q[i][j])
				fill(i,j);
		}
	}
	printf("%d\n",nr);
	fclose(stdout);
	return 0;
}

Am urmatoarea problema:
Se considera doua numere intregi m si n.Sa se determine cea mai mare valoare k , astfel incat numarul m! sa fie multiplu al numarului n^k(n la puterea k).
Date de intrare
Fisierul de intrare EXPONENT.IN contine o singura linie pe care se afla doua numere intregi,separate printr-un spatiu,reprezentand m si n.
Date de iesire
Fisierul EXPONENT.OUT va contine o singura linie pe care se va afla valoarea k.
Restrictie
2<=m,n<=2000000000(doua miliarde)
Exemplu
EXPONENT.IN                                   EXPONENT.OUT
20 24                                              6
Timpul de executie:1 secunda/test

Eu m-am gandit ca rezolvarea ar trebui implementata pe numere mari deoarece numerele depasesc si long long.Dar daca fac o implementare pe numere mari si il retin pe m! intr-un vector ,iar n^k in altul, ca sa verific daca m! este multiplu pt. n^k ar trebui sa fac impartirea pe numere mari,ceea ce e cam complicat(problema s-a dat la locala).
Ar fi o alta varianta mai usoara??

Ce parere aveti de teoria grafurilor de pe .campion ??(http://campion.edu.ro/arhiva/www/arhiva_2009/seds/17/index.htm)
Am citit  cu ceva vreme in urma teoria prezentata acolo,insa nu sunt inca in stare sa rezolv probleme de pe .campion cu grafuri.
Sunt numai clasa a X-a,dar ma gandeam ca e folositor sa stiu grafurile pt. ca m-ar putea ajuta la olimpiada olimpiada la diferite probleme.( cele cu Lee de exemplu,dar nu numai)

Mi-ati putea recomanda un site,tutorial sau ceva de unde as putea sa invat grafurile  (ceva teorie si eventual niste probleme rezolvate ca ex.) ??

Nu inteleg de ce nu merge ca am facut 2 Lee-uri si am pus if-uri cu toate cazurile cand apara tinta si am retinut minimurile (cand este pe aceeasi linie sau coloana cu sursa,cand e pe diagonala daca e posibil si cand robotul e in acelasi loc cu sursa ) .Am pus si marimea cozii mai mare,dar inca iau killed by signal 11 la cateva teste + ca unele teste nu merg.

Cod:

#include<cstdio>
using namespace std;
#define kmax 500000
int n,T1,T2,S1,S2,S3,S4,R1,R2,R3,R4,k,min1=1001,min2=1001,min3=1001,min4=1001;
int mat[1001][1001],mat2[1001][1001];
const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};
int q1[kmax][3],q2[kmax][3];
int abs(int plm){
	if(plm<0)
		plm=-plm;
	return plm;
}
int max(int a,int b){
	if(a>b)
		return a;
	return b;
}
int min(int a,int b){
	if(a<b)
		return a;
	return b;
}
int zid(int i,int j){
	int j2=j,l1=1,l2=1;
	while(mat[i][j2+1]==-1){
		j2++;
		l1++;
	}
	while(mat[i+1][j]==-1){
		i++;
		l2++;
	}
	if(l1>l2)
		return l1;
	return l2;
}
int Lee (){
	int p,u,xnou,ynou,tmp,x,y,d;
	q1[1][1]=R1;q1[1][2]=R2;
	q2[1][1]=R3;q2[1][2]=R4;
	for(p=1,u=1;p<=u;p++){
		x=q1[p][1];y=q1[p][2];
		for(d=0;d<4;d++){
			xnou=x+dx[d];
			ynou=y+dy[d];
			if(xnou>=1 && xnou<=n && ynou>=1 && ynou<=n && mat[xnou][ynou]==0){
				mat[xnou][ynou]=mat[x][y]+1;
				q1[++u][1]=xnou;
				q1[u][2]=ynou;
				if((xnou==S1 && xnou==T1 && ynou>min(S2,T2) && ynou<max(S2,T2))||(ynou==S2 && ynou==T2 && xnou>min(S1,T1) && xnou<max(S1,T1))){
					if(mat[xnou][ynou]<min1)
						min1=mat[xnou][ynou];
				}
				if((xnou==S3 && xnou==T1 && ynou>min(S4,T2) && ynou<max(S4,T2)) || (ynou==S4 && ynou==T2 && xnou>min(S3,T1) && xnou<max(S3,T1))){
					if(mat[xnou][ynou]<min2)
						min2=mat[xnou][ynou];
				}
				if(abs(xnou-S1)==abs(ynou-S2) && abs(xnou-T1)==abs(ynou-T2) && xnou>min(S1,T1) && xnou<max(S1,T1) && ynou>min(S2,T2) && ynou<max(S2,T2)){
					if(mat[xnou][ynou]<min1)
						min1=mat[xnou][ynou];
				}
				if(abs(xnou-S3)==abs(ynou-S4) && abs(xnou-T1)==abs(ynou-T2) && xnou>min(S3,T1) && xnou<max(S3,T1) && ynou>min(S4,T2) && ynou<max(S4,T2)){
					if(mat[xnou][ynou]<min2)
						min2=mat[xnou][ynou];
				}
				if(xnou==S1 && ynou==S2){
					if(mat[xnou][ynou]<min1)
						min1=mat[xnou][ynou];
				}
				if(xnou==S3 && ynou==S4){
					if(mat[xnou][ynou]<min2)
						min2=mat[xnou][ynou];
				}
			}
		}
	}
	for(p=1,u=1;p<=u;p++){
		x=q2[p][1];y=q2[p][2];
		for(d=0;d<4;d++){
			xnou=x+dx[d];
			ynou=y+dy[d];
			if(xnou>=1 && xnou<=n && ynou>=1 && ynou<=n && mat2[xnou][ynou]==0){
				mat2[xnou][ynou]=mat2[x][y]+1;
				q2[++u][1]=xnou;
				q2[u][2]=ynou;
				if((xnou==S1 && xnou==T1 && ynou>min(S2,T2) && ynou<max(S2,T2))||(ynou==S2 && ynou==T2 && xnou>min(S1,T1) && xnou<max(S1,T1))){
					if(mat2[xnou][ynou]<min3)
						min3=mat2[xnou][ynou];
				}
				if((xnou==S3 && xnou==T1 && ynou>min(S4,T2) && ynou<max(S4,T2)) || (ynou==S4 && ynou==T2 && xnou>min(S3,T1) && xnou<max(S3,T1))){
					if(mat2[xnou][ynou]<min4)
						min4=mat2[xnou][ynou];
				}
				if(abs(xnou-S1)==abs(ynou-S2) && abs(xnou-T1)==abs(ynou-T2) && xnou>min(S1,T1) && xnou<max(S1,T1) && ynou>min(S2,T2) && ynou<max(S2,T2)){
					if(mat2[xnou][ynou]<min3)
						min3=mat2[xnou][ynou];
				}
				if(abs(xnou-S3)==abs(ynou-S4) && abs(xnou-T1)==abs(ynou-T2) && xnou>min(S3,T1) && xnou<max(S3,T1) && ynou>min(S4,T2) && ynou<max(S4,T2)){
					if(mat2[xnou][ynou]<min4)
						min4=mat2[xnou][ynou];
				}
				if(xnou==S1 && ynou==S2){
					if(mat2[xnou][ynou]<min3)
						min3=mat2[xnou][ynou];
				}
				if(xnou==S3 && ynou==S4){
					if(mat2[xnou][ynou]<min4)
						min4=mat2[xnou][ynou];
				}
			}
		}
	}
	tmp=min(max(min1,min4),max(min2,min3));
	return tmp;
}
	
int main(){
	int i,j,maxz=0,xx,yy,timp;
	freopen("ai.in","r",stdin);
	freopen("ai.out","w",stdout);
	scanf("%d",&n);
	scanf("%d%d%d%d%d%d%d%d%d%d",&T1,&T2,&S1,&S2,&S3,&S4,&R1,&R2,&R3,&R4);
	scanf("%d",&k);
	for(i=1;i<=k;i++){
		scanf("%d%d",&xx,&yy);
		mat[xx][yy]=-1;
	}
	mat[T1][T2]=-2;
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			mat2[i][j]=mat[i][j];
			if(mat[i][j]==-1)
				if(zid(i,j)>maxz)
					maxz=zid(i,j);
		}
	}
	timp=Lee();
	printf("%d\n",maxz);
	printf("%d\n",timp);
	return 0;
}

Am si eu o problema....Am rezolvat problema imi da bine pe exemplu si pe cateva teste mai mici ,dar la cele mai mari tot iau killed by signal 11.
In memrie cred ca ma incadrez deoarece limita e destul de mare ,dar imi da o eroare ceva de genul ca un ciclu infinit si nu reusesc sa-mi dau seama nici cum care e problema.Ma puteti ajuta??(cred totusi ca problema la Lee)
Aici aveti sursa si ce mesaj imi da compilatoru:
http://infoarena.ro/job_detail/660028
http://infoarena.ro/job_detail/660028?action=view-source