## 11935 - Through the Desert

Moderator: Board moderators

### 11935 - Through the Desert

Hello,

Problem looks simple, but I got WA.

Could anyone tell me about traps in this problem ?

What should be an output for this test case ?
Code: Select all
`0 Fuel consumption 10 Fuel consumption 01 Leak1 Leak6 Goal`

?? My code outputs "10". Maybe it should be "0" ??

Maybe this problem has rounding error ??

Best regards
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)
Dominik Michniewski
Guru

Posts: 828
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland

### Re: 11935 - Through the Desert

My AC program outputs 10.000
Did you print 3 digits after the decimal point?

...and welcome back

sohel
Guru

Posts: 862
Joined: Thu Jan 30, 2003 5:50 am
Location: University of Texas at San Antonio

### Re: 11935 - Through the Desert

Yes, I output always number with three digits after decimal point.

Algorithm is simply:
when I read another event on the road, I calculate fuel consumed between current and last event:
Code: Select all
`actFuel += (actKm - lastKm)*(actFuelConsumpton/100.0 + actLeakNo)`

After that I manage action connected to particular event and read another one until I reach Goal event.
Every gas station on the road is special - I check if between start (or another gas station) car used more fuel than in maximal case - if I exceed computed erlier maximum I remember it.
If I reach goal I output found maximum.

I tried to post to versions of code:
1) in the first I used directly formula specified above (WA)
2) in the second I used only integer calculations (formula is a bit different to correct handle decimal and fractional parts) (WA)

It's nice that somebody remembered me :)
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)
Dominik Michniewski
Guru

Posts: 828
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland

### Re: 11935 - Through the Desert

I did exactly what you did in the first version. The only thing you didn't name was to check the fuel used between the start (or last gas station) and the goal. Other than that, I don't see any difference. Maybe add some epsilon when you print the result.
lgarcia
New poster

Posts: 16
Joined: Mon Sep 14, 2009 7:49 pm
Location: Venezuela

### Re: 11935 - Through the Desert

I tried to add epsilon value to result, but without success.
I wrote also different version of code, in which I avoid using doubles - without success too.
I probably test all cases (start->goal, start->gas station, gas station->gas station, gas station -> goal) which can lead to find minimum value for fuel tank.

Below is my code:
Code: Select all
`Code removed after Acc`

Maybe someone see my error or give me example on which I fail I have no idea what I can do wrong
Last edited by Dominik Michniewski on Wed Mar 09, 2011 2:56 pm, edited 1 time in total.
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)
Dominik Michniewski
Guru

Posts: 828
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland

### Re: 11935 - Through the Desert

Change "long int" to "int" and you will got AC.
lgarcia
New poster

Posts: 16
Joined: Mon Sep 14, 2009 7:49 pm
Location: Venezuela

### Re: 11935 - Through the Desert

What a stupid mistake :/
I changed %d into %ld in my code and I got Accepted.
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)
Dominik Michniewski
Guru

Posts: 828
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland

### Re: 11935 - Through the Desert

It happens
lgarcia
New poster

Posts: 16
Joined: Mon Sep 14, 2009 7:49 pm
Location: Venezuela

### Re: 11935 - Through the Desert

SImple Binary Search:
For 300 iterations:
[
volume=(high+low)/2.0
ret=simulate(volume)
if(ret==NOT ENOUGH) low=volume
]
Shafaet_du
Experienced poster

Posts: 147
Joined: Mon Jun 07, 2010 11:43 am

### Re: 11935 - Through the Desert

Getting WA !!!
please give me some sample input and output....

Code: Select all
`Thanks brianfry713.... I have got this problem the magical word "Accepted" .... :)`
Last edited by Mukit Chowdhury on Wed Oct 31, 2012 8:05 am, edited 1 time in total.
Mukit Chowdhury
Learning poster

Posts: 59
Joined: Fri Aug 17, 2012 9:23 pm
Location: CUET

### Re: 11935 - Through the Desert

Input:
Code: Select all
`0 Fuel consumption 1050 Gas station50 Fuel consumption 20100 Goal0 Fuel consumption 2050 Gas station50 Fuel consumption 10100 Goal`
AC output:
Code: Select all
`10.00010.000`
brianfry713
Guru

Posts: 1771
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA