414 Excursie

[•DITzoneC]

Aici puteţi discuta despre problema Excursie.

[•DITzoneC]

S-a modificat un pic enuntul acestei probleme. 

[•zbarni]

salut. am rezolvat problema excursie, > job: http://infoarena.ro/job_detail/185238 dar mi se intampla un lucru ciudat: iau 5 puncte  am downloadat testele de la ONI 2007, si evaluand manual merge corect pe primele 10 teste, cu compilatorul borland...dupa asta da error pt ca ocup mai multa memorie decat imi permite, dar cu gnu ar trebui sa mearga.  Iar daca compilez cu dev-c++ si merg ori pe testele linux ori pe cele windows scrie rezultatul dar ori partial, ori cu +e26 sau nu stiu ce numere si litere chiar e enervant.. personal cred ca am o problema cu scrierea de 3 zecimale: folosesc setprecision din c++, dar nu stiu ce are. Tind sa cred ca exista si alte modalitati(more efficient and less annoying) cu care pot sa rezolv problema. Ma puteti ajuta cumva?
ultimele randuri:

Cod:

# if (a[x2][y2].drum>Lmax)  
#     ki<<-1;  
#   else  
#     ki<<setprecision(3)<<a[x2][y2].efort<<" "<<setprecision(3)<<a[x2][y2].drum;  
#   ki<<'\n';  
#   ki.close();  
#   return 0;  

folosesc pentru efort si drum double long, pentru value short, pentru celelalte short.
Mersi inainte

[•wefgef]

Pentru a printa un numar real cu 3 zecimale foloseste functia printf:

Cod:

printf("%.3lf\n", x)

x este un double.

[•stef2n]

Cu

Cod:

out << fixed << setprecision(3) << N

ar trebui sa mearga. "out" e fisierul de iesire, iar "N" este numarul (double) pe care vrei sa-l printezi.

[•zbarni]

Am folosit setiosflags(ios::fixed), si merge, insa la testul 5 primesc Killed by signal... presupun ca este o problema legata de memorie, insa nu sunt sigur. http://infoarena.ro/job_detail/185341 E adevarat ca memoria folosita e cea mai mare la t 5 :936. Am incercat sa maresc marimea listei pana la 150.000 (nu cred ca e nevoie..), si tot nu merge. Ceva idei?
Sursa:
 

Cod:

   1. #include<fstream>  
   2. #include<math.h>  
   3. #include<iomanip>  
   4. #include<stdio.h>  
   5. #define g 41  
   6. #define G 50000  
   7. using namespace std;  
   8. struct MATRIX  
   9.  {  
  10.   double efort,drum;  
  11.   short value;  
  12.  } ;  
  13. MATRIX a[g][g];  
  14. struct LIST  
  15.  {  
  16.   int x,y;  
  17.  };  
  18.   
  19.   LIST lista[G];  
  20. int main()  
  21.  {  
  22.   ifstream be ("excursie.in");  
  23.   ofstream ki ("excursie.out");  
  24.   int n,m,i,j,x1,x2,y1,y2,e,v;  
  25.   
  26.   double ef,d,Lmax;  
  27.   be>>n>>m>>Lmax;  
  28.   for (i=1;i<=n;i++)  
  29.      for (j=1;j<=m;j++)  
  30.     be>>a[i][j].value;  
  31.   be>>x1>>y1>>x2>>y2;  
  32.   be.close();  
  33.   e=1;v=1;int k;  
  34.   lista[1].x=x1; lista[1].y=y1;  
  35.   while (e<=v)  
  36.    {  
  37.     i=lista[e].x; j=lista[e].y;  
  38.     ef=-1;  
  39.     if (i!=x2||j!=y2)  
  40.      {  
  41.     k=0;  
  42.     if (i>1 && (i-1!=lista[1].x || j!=lista[1].y)) /////////////////////  
  43.       {  
  44.        if (a[i-1][j].value>a[i][j].value)  
  45.      { x1=a[i-1][j].value; y1=a[i][j].value; }  
  46.        else  
  47.      if (a[i-1][j].value<a[i][j].value)  
  48.        { y1=a[i-1][j].value; x1=a[i][j].value; k=1;}  
  49.      else  
  50.        { ef=1; d=1; }  
  51.        if (ef!=1)  
  52.      { d=sqrt((x1-y1)*(x1-y1)+1);  
  53.        if (k)  
  54.          ef=(d*(x1-y1))/2;  
  55.        else  
  56.          ef=d*(x1-y1); }  
  57.        if (a[i-1][j].efort==0 || (a[i-1][j].efort>=a[i][j].efort+ef))  
  58.      {  
  59.       lista[++v].x=i-1; lista[v].y=j;  
  60.       a[i-1][j].efort=a[i][j].efort+ef;  
  61.       a[i-1][j].drum=a[i][j].drum+d;  
  62.      }  
  63.       }  
  64.     ef=-1; k=0;  
  65.     if (j<m && (j+1!=lista[1].y || i!=lista[1].x))   /////////////////////////////////////  
  66.       {  
  67.        if (a[i][j+1].value>a[i][j].value)  
  68.      { x1=a[i][j+1].value; y1=a[i][j].value; }  
  69.        else  
  70.      if (a[i][j+1].value<a[i][j].value)  
  71.        { y1=a[i][j+1].value; x1=a[i][j].value; k=1;}  
  72.      else  
  73.        { ef=1; d=1; }  
  74.        if (ef!=1)  
  75.      { d=sqrt((x1-y1)*(x1-y1)+1);  
  76.        if (k)  
  77.          ef=(d*(x1-y1))/2;  
  78.        else ef=d*(x1-y1); }  
  79.        if (a[i][j+1].efort==0 || (a[i][j+1].efort>=a[i][j].efort+ef))  
  80.      {  
  81.        lista[++v].x=i; lista[v].y=j+1;  
  82.        a[i][j+1].efort=a[i][j].efort+ef;  
  83.        a[i][j+1].drum=a[i][j].drum+d;  
  84.      }  
  85.       }  
  86.     ef=-1; k=0;  
  87.     if (i<n && (i+1!=lista[1].x || j!=lista[1].y)) /////////////////////////////  
  88.       {  
  89.        if (a[i+1][j].value>a[i][j].value)  
  90.      { x1=a[i+1][j].value; y1=a[i][j].value; }  
  91.        else  
  92.      if (a[i+1][j].value<a[i][j].value)  
  93.        { y1=a[i+1][j].value; x1=a[i][j].value; k=1; }  
  94.      else  
  95.        { ef=1; d=1; }  
  96.        if (ef!=1)  
  97.      { d=sqrt((x1-y1)*(x1-y1)+1);  
  98.        if (k)  
  99.          ef=(d*(x1-y1))/2;  
 100.        else ef=d*(x1-y1); }  
 101.        if (a[i+1][j].efort==0 || (a[i+1][j].efort>=a[i][j].efort+ef))  
 102.      {  
 103.       lista[++v].x=i+1; lista[v].y=j;  
 104.       a[i+1][j].efort=a[i][j].efort+ef;  
 105.       a[i+1][j].drum=a[i][j].drum+d;  
 106.      }  
 107.       }  
 108.     ef=-1; k=0;  
 109.     if (j>1&& (j-1!=lista[1].y || i!=lista[1].x)) /////////////////////  
 110.       {  
 111.        if (a[i][j-1].value>a[i][j].value)  
 112.      { x1=a[i][j-1].value; y1=a[i][j].value; }  
 113.        else  
 114.      if (a[i][j-1].value<a[i][j].value)  
 115.        { y1=a[i][j-1].value; x1=a[i][j].value;k=1; }  
 116.      else  
 117.        { ef=1; d=1; }  
 118.        if (ef!=1)  
 119.      { d=sqrt((x1-y1)*(x1-y1)+1);  
 120.        if (k)  
 121.          ef=(d*(x1-y1))/2;  
 122.        else ef=d*(x1-y1); }  
 123.        if (a[i][j-1].efort==0 || (a[i][j-1].efort>=a[i][j].efort+ef))  
 124.      {  
 125.        lista[++v].x=i; lista[v].y=j-1;  
 126.        a[i][j-1].efort=a[i][j].efort+ef;  
 127.        a[i][j-1].drum=a[i][j].drum+d;  
 128.      }  
 129.       }  
 130.      }  
 131.     e++;  
 132.    }  
 133.   if (a[x2][y2].drum>Lmax)  
 134.     ki<<-1;  
 135.   else  
 136.     ki<<setprecision(3)<<setiosflags(ios::fixed)<<a[x2][y2].efort<<" ";  
 137.     ki<<setprecision(3)<<setiosflags(ios::fixed)<<a[x2][y2].drum;  
 138.   ki<<'\n';  
 139.   ki.close();  
 140.   return 0;  
 141.  }  

E cam lunga dar na..

[•fireatmyself]

poate accesezi o zona de memorie nealocata (coada[-1] sau cpada[150100]).
citeste aici pentru mai multe detalii.

[•zbarni]

nu cred: am marit coada la 1.000.000, si matricea la 55, si tot killed' imi da... are ceva special testul 5?

[•fireatmyself]

genereaza niste teste care sa fie cat mai apropiate de limitele problemei. sigur o sa prinzi un test pe care pica. 

L.E.: iti merge bine daca toata matricea are aceeasi valoare (cu n si m mare)?

[•cipri_tom]

are cineva vreo idee de ce imi intra in ciclu infinit la partea de mai jos:

Cod:

do
	{
		modif = false;
		for ( int i = 1; i <= m; ++i )
			for ( int j = 1; j <= n; ++j )
				if ( c[i][j] != CEVA_MARE )
					for ( int d = 0; d < 4; ++d )
					{
						iv = i + di[d];
						jv = j + dj[d];
						EFORT = Effort ( a[i][j], a[iv][jv] );
						if ( OK ( iv, jv ) and c[iv][jv] > c[i][j] + EFORT )
						{
							c[iv][jv] = c[i][j] + EFORT;
							modif = true;
						}
					}
	} while ( modif );

cred ca e din cauza compararii a 2a numere reale.... am urmarit executia si am vazut ca intra prin ultimul if si daca c[iv][jv] este egal cu c[j] + EFORT ... adica, EFORT nu da de fiecare data la fel pentru aceiasi 2 vecini.

[•alex_ovidiunitu]

Daca exista mai multe trasee cu acelasi efort minim se va alege cel care are lungimea cea mai mica. In cazul in care aceasta lungime depaseste valoarea Lmax se va afisa -1.

Nu ca ar fi ceva foarte imporatant, dar nu exista teste cu acest caz