10201 - Adventures in Moving - Part IV

All about problems in Volume 102. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Amin Md Nurul
New poster
Posts: 1
Joined: Sun Oct 14, 2001 2:00 am
Location: Bangladesh
Contact:

10201

Post by Amin Md Nurul » Tue Nov 06, 2001 1:54 am

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
New poster
Posts: 1
Joined: Sun Oct 14, 2001 2:00 am
Location: Bangladesh

Post by Runner » Sat Nov 17, 2001 6:36 am

Hi,

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

dh3014
New poster
Posts: 24
Joined: Tue Mar 26, 2002 2:00 am
Location: Taiwan
Contact:

10201 - Adventures in Moving - Part IV

Post by dh3014 » Sun Mar 31, 2002 4:48 pm

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

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Sun Mar 31, 2002 7:18 pm

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
New poster
Posts: 24
Joined: Tue Mar 26, 2002 2:00 am
Location: Taiwan
Contact:

Post by dh3014 » Mon Apr 01, 2002 4:57 pm

Quite appreciate.
According your output.
I got AC.

Even
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan

10201...@@

Post by Even » Sun Aug 04, 2002 8:52 pm

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
New poster
Posts: 9
Joined: Sat Oct 26, 2002 6:30 pm

Post by Jucovschi Constantin » Fri Jan 10, 2003 7:30 pm

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
New poster
Posts: 11
Joined: Sun Jan 26, 2003 4:25 pm
Contact:

Post by newhh2002 » Sat Feb 01, 2003 7:30 am

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
none

Shahriar Nirjon
New poster
Posts: 16
Joined: Tue Dec 03, 2002 9:44 pm

Input Clarification

Post by Shahriar Nirjon » Mon Feb 10, 2003 11:14 pm

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

:o

[/quote]

davor
New poster
Posts: 8
Joined: Sat Jun 28, 2003 11:04 pm

10201 Accepted P.E.

Post by davor » Thu Aug 28, 2003 6:47 pm

[/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.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. » Thu Aug 28, 2003 7:17 pm

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.
JongMan @ Yonsei

davor
New poster
Posts: 8
Joined: Sat Jun 28, 2003 11:04 pm

Post by davor » Sun Aug 31, 2003 11:08 am

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

User avatar
abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

Post by abishek » Thu Aug 26, 2004 1:24 am

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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Thu Aug 26, 2004 1:48 am

Use greedy.

ranjit
New poster
Posts: 34
Joined: Fri Jan 30, 2004 11:22 am
Location: india

hi

Post by ranjit » Fri Jan 28, 2005 8:49 pm

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.

Post Reply

Return to “Volume 102 (10200-10299)”