Show all threads Hide all threads Show all messages Hide all messages |
Literature in Russian | Andrewy | 1113. Jeep | 7 Aug 2019 19:27 | 1 |
Методы Программирования и Прикладные Алгоритмы |
To admins AC and wrong answer | WhiteMan | 1113. Jeep | 10 Sep 2014 13:19 | 1 |
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 |
HELP!!! Time limit exceeded 0.531sec | Chukharev | 1113. Jeep | 21 Jun 2014 02:27 | 2 |
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 |
accepted C/C++ | Sunnat | 1113. Jeep | 23 Oct 2012 00:04 | 1 |
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); |
Tell me how solve this problem | Turdubek | 1113. Jeep | 27 Jan 2011 16:39 | 2 |
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. |
Help me | Turdubek | 1113. Jeep | 25 Jan 2011 19:21 | 1 |
Anyone help me to understand or solve this problem.I didn't understand how comes the answer 3837 |
Shortest AC program: if(m<=2)f=n;else for(f=m;n-->m;f+=(f-m)/(m-2)*2+3); Can anybody do better? | Marko Tintor (marko@pkj.co.yu) | 1113. Jeep | 30 Aug 2009 17:57 | 5 |
Man you have compilation error :) Can anybody tell how to deduce this solution? |
Please C++ help... | Crash_access_violation | 1113. Jeep | 24 Aug 2009 22:50 | 1 |
[code deleted] Edited by author 26.08.2009 15:35 |
Very good problem | Imran Yusubov | 1113. Jeep | 13 Aug 2009 18:06 | 1 |
|
Very good problem | Imran Yusubov | 1113. Jeep | 13 Aug 2009 18:06 | 1 |
|
Where is mistake? | Drema [KhAI] Tihov Ilya | 1113. Jeep | 11 Jun 2009 14:20 | 1 |
#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;
} |
Explanation | Denis | 1113. Jeep | 30 Apr 2009 22:51 | 6 |
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) |
too easy.....Here's my ACP. | HandsomeG | 1113. Jeep | 10 Feb 2009 01:42 | 3 |
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. |
How to solve? | Piratek-(akaDK) | 1113. Jeep | 24 Jul 2008 18:27 | 3 |
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? |
Very good problem | VC15 (Orel STU) | 1113. Jeep | 11 Sep 2007 02:48 | 2 |
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 |
Strange problem description | VC15 (Orel STU) | 1113. Jeep | 23 Aug 2007 00:44 | 2 |
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. |
Why Crash???????? | kkkkk | 1113. Jeep | 22 Dec 2005 17:45 | 3 |
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 |
i did not anderstend this problem. Help me// PLEASE\\ | Виктор Крупко | 1113. Jeep | 17 Jul 2005 02:27 | 5 |
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 |
help !!!why wrong answer? | gwc_chin | 1113. Jeep | 16 Apr 2003 18:56 | 1 |
#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?(+) | asif | 1113. Jeep | 17 Jan 2003 22:25 | 1 |
Can anyone hint on the mathematics involved? Any links or text? Anything? My mail: asifh@agni1.net |