Page 1 of 2
10201
Posted: Tue Nov 06, 2001 1:54 am
by Amin Md Nurul
Its accepted in contest but not right now. May be the reason is multiple input
technique. But it is ambiguious.
With respect may be judge make any mistake when making input set as multiple. Pls judge
check it out again.
Because the same problem cames in waterloo local contest & still my code sirvive.
How I take the input
First read test case;
then a blank;
start a destination distance;
then given multiple or single gas station
distance and cost.
I stop this multiple gas station distance & cost input when get a blank line.
Then again comes to take start destination
distance input.
may be the input file looks like
3
400
100 200
200 300
300 400
500
100 200
200 300
500
100 1
<font size=-1>[ This Message was edited by: Amin Md Nurul on 2001-11-06 00:58 ]</font>
Posted: Sat Nov 17, 2001 6:36 am
by Runner
Hi,
I agree................
10201 - Adventures in Moving - Part IV
Posted: Sun Mar 31, 2002 4:48 pm
by dh3014
What should be the correct output for following input?
Or anyone knows any tricks in this problem?
-----
4
500
100 1
300 1
350 1
501 10
101
100 100
102 1
100
101
Posted: Sun Mar 31, 2002 7:18 pm
by ..
the output is:
950
299
Impossible
Impossible
and you can try these input:
200
100 10
201
100 10
201
101 10
50
25 10
Posted: Mon Apr 01, 2002 4:57 pm
by dh3014
Quite appreciate.
According your output.
I got AC.
10201...@@
Posted: Sun Aug 04, 2002 8:52 pm
by Even
Input
2
150
100 10
151 20
150
100 10
151 20
152 1
please tell me the output...
and I can't understand ..
why
500
100 1
300 1
350 1
501 10
the answer is 950 ... not 970 ??
when I arrive in (501), I needn't go back to (500) ??
please tell me...thank you
Posted: Fri Jan 10, 2003 7:30 pm
by Jucovschi Constantin
I think Even is right for the following inputs
Code: Select all
10
500
100 1
300 1
350 1
501 10
101
100 100
102 1
100
101
200
100 10
201
100 10
201
101 10
50
25 10
150
100 10
151 20
150
100 10
151 20
152 1
I get the results
Code: Select all
970
301
Impossible
Impossible
2000
Impossible
Impossible
500
1500
622
Am I right ? I get WA ?
Posted: Sat Feb 01, 2003 7:30 am
by newhh2002
Jucovschi Constantin wrote:I think Even is right for the following inputs
Code: Select all
10
500
100 1
300 1
350 1
501 10
101
100 100
102 1
100
101
200
100 10
201
100 10
201
101 10
50
25 10
150
100 10
151 20
150
100 10
151 20
152 1
I get the results
Code: Select all
970
301
Impossible
Impossible
2000
Impossible
Impossible
500
1500
622
Am I right ? I get WA ?
sorry i'm afraid you are not right, my results are:
Code: Select all
950
299
Impossible
Impossible
2000
Impossible
Impossible
500
1500
618
Input Clarification
Posted: Mon Feb 10, 2003 11:14 pm
by Shahriar Nirjon
<^7
HI,
I have got AC.
I only considered those stations which are <= target.
Jucovschi Constantin/ newhh2002 or even Even thinks of a
variety of inputs. You also go for 950/970 ... like outputs. But
Judge data does not have those.
More interesting, My AC code gives another output for those 10
Inputs.My output --
(Output for 'impossible' test cases)
Impossible
10100
Impossible
Impossible
2000
Impossible
Impossible
500
1500
1500
So, feel free to setup extra station(s) or discard excess ones.
[/quote]
10201 Accepted P.E.
Posted: Thu Aug 28, 2003 6:47 pm
by davor
[/quote] I don't understand why my code gives Presentation Error. Can anyone tell me?
Code: Select all
var m,i,j,k,n,u,v,l:longint;
s:string[200];
a:array[0..100,0..300] of longint;
b:array[0..100,1..2] of integer;
begin
read(u);
for v:=1 to u do begin
for i:=0 to 100 do for j:=0 to 300 do a[i,j]:=2000000000;
s:='';
for i:=0 to 100 do begin
b[i,1]:=0; b[i,2]:=0;
end;
i:=0; j:=0; k:=0; n:=0; l:=0; m:=0;
readln(n);
readln(s);
i:=0;
while s<>'' do begin
i:=i+1;
j:=1; k:=0;
while s[j]<>' ' do begin
k:=k*10+ord(s[j])-48;
j:=j+1;
end;
b[i,1]:=k; k:=0; j:=j+1;
while (j<=ord(s[0])) do begin
k:=k*10+ord(s[j])-48;
j:=j+1;
end;
b[i,2]:=k;
readln(s);
end;
m:=i;
if (b[1,1]<=100) and (m>0) then begin
for i:=m downto 1 do begin
if (b[i,1]=b[i-1,1]) and (b[i,2]<b[i-1,2]) then begin
k:=b[i,2]; b[i,2]:=b[i-1,2]; b[i-1,2]:=k;
end;
end;
for i:=(100-b[1,1]) to 200 do begin
a[1,i]:=(i-(100-b[1,1]))*b[1,2];
end;
for i:=2 to m do begin
if b[i,1]-b[i-1,1]>200 then break;
for j:=0 to 200 do begin
if (b[i,1]-b[i-1,1]+j)>200 then begin
k:=a[i-1,200]+(b[i,1]-b[i-1,1]+j-200)*b[i,2];
end
else k:=a[i-1,b[i,1]-b[i-1,1]+j];
l:=a[i-1,b[i,1]-b[i-1,1]]+j*b[i,2];
if k<l then a[i,j]:=k else a[i,j]:=l;
end;
end;
k:=n-b[m,1];
if a[m,100+k]=2000000000 then writeln('Impossible') else writeln(a[m,100+k]);
writeln;
end else writeln('Impossible');
end;
end.
[/pascal][pascal][/pascal]
Posted: Thu Aug 28, 2003 7:17 pm
by Whinii F.
It's because you don't insert blank lines correctly, that the answers for different test cases should be seperated by a blank line. That means the first and last line of output will not be blank.
Posted: Sun Aug 31, 2003 11:08 am
by davor
Thanks. I got Accepted now. I always forgot about those blank lines
Posted: Thu Aug 26, 2004 1:24 am
by abishek
I use the following algorithm and get WA.
can anyone help?
Code: Select all
1. For each station I store the minimum cost with which i can reach that station with a fuel of
0---->200
2. Then i print the output is mincost[100] at the final destination.
3. If it is not possible to reach any of the intermediate stations or if it is not possible to reach the destination with a fuel 100 i print -1.
Note: i don't consider any stations beyond the destination. However I think that complicates the matters also.
for example
--- dest (reachable with fuel 20) --- dist 10 --- (fuel cost 1000000000) --- dist 10 (fuel cost 1)
clearly we must skip this fuel station and then filll in the next fuel station.
also in the input it says that
all the gas stations along your route,
-----------------------^^^^^^^^^^^^^^^^^
so i think that we must not consider later gas stations. can any one point me something wrong in my algorithm? or should i think more about considering cases where stations may be away from the destination as well.
bye
abi
Posted: Thu Aug 26, 2004 1:48 am
by Larry
Use greedy.
hi
Posted: Fri Jan 28, 2005 8:49 pm
by ranjit
hi abishek,
from your description of the solution,it is not clear whether you ensure that at the destination
the truck has fuel > 100 litres.
Also, print Impossible not -1.