Titlul: 414 Excursie
Scris de: Adrian Diaconu din Aprilie 24, 2007, 07:43:40
Aici puteţi discuta despre problema Excursie (http://infoarena.ro/problema/excursie).
Titlul: Răspuns: 414 Excursie
Scris de: Adrian Diaconu din Iunie 07, 2007, 22:51:19
S-a modificat un pic enuntul acestei probleme. :-'
Titlul: Ciudat
Scris de: Zajzon Barna din Aprilie 24, 2008, 22:23:50
salut. am rezolvat problema excursie, > job: http://infoarena.ro/job_detail/185238 (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. :annoyed: 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 :-s 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: # 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 :)
Titlul: Răspuns: 414 Excursie
Scris de: Andrei Grigorean din Aprilie 24, 2008, 23:00:07
Pentru a printa un numar real cu 3 zecimale foloseste functia printf: x este un double.
Titlul: Răspuns: 414 Excursie
Scris de: Stefan Istrate din Aprilie 24, 2008, 23:08:20
Cu 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.
Titlul: Răspuns: 414 Excursie
Scris de: Zajzon Barna din Aprilie 25, 2008, 08:26:03
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 (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: 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.. :P
Titlul: Răspuns: 414 Excursie
Scris de: Bogdan-Alexandru Stoica din Aprilie 25, 2008, 10:41:43
poate accesezi o zona de memorie nealocata (coada[-1] sau cpada[150100]).
citeste aici (http://infoarena.ro/documentatie/borderoul-de-evaluare) pentru mai multe detalii.
Titlul: Răspuns: 414 Excursie
Scris de: Zajzon Barna din Aprilie 25, 2008, 14:16:08
nu cred: am marit coada la 1.000.000, si matricea la 55, si tot killed' imi da... ](*,) are ceva special testul 5? :)
Titlul: Răspuns: 414 Excursie
Scris de: Bogdan-Alexandru Stoica din Aprilie 25, 2008, 23:35:30
genereaza niste teste care sa fie cat mai apropiate de limitele problemei. sigur o sa prinzi un test pe care pica. :thumbup:
L.E.: iti merge bine daca toata matricea are aceeasi valoare (cu n si m mare)?
Titlul: Răspuns: 414 Excursie
Scris de: Ciprian Tomoiaga din Februarie 28, 2010, 16:00:17
are cineva vreo idee de ce imi intra in ciclu infinit la partea de mai jos: 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.
Titlul: Răspuns: 414 Excursie
Scris de: Alex Ovidiu Nitu din Martie 17, 2012, 22:12:36
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 :ok:
|