477 Alee

[•DITzoneC]

Aici puteţi discuta despre problema Alee.

[•05_Yohn]

de ce nu-mi compileaza sursa??

Cod:

   1. {$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R-,S-,T-,V+,X+}  
   2. {$M 16384,0,655360}  
   3. program lee;  
   4. const oriz:array[1..4]of shortint=(1,-1,0,0);  
   5.       vert:array[1..4]of shortint=(0,0,1,-1);  
   6. var f,g:text;  
   7.     v:array[1..175,1..175]of integer;  
   8.     modif:boolean;  
   9.     x,y,x1,y1,x2,y2,n:byte;  
  10.     m,pas,xnou,ynou,i:integer;  
  11. begin  
  12. assign(f,'alee.in');  
  13. assign(g,'alee.out');  
  14. reset(f);  
  15. rewrite(g);  
  16. readln(f,n,m);  
  17. for i:=1 to m do begin  
  18.     readln(f,x,y);  
  19.     v[x,y]:=-1;  
  20. end;  
  21. readln(f,x1,y1,x2,y2);  
  22. x:=1;y:=1;  
  23. modif:=true;  
  24. pas:=1;  
  25. v[x1,y1]:=pas;  
  26. while modif do begin  
  27.       modif:=false;  
  28.       for x:=1 to n do  
  29.           for y:=1 to n do  
  30.               if v[x,y]=pas then begin  
  31.                  for i:=1 to 4 do begin  
  32.                      xnou:=x+oriz[i];  
  33.                      ynou:=y+vert[i];  
  34.                      if (xnou in [1..n])and(ynou in [1..n]) then  
  35.                         if (v[xnou,ynou]=0)and(v[xnou,ynou]<>-1)then begin  
  36.                            v[xnou,ynou]:=pas+1;  
  37.                            modif:=true;  
  38.                         end;  
  39.                         if v[x2,y2]<>0 then begin  
  40.                            modif:=false;  
  41.                            x:=n;y:=n;  
  42.                         end;  
  43.                  end;  
  44.               end;  
  45.      pas:=pas+1;  
  46. end;  
  47. writeln(g,v[x2,y2]);  
  48. close(f);close(g);  
  49. end.  

editat de moderator: foloseste tagul "[ code ]" cand postezi cod

[•pauldb]

user.fpc(41,32) Error: Illegal assignment to for-loop variable "x"
user.fpc(41,37) Error: Illegal assignment to for-loop variable "y"

Erorile de compilare sunt in general destul de clare (ca si acum). Nu ai voie sa modifici contorul intr-un for. Incearca alta data sa te descurci singur si daca chiar nu reusesti, abia atunci posteaza.

[•cristiprg]

am facut problema de 90 puncte...iese din timp la un test...cum ati rezolvat-o voi?...care ati luat 100...eu am facut pur si simplu , un lee clasic...

[•Florian]

Lee clasic trebuie. Vezi poate iti intra in vreun ciclu infinit... Nu prea e nimic special la aceasta problema. S-au pastrat testele de la oji 2007. Deci poti sa le iei de pe olimpiada.info. Succes 

[•Tabara]

am facut problema de 90 puncte...iese din timp la un test...cum ati rezolvat-o voi?...care ati luat 100...eu am facut pur si simplu , un lee clasic...

Si eu am patit la fel. Incearca sa maresti coada ...

[•Mishu91]

Sau incearca sa faci dinamic, si nu mai stres cu maritu cozii   

[•Mishu91]

Incearca sa mai maresti putin coada, tu ai declarat-o de exact 175*175 , si pt testele in care matricea are 175*175 elemente iese din memorie

[•Pepelea_Flaviu]

cam urat sa pui sursa pe forum sa iti caute altul erorile

[•wefgef]

cam urat sa pui sursa pe forum sa iti caute altul erorile

Eh, e foarte util uneori sa fii in stare sa gasesti erorile rapid . Nu stiu cat de castigat este cel care pune sursa pe forum, insa cel care gaseste bugurile cu siguranta se alege cu ceva.

[•xtreme]

Am o nedumerire...daca compilez sursa cu compilatorul de pe infoarena pentru C++ iau 100 in schimb primesc erori pe evaluatoru OJI(chiar crash)...dupa calculele mele am folosit  memorie statica 177*177*2+9*2+31000*2=124676 bytes=124.676 kilobytes...tinand cont ca la OJI se da 640 kilobytes>124.676 kilobytes nu cred ca am depasit memoria dispusa...unde gresesc?

