| ENG RUS | Timus Online Judge |
Обсуждение задачи 1113. ДжипAndrewy Literature in Russian // Задача 1113. Джип 7 авг 2019 19:27 Методы Программирования и Прикладные Алгоритмы WhiteMan To admins AC and wrong answer // Задача 1113. Джип 10 сен 2014 13:19 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 Chukharev HELP!!! Time limit exceeded 0.531sec [1] // Задача 1113. Джип 20 июн 2014 21:33 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 Chukharev No subject // Задача 1113. Джип 21 июн 2014 02:27 Edited by author 21.06.2014 21:27 Sunnat accepted C/C++ // Задача 1113. Джип 23 окт 2012 00:04 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); Turdubek Tell me how solve this problem [1] // Задача 1113. Джип 25 янв 2011 19:24 Alexander Fedulin Re: Tell me how solve this problem // Задача 1113. Джип 27 янв 2011 16:39 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. Turdubek Help me // Задача 1113. Джип 25 янв 2011 19:21 Anyone help me to understand or solve this problem.I didn't understand how comes the answer 3837 Marko Tintor (marko@pkj.co.yu) 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? [4] // Задача 1113. Джип 21 июл 2002 21:06 hawking now it cannot got AC? // Задача 1113. Джип 26 сен 2002 10:59 > PSV Re: 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? [1] // Задача 1113. Джип 5 ноя 2006 21:39 Man you have compilation error :) [SPbSU ITMO] WiNGeR Re: 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? // Задача 1113. Джип 6 ноя 2006 21:33 Can anybody tell how to deduce this solution? Amir Hessam Moltaji No subject // Задача 1113. Джип 30 авг 2009 17:57 It is a wrong solution Crash_access_violation Please C++ help... // Задача 1113. Джип 24 авг 2009 22:50 [code deleted] Edited by author 26.08.2009 15:35 Imran Yusubov Very good problem // Задача 1113. Джип 13 авг 2009 18:06 Just Sum of 1+1/3+1/5+...1/2n+1 see http://en.wikipedia.org/wiki/Jeep_problem Edited by author 13.08.2009 18:07 Imran Yusubov Very good problem // Задача 1113. Джип 13 авг 2009 18:06 Drema [KhAI] Tihov Ilya Where is mistake? // Задача 1113. Джип 11 июн 2009 14:20 #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; } Denis Explanation [5] // Задача 1113. Джип 21 янв 2008 02:41 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 ??? Denis Koshman Re: Explanation // Задача 1113. Джип 24 июл 2008 19:55 I'd like to know as well... elmariachi1414 (TNU) Re: Explanation [1] // Задача 1113. Джип 25 июл 2008 00:57 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! Nikola Yolov Re: Explanation // Задача 1113. Джип 30 апр 2009 22:51 Thank you for the explanation, everything is clear now. Seraphy Re: Explanation [1] // Задача 1113. Джип 16 авг 2008 21:46 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 Dmitry "Logam" Kobelev [TSOGU] Re: Explanation // Задача 1113. Джип 30 янв 2009 11:30 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) HandsomeG too easy.....Here's my ACP. [2] // Задача 1113. Джип 23 июл 2003 08:15 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. Denis Koshman Re: too easy.....Here's my ACP. // Задача 1113. Джип 24 июл 2008 19:53 Thanks! Helped a lot :) Fyodor Menshikov Re: too easy.....Here's my ACP. // Задача 1113. Джип 10 фев 2009 01:42 Thanks! :-) Piratek-(akaDK) How to solve? [2] // Задача 1113. Джип 20 сен 2007 22:28 I think about DP. But i think it will not pass by time. Maybe some mathematics formules? Vedernikoff Sergey Re: How to solve? [1] // Задача 1113. Джип 21 сен 2007 04:31 Use DP by event (think what event in this problem is). The problem can be easily solved for more strong constraints... Denis Koshman Re: How to solve? // Задача 1113. Джип 24 июл 2008 18:27 DP? But what's about non-integral even timing? VC15 (Orel STU) Very good problem [1] // Задача 1113. Джип 11 сен 2007 00:11 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 Vedernikoff Sergey Re: Very good problem // Задача 1113. Джип 11 сен 2007 02:48 I agree... VC15 (Orel STU) Strange problem description [1] // Задача 1113. Джип 22 авг 2007 19:29 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. VC15 (Orel STU) Re: Strange problem description // Задача 1113. Джип 23 авг 2007 00:44 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. kkkkk Why Crash???????? [2] // Задача 1113. Джип 23 окт 2004 19:24 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. Michael Rybak (accepted@ukr.net) Enlarge your arrays. Why 100? (-) // Задача 1113. Джип 27 окт 2004 17:06 xurshid_n Re: Why Crash???????? // Задача 1113. Джип 22 дек 2005 17:45 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\\ [4] // Задача 1113. Джип 26 апр 2005 00:50 Akshin Salimov It's not so hard [3] // Задача 1113. Джип 26 апр 2005 19:14 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! Виктор Крупко Re: It's not so hard // Задача 1113. Джип 26 апр 2005 22:57 I do not understand a condition of a problem, Instead of her decision! Nirjon Re: It's not so hard [1] // Задача 1113. Джип 14 июл 2005 14:38 Can you explain little more plz. We donot have Okulov, Leyzerson(!). Also which Classic DP you are talking about? Nirjon Re: It's not so hard // Задача 1113. Джип 17 июл 2005 02:27 Can anyone explain how the output is 3837 for n=1000,m=500 gwc_chin help !!!why wrong answer? // Задача 1113. Джип 16 апр 2003 18:56 #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; } asif Can anyone hint on the mathematics involved?(+) // Задача 1113. Джип 17 янв 2003 22:25 Can anyone hint on the mathematics involved? Any links or text? Anything? My mail: asifh@agni1.net
|