1132 AI

[•Marius]

Aici puteti discuta despre problema Ai.

[•VisuianMihai]

Se afla pe infoarena si cealalta problema de la ofi 2011 ?? Cea cu expresia...

[•SpiderMan]

Uite-o aici.

[•SebiSebi]

Am vazut ca imi dadea incorect la a doua cerinta pe unele teste si nu gaseam greseala, apoi am loat testele oficiale si am vazut ca afisa corect. Este o problema cu evaluatorul? Daca nu poate sa imi spuna cineva ce gresesc? Multumesc anticipat!

[•Gady_paul]

Am si eu o mica chestie la problema asta. Merge bine...dar imi iese din timp. Ca idee...pentru determinarea lungimii maxime a zidului...am sortat toate punctele dupa x, am pus intr-un vector toate punctele care au acelasi x, am sortat vectorul dupa y si am numarat cate sunt consecutive. Apoi...am sortat dupa y, am pus toate cele egale intr-un vector...sortat dupa x...numarat consecutive...si la sfarsit...am luat cel mai mare numar. Apoi am luat fircare sursa cu tinta, am calculat ecuatia dreptei...apoi am iterat pe x...si am cautat valorile lui x pentru care y e numar intreg...si am cautat toate punctele respective si le-am introdus intr-un vector. apoi am luat toate punctele respective...si am calculat cu un lee distanta. E vreo metoda mai eficienta?

[•S7012MY]

Pentru determinarea lungimii maxime tu faci N^2 log N calcule dar poti sa faci doar N^2. Am impresia ca te-ai complicat.

[•Gady_paul]

Ok.....si cum se face mai simplu?

[•tzipleatud]

Cu un algoritm de tip Fill

[•Mitza444]

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

[•S7012MY]

Cred ca iesi din limita cozii

[•Mitza444]

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;
}

[•IronKing]

Salutare!
Am rezolvat doar prima cerință momentan si imi dă raspuns greșit la testul 12 si 20. Imi poate arata cineva fișierul de intrare pentru testele astea sau sa imi explice ce greșesc (cod: http://www.infoarena.ro/job_detail/942399?action=view-source).
Mulțumesc anticipat!

[•SebiSebi]

Poti sa iti descarci testele de la OJI 2011, clasa a 10-a din meniul "Downloads".

[•CosminRusu]

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;
}

Cred ca si tie ti-e greu sa intelegi ce si cum ai facut, asa ca nu te astepta la vreun raspuns la intrebarea ta, "De ce nu merge?". Cred ca cel mai bine ar fi sa faci LEE folosind coada ( queue ) din STL. Ca sa intelegi  mai bine cum functioneaza recomand problema Pietre2 de pe infoarena. Eu acolo am invatat cum si ce face queue-ul...
Sau daca nici asta nu te convinge sa inveti STL, atunci gandeste-te sa folosesti coada aceea circular.
Adica functiile, sau oriunde faci introducerea si extragerea unui elemnt din coada sa fie cam asa :

Cod:

void intr ( int c, int d )
{
       u=u+1;
       //Aici e smecheria, daca dai de limita cozii, incepi de la inceput
       if(u>20000)
            u=1;
       q[1][u]=c;
       q[2][u]=d;
} 
//extrag un element din coada
void extr(int &c,int &d)
{
     p=p+1;
     //La fel procedezi si in cazul extragerii
     if(p>20000)
           p=1;
     c=q[1][p];
     d=q[2][p];
}

Cam astea ar fi modalitatile pe care eu le stiu pentru ca sa scapi de KBS si incorect.

[•Sapientia]

Sa zicem ca avem un dreptunghi de lungime n si latime m(numere naturale diferite) si il impartim in nxm patratele de latura 1,apoi ducem o diagonalaa dreptunghiului.
Exista cazul in care diagonala acelui dreptunghi intersecteaza coltul unui patratel din dreptunghi?(inafara de colturile dreptunghiului)

[•romircea2010]

Daca cmmdc(n, m) este diferit de 1 atunci exista cazul pe care l-ai identificat iar daca numerele n si m sunt prime intre ele atunci diagonala intersecteaza doar colturile dreptunghiului.

[•hasmasandragos]

Daca robotii nu mai trebuie sa faca nici un pas sa protejeze tinta , se va afisa 0 ? Si cat va da pentru testul urmator ?

Cod:

6
4 4 1 1 6 6 2 2 5 5
3
1 3
1 4
1 5

Mie imi da:

Cod:

3
0

[•ionut98]

da asa e si mie tot atat imi da pe testul tau