Cod:

#include<iostream.h>
#include<fstream.h>

int main()
	{
	struct orice
		{unsigned char x,y;}coada[31000];
	int parc[177][177],n,m,i,j,l,c,l2,c2,nr=0;
	fstream f("alee.in",ios::in),g("alee.out",ios::out);
	f>>n>>m;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			parc[i][j]=30625;
	for(i=1;i<=n;i++)
		{
		parc[0][i]=-1;parc[n+1][i]=-1;
		parc[i][n+1]=-1;parc[i][0]=-1;
		}
	for(i=1;i<=m;i++)
		{f>>l>>c;parc[l][c]=-1;}
	f>>l>>c>>l2>>c2;
	i=0;parc[l][c]=0;coada[0].x=l;coada[0].y=c;
	while(i<=nr)
		{
		l=int(coada[i].x);c=int(coada[i].y);
		if(parc[l][c]+1<parc[l+1][c])
			{parc[l+1][c]=parc[l][c]+1;nr++;coada[nr].x=l+1;coada[nr].y=c;}
		if(parc[l][c]+1<parc[l-1][c])
			{parc[l-1][c]=parc[l][c]+1;nr++;coada[nr].x=l-1;coada[nr].y=c;}
		if(parc[l][c]+1<parc[l][c+1])
			{parc[l][c+1]=parc[l][c]+1;nr++;coada[nr].x=l;coada[nr].y=c+1;}
		if(parc[l][c]+1<parc[l][c-1])
			{parc[l][c-1]=parc[l][c]+1;nr++;coada[nr].x=l;coada[nr].y=c-1;}
		i++;
		}
	g<<parc[l2][c2]+1;
	f.close();g.close();return 0;
	}

                                                                                                 

[•wefgef]

Tu aloci pe stiva (in interiorul functiilor). Scoate toate variabilele mari in afara functiei main() si iti va merge.

[•xtreme]

Tu aloci pe stiva (in interiorul functiilor). Scoate toate variabilele mari in afara functiei main() si iti va merge.

am scos "structura orice" in afara mainului.Asa aloc static (31000*2)=62000<64000(limita) bytes(coada) in stiva(in functia main) aloc (9(variabile)+177*177(matricea parc))*2=62676<65520  bytes.....si tot imi da abnormal program termination...de ce?

Cod:

#include<iostream.h>
#include<fstream.h>

struct orice
		{unsigned char x,y;}coada[31000];


int main()
	{
	int n,m,i,j,l,c,l2,c2,nr=0,parc[177][177];
	fstream f("alee.in",ios::in),g("alee.out",ios::out);
	f>>n>>m;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			parc[i][j]=30625;
	for(i=1;i<=n;i++)
		{
		parc[0][i]=-1;parc[n+1][i]=-1;
		parc[i][n+1]=-1;parc[i][0]=-1;
		}
	for(i=1;i<=m;i++)
		{f>>l>>c;parc[l][c]=-1;}
	f>>l>>c>>l2>>c2;
	i=0;parc[l][c]=0;coada[0].x=l;coada[0].y=c;
	while(i<=nr)
		{
		l=int(coada[i].x);c=int(coada[i].y);
		if(parc[l][c]+1<parc[l+1][c])
			{parc[l+1][c]=parc[l][c]+1;nr++;coada[nr].x=l+1;coada[nr].y=c;}
		if(parc[l][c]+1<parc[l-1][c])
			{parc[l-1][c]=parc[l][c]+1;nr++;coada[nr].x=l-1;coada[nr].y=c;}
		if(parc[l][c]+1<parc[l][c+1])
			{parc[l][c+1]=parc[l][c]+1;nr++;coada[nr].x=l;coada[nr].y=c+1;}
		if(parc[l][c]+1<parc[l][c-1])
			{parc[l][c-1]=parc[l][c]+1;nr++;coada[nr].x=l;coada[nr].y=c-1;}
		i++;
		}
	g<<parc[l2][c2]+1;
	f.close();g.close();return 0;
	}

[•toni2007]

Pe Borland sunt teoretic 640 de kb, dar nu poti avea acces la toata memoria decat lucrand cu pointeri. Incearca sa gasesti o solutie mai simpla. Eu nu folosesc decat 16 kb de memorie pe majoritatea testelor, doar pe testul maxim folosesc 288 kb.

Scoate matricea parc din main. Ocupa 177 * 177 * 2 ~= 62 de kb daca e in main si spargi stiva.

Spor

[•xtreme]

