Discussion of Problem 1113. JeepPage 2 Методы Программирования и Прикладные Алгоритмы I got AC, but my program on the input data 10 9 Throws 13, although the correct answer 12. Edited by author 22.09.2014 17:03 PLZ HELP!!! why? #include<iostream> using namespace std; int main() { int a,m,n; double d,o,w; cin>>n>>m; a=0; w=0; o=0; bool q=true; while(q){ a++; d=m/(a << 1-1); if (w+d>=n){ q=false; } w=w+d; o=o+m; }
d=n-w; o=o+d*(a << 1-1); cout<<(abs(o+0.49999999999)); return 0; } Edited by author 21.06.2014 02:18 Edited by author 21.06.2014 02:18 Edited by author 21.06.2014 21:29 Edited by author 21.06.2014 21:27 while(s+m/(2*t-1)<n){s+=m/(2*t-1);oil=t*m;t++;} ans=(n-s)*(2*t-1)+oil; printf("%.0lf",ans+0.5 - 1e-8); Page 1 I advice you to read books of Martin Gardner. There is beautiful solution of this problem. Or you can write DP and look at the points where stations are built. Anyone help me to understand or solve this problem.I didn't understand how comes the answer 3837 [code deleted] Edited by author 26.08.2009 15:35 #include <iostream> #include <stdlib.h> using namespace std; int main() { int m, n, f; double out; div_t o; double way[32005] = {0}; long long int oil[32005] = {0}; cin >> n >> m; way[1] = m; oil[1] = m;
for(f = 1; way[f - 1] + m / (2 * f - 1) < n; f++) { way[f] = way[f - 1] + m / (2 * f - 1); oil[f] = f * m; } out = (n - way[f - 1]) * (2 * f - 1) + oil[f - 1]; o = div(out, 1); if(abs(out - o.quot) < 1e-8) cout << o.quot; else cout << o.quot + 1;
} Some helpful description can be found at http://mathworld.wolfram.com/JeepProblem.html But i still do not understand one thing : For example, the farthest a Jeep with n==1 drum can travel is obviously 1 unit. However, with n==2 drums of gas, the maximum distance is achieved by filling up the Jeep's tank with the first drum, traveling 1/3 of a unit, storing 1/3 of a drum of fuel there, and then returning to base with the remaining 1/3 of a tank. At the base, the tank is filled with the second drum. The Jeep then travels 1/3 of a unit (expending 1/3 of a drum of fuel), refills the tank using the 1/3 of a drum of fuel stored there, and continues an additional 1 unit of distance on a full tank, giving a total distance of 4/3. How this logic works with n==3 ??? I'd like to know as well... I'll try to explain... Suppose fuel tank capacity = 1 unit and we have 3 units of patrol at point A. There will be three parts of the path with lengths 1/5, 1/3 and 1. A--1/5--B------1/3------C---------------1---------------D 1. Let's carry 2 units of patrol from A to B. It would take 3 trips. Step 0: Fuel(A) = 3, Fuel(B) = 0. Step 1: Fuel(A) = 2, Fuel(B) = 3/5. Step 2: Fuel(A) = 1, Fuel(B) = 6/5. Step 3: Fule(A) = 0, Fule(B) = 10/5 = 2. And we are at B now. 2. Let's carry 1 unit of patrol from B to C. It would take 2 trips. Step 0: Fuel(B) = 2, Fuel(C) = 0. Step 1: Fuel(A) = 1, Fuel(B) = 1/3. Step 2: Fuel(A) = 2, Fuel(B) = 3/3 = 1. And we are at C now. 3. Let's carry 1 unit of patrol from C to D. It would take only 1 trip. So if we have 1-unit fuel tank and 3 litres of patrol we can travel for 1+1/3+1/5 = 23/15 km. Good luck! Thank you for the explanation, everything is clear now. when n == 1 we can travel 1 unit. when n == 2 we will carry 1 drum as far as I can, so the situation is as same as n == 1, we can spend the extra 1 drum of gas on the way for 3 times (carry 1 , go , left some, back ,carry 1, go), so I can travel 1/3 for the best solution when n == 3 we will carry 2 drums of gas as far as I can, then it became situation #2 , the extra 1 drum of gas will use 5 times (go , back ,go , back ,go) ,so best solution is 1/5 and so on hope this help You should just try to think how far you are able to move with m, 2m, 3m liters of fuel. Then it'l be easy to reform the task as moving k * m liters at the distance n1. (k is integer and n1 < m) I think about DP. But i think it will not pass by time. Maybe some mathematics formules? Use DP by event (think what event in this problem is). The problem can be easily solved for more strong constraints... DP? But what's about non-integral even timing? I've spent so much time solving this problem and tried many different approaches. Finally, I've go Accepted. It's a very good problem, it develops your imagination. For those who doesn't no how to solve it there is a hint. Assume that N <= 4 / 3 * M and solve it. After that generalize your approach As I understand the jeep leaving the beginning of the road can take an infinite amount of fuel - M liters in the fuel tank and the rest in the driver's mouth. Somewhere on the way we can leave some fuel. After that we can return and take this fuel. But why can't we fill up the tank after M kilometers? We have the fuel in the driver's mouth!!! Please, anybody who understand this problem explain why I am wrong. Oh, I'm stupid. I understood the problem later. The jeep can carry only M liters. So, we can take M liters in the beginning, go on distance X, leave Y liters there and return back. So, 2 * X + Y <= M. Next time, we can take these Y liters and actually we would be able to carry M + Y liters. It's not so hard problem! This problem is classic Dynamic Programming problem, you can alg of this problem in many books(Okulov,Leyzerson,...). DP algorithm is simple just go from the end and count with equation! I do not understand a condition of a problem, Instead of her decision! Can you explain little more plz. We donot have Okulov, Leyzerson(!). Also which Classic DP you are talking about? Can anyone explain how the output is 3837 for n=1000,m=500 var m,n,t:integer; out:double; way:array[1..100]of double; oil:array[1..100]of longint; begin readln(n,m); way[1]:=m; oil[1]:=m; t:=2; while way[t-1]+m/(2*t-1)<n do begin way[t]:=way[t-1]+m/(2*t-1); oil[t]:=t*m; inc(t); end; out:=(n-way[t-1])*(2*t-1)+oil[t-1]; if abs(out-trunc(out))<1e-8 then writeln(trunc(out)) else writeln(trunc(out)+1); end. Size array take 32000!!! i.e way: array[1..32000]of double; oil: array[1..32000]of longint; Edited by author 22.12.2005 17:45 Edited by author 22.12.2005 17:45 var a,m,n:longint; d,o,w:double; begin readln(n,m); a:=0; w:=0; o:=0; repeat inc(a); d:=m/(a shl 1-1); if w+d>=n then break; w:=w+d; o:=o+m; until false; d:=n-w; o:=o+d*(a shl 1-1); writeln(round(o+0.49999999999)); end. #include<fstream.h> int main() { int n=1; float h=1.0; float s=0; long N; double M; double k=0; double d1; long d; cin>>N;cin>>M; if(M>N) {cout<<N; return 0; } k=N/M-1; for(;;n++) { s=s+h/(2*n+1); if(s>k) break; } d1=(((k-s)*(2*n+1)+1)*M+n*M); d=long(d1); if(d1-d>0) d=d+1; cout<<d; return 0; } Can anyone hint on the mathematics involved? Any links or text? Anything? My mail: asifh@agni1.net |
|