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