10261  Ferry Loading
Moderator: Board moderators

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
10261
I got WA many time. I checked my program using the data I found in http://plg.uwaterloo.ca/~acm00/, and it was right.
Who can tell my program's bug? Thanks.
[pascal]
const
maxn = 10010;
var
f,g : array[0 .. maxn] of boolean;
pre : array[0 .. maxn] of integer;
w : array[1 .. 210] of integer;
sol : array[1 .. 210] of boolean;
m,k,n : integer;
procedure init;
var j,s : integer;
begin
readln(k);
n := 0; s := 0;
readln(j); k := k * 100;
while j <> 0 do begin
inc(s, j);
if s <= k + k then begin
inc(n);
w[n] := j;
end;
readln(j);
end;
end;
procedure main;
var i,j,s,r : integer;
more : boolean;
begin
if n = 0 then begin
writeln(0);
exit;
end;
fillchar(g, sizeof(g), false);
fillchar(pre, sizeof(pre), 0);
g[0] := true; s := 0;
for i := 1 to n do begin
s := s + w; more := false;
fillchar(f, sizeof(f), 0);
for j := k downto 0 do
if g[j] then begin
if s  j <= k then begin
f[j] := true; more := true;
end;
if j + w <= k then begin
f[j + w] := true;
pre[j + w] := i;
more := true;
end;
end;
if not more then break;
g := f;
end;
if not more then i := i  1;
writeln(i);
r := 0;
for j := 0 to maxn do
if g[j] and (abs(s  j  j) < abs(s  r  r)) then r := j;
fillchar(sol, sizeof(sol), false);
while r <> 0 do begin
sol[pre[r]] := true;
r := r  w[pre[r]];
end;
for j := 1 to i do
if sol[j] then writeln('port')
else writeln('starboard');
end;
begin
readln(m);
while m > 0 do begin
dec(m);
init;
main;
writeln;
end;
end.
[/pascal]
Who can tell my program's bug? Thanks.
[pascal]
const
maxn = 10010;
var
f,g : array[0 .. maxn] of boolean;
pre : array[0 .. maxn] of integer;
w : array[1 .. 210] of integer;
sol : array[1 .. 210] of boolean;
m,k,n : integer;
procedure init;
var j,s : integer;
begin
readln(k);
n := 0; s := 0;
readln(j); k := k * 100;
while j <> 0 do begin
inc(s, j);
if s <= k + k then begin
inc(n);
w[n] := j;
end;
readln(j);
end;
end;
procedure main;
var i,j,s,r : integer;
more : boolean;
begin
if n = 0 then begin
writeln(0);
exit;
end;
fillchar(g, sizeof(g), false);
fillchar(pre, sizeof(pre), 0);
g[0] := true; s := 0;
for i := 1 to n do begin
s := s + w; more := false;
fillchar(f, sizeof(f), 0);
for j := k downto 0 do
if g[j] then begin
if s  j <= k then begin
f[j] := true; more := true;
end;
if j + w <= k then begin
f[j + w] := true;
pre[j + w] := i;
more := true;
end;
end;
if not more then break;
g := f;
end;
if not more then i := i  1;
writeln(i);
r := 0;
for j := 0 to maxn do
if g[j] and (abs(s  j  j) < abs(s  r  r)) then r := j;
fillchar(sol, sizeof(sol), false);
while r <> 0 do begin
sol[pre[r]] := true;
r := r  w[pre[r]];
end;
for j := 1 to i do
if sol[j] then writeln('port')
else writeln('starboard');
end;
begin
readln(m);
while m > 0 do begin
dec(m);
init;
main;
writeln;
end;
end.
[/pascal]
got RTE
I got Runtime Error (SIGSEGV) with my program. Please help me to find the bug.
[c]#include <stdio.h>
#define MAXN 201
#define MAXL 10001
int length[MAXN];
int knapsack(int itemsTaken[][MAXL], int n, int maxL)
{
int i, j;
int C[MAXN][MAXL];
for(i=0; i<=n; i++)
for(j=0; j<=maxL; j++)
itemsTaken[j] = 0;
for(i=0; i<=n; i++) C[0] = 0;
for(j=0; j<=maxL; j++) C[0][j] = 0;
for(i=1; i<=n; i++)
for(j=1; j<=maxL; j++)
{
if(length > j) C[j] = C[i1][j];
else
{
if(C[i1][j] >= C[i1][jlength]+length)
{
C[j] = C[i1][j];
itemsTaken[j] = itemsTaken[i1][j];
}
else
{
C[j] = C[i1][jlength]+length[i];
itemsTaken[i][j] = i;
}
}
}
return (C[n][maxL]);
}
void main()
{
int kase, I;
int maxLenOfFerry, total, limit, count;
int newleft, newright;
int used[MAXN];
int i, temp, flag;
int itemsTaken[MAXN][MAXL];
scanf("%d", &kase);
for(I=0; I<kase; I++)
{
if(I) printf("\n");
scanf("%d", &maxLenOfFerry);
maxLenOfFerry *= 200;
limit = maxLenOfFerry / 2;
newleft = newright = 0;
flag = 1;
length[0] = 0;
for(i=1, total=0, count=0; ; )
{
scanf("%d", &length[i]);
if(length[i]==0) break;
if(flag) total += length[i];
if(total <= maxLenOfFerry && newright <= limit && (newright+newleft+length[i])<=maxLenOfFerry)
{
newleft = knapsack(itemsTaken, i, limit);
newright = total  newleft;
if(newright <= limit)
count++;
i++;
}
else flag = 0;
}
for(i=0; i<=count; i++) used[i] = 0;
temp = count;
while(itemsTaken[count][limit])
{
used[itemsTaken[count][limit]] = 1;
limit = limitlength[itemsTaken[count][limit]];
count;
}
count = temp;
printf("%d\n", count);
for(i=1; i<=count; i++)
{
if(used[i]) printf("starbord\n");
else printf("port\n");
}
}
}[/c]
[c]#include <stdio.h>
#define MAXN 201
#define MAXL 10001
int length[MAXN];
int knapsack(int itemsTaken[][MAXL], int n, int maxL)
{
int i, j;
int C[MAXN][MAXL];
for(i=0; i<=n; i++)
for(j=0; j<=maxL; j++)
itemsTaken[j] = 0;
for(i=0; i<=n; i++) C[0] = 0;
for(j=0; j<=maxL; j++) C[0][j] = 0;
for(i=1; i<=n; i++)
for(j=1; j<=maxL; j++)
{
if(length > j) C[j] = C[i1][j];
else
{
if(C[i1][j] >= C[i1][jlength]+length)
{
C[j] = C[i1][j];
itemsTaken[j] = itemsTaken[i1][j];
}
else
{
C[j] = C[i1][jlength]+length[i];
itemsTaken[i][j] = i;
}
}
}
return (C[n][maxL]);
}
void main()
{
int kase, I;
int maxLenOfFerry, total, limit, count;
int newleft, newright;
int used[MAXN];
int i, temp, flag;
int itemsTaken[MAXN][MAXL];
scanf("%d", &kase);
for(I=0; I<kase; I++)
{
if(I) printf("\n");
scanf("%d", &maxLenOfFerry);
maxLenOfFerry *= 200;
limit = maxLenOfFerry / 2;
newleft = newright = 0;
flag = 1;
length[0] = 0;
for(i=1, total=0, count=0; ; )
{
scanf("%d", &length[i]);
if(length[i]==0) break;
if(flag) total += length[i];
if(total <= maxLenOfFerry && newright <= limit && (newright+newleft+length[i])<=maxLenOfFerry)
{
newleft = knapsack(itemsTaken, i, limit);
newright = total  newleft;
if(newright <= limit)
count++;
i++;
}
else flag = 0;
}
for(i=0; i<=count; i++) used[i] = 0;
temp = count;
while(itemsTaken[count][limit])
{
used[itemsTaken[count][limit]] = 1;
limit = limitlength[itemsTaken[count][limit]];
count;
}
count = temp;
printf("%d\n", count);
for(i=1; i<=count; i++)
{
if(used[i]) printf("starbord\n");
else printf("port\n");
}
}
}[/c]

 New poster
 Posts: 1
 Joined: Sun Sep 19, 2004 2:31 pm
