10261 - Ferry Loading

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

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

10261 - Ferry Loading

Post by Revenger » Wed Jun 26, 2002 1:05 pm

I have no idea why my program gets WA :( Can anyone help me?

[pascal]Program p10261;

Const MaxL = 100*100;
MaxC = 5000;
_tr = 'port';
_fa = 'starboard';

Var Inf : array[0..MaxL]of record ok,use : integer end;
Cars,Sum : array[0..MaxC]of integer;
Use : array[1..MaxC]of boolean;
i,j,L,N,ok,k : Integer;
T,TT : Integer;

begin
Read(T);
for TT:=1 to T do begin
if TT>1 then Writeln;
Read(L); L:=L*100; N:=0;
while true do begin
N:=N+1;
Read(Cars[N]);
if Cars[N]=0 then break;
end;
N:=N-1;
for i:=1 to MaxL do Inf.ok:=-1; Inf[0].ok:=0; Sum[0]:=0;
for j:=1 to N do begin
Sum[j]:=Sum[j-1]+Cars[j];
for i:=0 to L-Cars[j] do
if Inf.ok=0 then
if Inf[i+Cars[j]].ok=-1 then
if Sum[j]-i-Cars[j]<=L then begin
Inf[i+Cars[j]].ok:=0;
Inf[i+Cars[j]].use:=j;
ok:=1;
end;
end;
k:=0;
for i:=0 to L do
if Inf.ok=0 then
if Inf.use>Inf[k].use then
k:=i;
Writeln(Output,Inf[k].use);
for i:=1 to Inf[k].use do Use:=false; j:=k;
while true do begin
Use[Inf[j].use]:=true;
j:=j-Cars[Inf[j].use];
if j=0 then break;
end;
for i:=1 to Inf[k].use do
if Use then Writeln(_tr) else Writeln(_fa);
end;
end.[/pascal]

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Wed Jun 26, 2002 2:29 pm

If I understand your algorithm, you made the mistake here:
for i:=0 to L-Cars[j] do

try for i:=L-Cars[j] downto 0 do

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

Post by Revenger » Wed Jun 26, 2002 4:47 pm

I change my program, but it stil gets WA :(

[pascal]Program p10261;

Const MaxL = 100*100;
MaxC = 5000;
_tr = 'port';
_fa = 'starboard';

Var Inf : array[0..MaxL]of record ok,use : integer end;
Cars,Sum : array[0..MaxC]of integer;
Use : array[1..MaxC]of boolean;
i,j,L,N,ok,k : Integer;
T,TT : Integer;

begin
Read(T);
for TT:=1 to T do begin
if TT>1 then Writeln;
Read(L); L:=L*100; N:=0;
while true do begin
N:=N+1;
Read(Cars[N]);
if Cars[N]=0 then break;
end;
N:=N-1;
for i:=1 to MaxL do Inf.ok:=-1;
Inf[0].ok:=0; Inf[0].use:=0; Sum[0]:=0;
for j:=1 to N do begin
Sum[j]:=Sum[j-1]+Cars[j];
for i:=L-Cars[j] downto 0 do
if Inf.ok=0 then
if Inf[i+Cars[j]].ok=-1 then
if Sum[j]-i-Cars[j]<=L then begin
Inf[i+Cars[j]].ok:=0;
Inf[i+Cars[j]].use:=j;
ok:=1;
end;
end;
k:=0;
for i:=0 to L do
if Inf.ok=0 then
if Inf.use>Inf[k].use then
k:=i;
Writeln(Inf[k].use);
for i:=1 to Inf[k].use do Use:=false;
j:=k;
while true do begin
if j=0 then break;
Use[Inf[j].use]:=true;
j:=j-Cars[Inf[j].use];
end;
for i:=1 to Inf[k].use do
if Use then Writeln(_tr) else Writeln(_fa);
end;
end.[/pascal]

Kamp
New poster
Posts: 18
Joined: Tue Mar 05, 2002 2:00 am
Location: Poland (3-city)
Contact:

Post by Kamp » Wed Jun 26, 2002 6:01 pm

It's not a multiple input !!! :(

Just delete the first 3 lines after 'begin' and one 'end' at should be working :D

Also you should use 'readln' instead of 'read' :)

Good Luck !! :P

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

Post by Revenger » Wed Jun 26, 2002 6:09 pm

You are wrong. In problem says:
The Input
The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.


The first line of input contains a single integer between 1 and 100: the length of the ferry (in metres). For each car in the queue there is an additional line of input specifying the length of the car (in cm, an integer between 100 and 3000 inclusive). A final line of input contains the integer 0. The cars must be loaded in order, subject to the constraint that the total length of cars on either side does not exceed the length of the ferry. Subject to this constraint as many cars should be loaded as possible, starting with the first car in the queue and loading cars in order until no more can be loaded.

Kamp
New poster
Posts: 18
Joined: Tue Mar 05, 2002 2:00 am
Location: Poland (3-city)
Contact:

Post by Kamp » Wed Jun 26, 2002 8:00 pm

Yes, you're right :oops:

My mistake...I read the old version of the problem description :(

Sorry :)

Kamp
New poster
Posts: 18
Joined: Tue Mar 05, 2002 2:00 am
Location: Poland (3-city)
Contact:

Post by Kamp » Wed Jun 26, 2002 8:38 pm

I've tested your program on several inputs, and for data:
1

6
200
200
400
400
your program gives:
3
port
starboard
port
If I correctly understand the problem, the output should be different :(

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

Post by Revenger » Thu Jun 27, 2002 11:32 am

Thank you, but it still get WA :oops:

[pascal]Program p10261;

Const MaxL = 100*100;
MaxC = 5000;
_tr = 'port';
_fa = 'starboard';

Var Inf : array[0..MaxL]of record ok,use : integer end;
Cars,Sum : array[0..MaxC]of integer;
Use : array[1..MaxC]of boolean;
i,j,L,N,ok,k : Integer;
T,TT : Integer;

begin
Read(T);
for TT:=1 to T do begin
if TT>1 then Writeln;
Read(L); L:=L*100; N:=0;
while true do begin
N:=N+1;
Read(Cars[N]);
if Cars[N]=0 then break;
end;
N:=N-1;
for i:=1 to MaxL do Inf.ok:=-1;
Inf[0].ok:=0; Inf[0].use:=0; Sum[0]:=0;
for j:=1 to N do begin
Sum[j]:=Sum[j-1]+Cars[j];
for i:=L-Cars[j] downto 0 do
if Inf.ok=0 then
if i+Cars[j]>=Sum[j]-i-Cars[j] then begin
Inf[i+Cars[j]].ok:=0;
Inf[i+Cars[j]].use:=j;
ok:=1;
end;
end;
k:=0;
for i:=0 to L do
if Inf.ok=0 then
if Inf.use>Inf[k].use then
k:=i;
Writeln(Inf[k].use);
for i:=1 to Inf[k].use do Use:=false;
j:=k;
while true do begin
if j=0 then break;
Use[Inf[j].use]:=true;
j:=j-Cars[Inf[j].use];
end;
for i:=1 to Inf[k].use do
if Use then Writeln(_tr) else Writeln(_fa);
end;
end.[/pascal]

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

Hmm..

Post by cyfra » Thu Jun 27, 2002 11:52 am

Hmm....

You would better check your program for the input in the task description...

Because you have wrong answer for this test case !!

So try to change it :wink:

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

Post by Revenger » Thu Jun 27, 2002 12:08 pm

Many thanks to all who helped me. Now I get Accepted 8) But my program use 31 MB of memory and run about 10 sec :(

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

Post by Revenger » Thu Jun 27, 2002 12:48 pm

Wow! Now it get Accepted in 1 second usung 8 MB of memory :lol:

Kamp
New poster
Posts: 18
Joined: Tue Mar 05, 2002 2:00 am
Location: Poland (3-city)
Contact:

Post by Kamp » Thu Jun 27, 2002 1:46 pm

Waw :D

Nice time :lol:

Congratulation :wink:

henar2
New poster
Posts: 30
Joined: Mon Nov 26, 2001 2:00 am
Location: Valladolid (Spain)

10261 Ferry Loading

Post by henar2 » Thu Aug 01, 2002 2:27 pm

Hi all, I have sent the problem 10261 Ferry Loading and I am getting WA, could anyone send me or post here some inputs and outputs.
Thanks in advance.

Alfredo Guti

Rivaldo
New poster
Posts: 19
Joined: Sun Jul 07, 2002 3:59 pm

Post by Rivaldo » Wed Aug 07, 2002 4:43 pm

I also got WA. So i want to know whether i should keep abs(portlen - starboardlen) is minimal. Can anyone who got AC tell me that?

obayashi
New poster
Posts: 33
Joined: Thu Jun 20, 2002 1:18 pm

Post by obayashi » Sat Aug 17, 2002 12:59 pm

it's just a knap-sack like problem.
think it over and u will find what to do with this problem:)

good luck~
Time makes a fool of memory
And yet my memories still shine

Post Reply

Return to “Volume 102 (10200-10299)”