Pe Borland sunt teoretic 640 de kb, dar nu poti avea acces la toata memoria decat lucrand cu pointeri. Incearca sa gasesti o solutie mai simpla. Eu nu folosesc decat 16 kb de memorie pe majoritatea testelor, doar pe testul maxim folosesc 288 kb.

Scoate matricea parc din main. Ocupa 177 * 177 * 2 ~= 62 de kb daca e in main si spargi stiva.

Spor

vrei sa zici ca,compilatorul Borland C(care daca nu gresesc este compilatorul lui Borland C++ 3.1 si care e la OJI pt limabju de programare C++) dispune de 640 KB(KB-kilobytes,Kb-kilobits)?eu stiam ca pentru datele alocate static dispun de 64 Kilobytes,pentru stiva maxim 65 Kilobytes iar pentru heap 655 kilobytes pe compilatorul de mai sus...eu problema am rezolvat-o(compiland-o cu g++,gcc) dar pe mine ma intereseaza de ce nu pot aloca memoria respectiva cu compilatorul Borland C...in care zona pun prea mult?....problema se rezolva cu un Lee clasic...singura optimizare la problema aceasta ar fi sa implementez coada dinamic...inca ceva pe stiva ai 65 Kilobytes,de ce sa se sparga la 62 kilobytes?....daka pun coada statica si restu pe stiva(in main) tot abnormal program termination imi da...

[•toni2007]

Incearca sa implementezi coada dinamic si scapi de probleme. Daca nu ma insel asa era implementata si in sursa oficiala.

Spor

[•xtreme]

Incearca sa implementezi coada dinamic si scapi de probleme. Daca nu ma insel asa era implementata si in sursa oficiala.

Spor

In sursa oficiala a fost implementata coada static si in C,nu in C++(de aceea pt ca nu se poate face cu alocare statica in C++).

[•toni2007]

Cum adica a fost implementata in C nu in C++? Se aloca EXACT la fel static in C ca in C++. La alocarea dinamica e diferit.

[•xtreme]

Cum adica a fost implementata in C nu in C++? Se aloca EXACT la fel static in C ca in C++. La alocarea dinamica e diferit.

nu cunosc prea multe in C...mai mult cunosc C++..am observat ca la solutii(olimpiade) in general le rezolva in C daka sunt probleme la implementare(de genu memorie) si in rest in c++(poate gresesc)...oricum,dupa cat am intors problema nu cred ca se poate face  cu compilatorul Borland C si cu limbajul c++ cu alocare statica a cozii... ba mai mult am implementat coada dinamic iar nu ma lasa ka matricea(parcul) sa-l fak mai mult de [ 170 ] [ 170 ](daka pun [ 175 ] [ 175 ] in afara stivei imi da abnormal program termination iar daka pun in stiva imi da null pointer assigment pe comp Borland C)

[•toni2007]

Tot ce merge in C merge si in C++, C++ fiind C + clase + stl. In rest sunt foarte mici diferente intre C si C++, la nivelul variabilelor adresa, la structuri, si la alocarea memoriei dinamic (in c++ se poate aloca in 2 feluri, cu malloc si new), dar deja suntem off-topic. Daca vrei diferentele exacte intre C si C++ deschide un topic in categoria informatica.

[•gabor_oliviu1991]

am rezolvat problema cu dinamica. toate bune si frumoase exceptant testul 7 pe care iau TLE. http://infoarena.ro/job_detail/255720 .timpii la restul testelor sunt mici, deci presupun ca acolo imi cicleaza programul. unde ar putea fi gresala?

[•Pepelea_Flaviu]

Ai putea descrie putin ce faci pe-acolo si ce matrici/ vectori ai folosit.

[•gabor_oliviu1991]

deci... matricea initiala ii initializata cu 0 daca am drum liber, si -1 daka e pom. in locul din care pornesc pun 1, si apoi atata timp cat in matricea mea mai am elemente de 0, pentru fiecare a(i,j)==0 imi determin minimul din N,E,S,V si actualizez a(i,j) cu min+1. daka e prea explicit va rog sa-mi ziceti

[•c_e_manu]

tu faci minimul daca nu e -1... si ce faci daca in N, E, V, si S e pom si tu nu poti ajunge in punctul respectiv? ...

ceva de genul:

Cod:

0 0 -1 0 0
0 -1 0 -1 0
0 0 -1 0 0
0 0 0 0 0
0 0 0 0 0

[•gabor_oliviu1991]

merge si pe exemplul acela. chiar nu stiu unde se poate impotmoli...