10201 - Adventures in Moving - Part IV

[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>

[Runner]

Hi,

I agree................

[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

[..]

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

[dh3014]

Quite appreciate.
According your output.
I got AC.

[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

[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 ?

[newhh2002]

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

[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]

[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]

[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.

[davor]

Thanks. I got Accepted now. I always forgot about those blank lines

[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

[Larry]

Use greedy.

[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.