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

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

Post by Adrian Kuegel »

Rivaldo, you should load as many cars as possible.

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


Post by Rivaldo »

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.
maxn = 10010;
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;
n := 0; s := 0;
readln(j); k := k * 100;
while j <> 0 do begin
inc(s, j);
if s <= k + k then begin
w[n] := j;

procedure main;
var i,j,s,r : integer;
more : boolean;
if n = 0 then begin
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;
if j + w <= k then begin
f[j + w] := true;
pre[j + w] := i;
more := true;
if not more then break;
g := f;

if not more then i := i - 1;
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]];
for j := 1 to i do
if sol[j] then writeln('port')
else writeln('starboard');

while m > 0 do begin

Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh

got RTE

Post by Subeen »

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[i-1][j];
if(C[i-1][j] >= C[i-1][j-length]+length)
C[j] = C[i-1][j];
itemsTaken[j] = itemsTaken[i-1][j];
C[j] = C[i-1][j-length]+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)
else flag = 0;
for(i=0; i<=count; i++) used[i] = 0;
temp = count;

used[itemsTaken[count][limit]] = 1;
limit = limit-length[itemsTaken[count][limit]];
count = temp;

printf("%d\n", count);

for(i=1; i<=count; i++)
if(used[i]) printf("starbord\n");
else printf("port\n");

Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil

Post by jpfarias »

Ok, I agree it is a knapsack problem, but I could not think in the right way to solve it... Can someone help me here?


A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States

Post by yiuyuho »

I am some confusion about this problem:

it says that the length of car is between 100 and 3000, is that true? I think I am getting some Run time error because of some values of cars are > 3000 in the judge input.


New poster
Posts: 1
Joined: Sun Sep 19, 2004 2:31 pm

10261 (Ferry loading problem) strange WAs...

Post by inverse.midas »

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

Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt

10261 ferry loading again...

Post by mido »

Could someone leak a hint for this problem(and I plead for more than that it's a knap-sack like problem)? I've been trying and leaving this problem for no less than a year now(shame, but true...). Thanks...

tat tvam asi
New poster
Posts: 30
Joined: Sat Nov 30, 2002 1:04 pm

Post by tat tvam asi »

When i solved the problem with dp, got ac in ~0.2,
then switched to exhaustive search (without sophisticated pruning)
and got better time. So the judge's data is weak enough to try this way...
Csaba Noszaly

Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt

Post by mido »

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

Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt

Post by mido »

Finally got the DP solution...1 less problem to solve in life...!!!

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

is there any greedy approach

Post by ranjit »

is there any greedy solution to the problem. I see some zero memory and time solutions

Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien

10261 - DP problem

Post by technobug »

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)

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((total-i)+v>tam) {
                               fer[i] = 0;
                       } else {
                               cabe = 1;

               // se coube em algum lugar.... ok
               if(cabe) {
                       total += v;
                       //cout << "ad o " << k << endl;
               } else {
                       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) {
               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--) {
               if(t) cout << endl;

       return 0;


A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA

Post by Abednego »

Is this answer to the sample input correct?

Code: Select all

I think it is, but how would the special judge test that?
If only I had as much free time as I did in college...

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

Post by little joey »

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.
This means you're not allowed to skip cars when loading. Your answer would give a total length of 52m on starboard.

A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA

Post by Abednego »

Ah! Thanks. Now I understand.
If only I had as much free time as I did in college...

Post Reply

Return to “Volume 102 (10200-10299)”