10261 (Ferry loading problem) strange WAs...
Hello.
I coded my solution but it gets WA.
Fortunately, I've got an accepted solution from somewhere.
So I wrote a program which solves the problem twice  once by my method and once by the accepted method  and prints the results of the accepted method.
I inserted into this program some code which generates a SIGFPE when the maximum numbers of the cars computed by the two methods are different.
It also generates the signal when my method produces an infeasible solution, where the total length of the cars on one side of the ferry(port or starboard) is greater than the length of the ferry.
I submitted this program.
It's accepted because it prints the results by the accepted method and it never results in a SIGFPE.
That means my method calculates the correct maximum number of the cars.
And the total length of the cars on each side is less than or equal to the length of the ferry.
But strangely, my own program gets WAs. I wonder if the judge program is not flexible enough to check correctly?
Please give me some ideas..
I coded my solution but it gets WA.
Fortunately, I've got an accepted solution from somewhere.
So I wrote a program which solves the problem twice  once by my method and once by the accepted method  and prints the results of the accepted method.
I inserted into this program some code which generates a SIGFPE when the maximum numbers of the cars computed by the two methods are different.
It also generates the signal when my method produces an infeasible solution, where the total length of the cars on one side of the ferry(port or starboard) is greater than the length of the ferry.
I submitted this program.
It's accepted because it prints the results by the accepted method and it never results in a SIGFPE.
That means my method calculates the correct maximum number of the cars.
And the total length of the cars on each side is less than or equal to the length of the ferry.
But strangely, my own program gets WAs. I wonder if the judge program is not flexible enough to check correctly?
Please give me some ideas..
10261 ferry loading again...
Could someone leak a hint for this problem(and I plead for more than that it's a knapsack like problem)? I've been trying and leaving this problem for no less than a year now(shame, but true...). Thanks...

 New poster
 Posts: 30
 Joined: Sat Nov 30, 2002 1:04 pm
Exhaustive search.....???!!! The input is definitely weak then, as with the given constraints, I believe one could have 100 cars in the queue, and 2^100 is not something to play with..
I still wish somebody would advise how DP would be used here...Like I mentioned before, I tried for a year now...
Anyways, thanks mr Csaba...
I still wish somebody would advise how DP would be used here...Like I mentioned before, I tried for a year now...
Anyways, thanks mr Csaba...
is there any greedy approach
is there any greedy solution to the problem. I see some zero memory and time solutions
10261  DP problem
I have beein trying this one.
I found out that:
read a new car
 if i cant add any previous cars, dont try this one
 i can either add the car to the left or to the right, so try it by doing:
for(i=tam;i>=0;i) if this position is checked THEN
if i can add it at position i (which means to the left), i try doing so
if i can not add it to the right, uncheck this position
if i unchecked all positions and did not check any one i was not able to add this car.... time to stop trying
The code follows, any tips? (ps: wrong answer)
I found out that:
read a new car
 if i cant add any previous cars, dont try this one
 i can either add the car to the left or to the right, so try it by doing:
for(i=tam;i>=0;i) if this position is checked THEN
if i can add it at position i (which means to the left), i try doing so
if i can not add it to the right, uncheck this position
if i unchecked all positions and did not check any one i was not able to add this car.... time to stop trying
The code follows, any tips? (ps: wrong answer)
Code: Select all
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <stdio.h>
#define FOR(a,b) for(a=0;a<b;a++)
#define REP(a,b) for(int a=0;a<b;a++)
using namespace std;
char d[1000];
int le() {
int v;
cin >> v;
return v;
}
int fer[30000],pre[30000],ult[30000];
void st() {
int tam = le() * 100;
int v;
int i,j,k = 0;
FOR(i,tam+100) fer[i] = ult[i] = 0;
FOR(i,tam+100) pre[i] = 1;
fer[0] = 1;
int total = 0;
bool parei = 0;
//cout << "comec" << endl;
while((v=le())!=0) {
if(parei) continue; // se parou, ignora esse
k++; // estamos no kesimo
bool cabe = 0;
for(i=tam;i>=0;i) {
// se nao ativado ignora
if(!(fer[i])) continue;
// se cabe na esquerda, tenta la
if(i+v<=tam && !ult[i+v]) {
fer[i+v] = 1;
ult[i+v] = k;
cabe = 1;
pre[i+v] = i;
}
// se nao cabe na direita, tira daqui
if((totali)+v>tam) {
fer[i] = 0;
} else {
cabe = 1;
}
}
// se coube em algum lugar.... ok
if(cabe) {
total += v;
//cout << "ad o " << k << endl;
} else {
k;
parei = 1;
}
}
// sai imprimindo
/*FOR(i,tam+1) cout << fer[i] << " ";
cout << endl;
FOR(i,tam+1) cout << pre[i] << " ";
cout << endl;
FOR(i,tam+1) cout << ult[i] << " ";
cout << endl;*/
// procura o k na lista
FOR(i, tam+1) if(ult[i]==k) break;
vector<int> li;
// agora roda o iterativo
while(i!=0) {
li.push_back(ult[i]);
i = pre[i];
}
cout << k << endl;
for(i=1;i<=k;i++) {
if(find(li.begin(),li.end(),i)!=li.end()) cout << "port" << endl;
else cout << "starboard" << endl;
}
}
int main() {
int t = le();
while(t) {
st();
if(t) cout << endl;
}
return 0;
}

 A great helper
 Posts: 281
 Joined: Tue Sep 10, 2002 5:14 am
 Location: Mountain View, CA, USA
 Contact:
Is this answer to the sample input correct?
I think it is, but how would the special judge test that?
Code: Select all
6
port
starboard
port
port
starboard
starboard
If only I had as much free time as I did in college...

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm