Local time:  
CET time:  
Balkan Olympiad in Informatics by NET
 

View problem

Problem title: Spaceship
Problem number: 3
Round: DAY 2
Solution: Ship – solution

Marinel Serban

The problem is known in the literature as the “Tennis ball problem”. This is because for s=2 the problem models a real situation in tennis: players receive two balls each time, but only serve one.

Here is a possible way to serve the balls:

Step Received balls Available balls Served balls

1 1, 2 1, 2 1

2 3, 4 2, 3, 4 4

3 5, 6 2, 3, 5, 6 2

4 7, 8 3, 5, 6, 7, 8 6

So, after 4 steps the “team” is { 1, 4, 2, 6 }.

We can give a graphical representation of the possibilities to serve the balls:

- root = 0 – no ball was served

- on the first level, the balls that can be served in the first step

- on the second level, the balls that can be served are:

o balls 2, 3 or 4 if the first ball was number 1.

o balls 3 or 4 if the second ball was number 2.

- on level 3 ...

It is quite clear that we can describe the possibilities of serving the balls in this way. We need only consider the balls in ascending order, because the order of the balls is irrelevant – for instance (1, 4, 2, 6) is the same “team” as (1, 2, 4, 6). The members of the team are given by a root to leaf path in this tree.

One can see that this describes all the possibilities for n=3 steps. We have:

n number of possibilities

1 2

2 5

3 14

4 42

... ...

This values are Catalan’s numbers:

If we generalize to an arbitrary s:

These are the generalized numbers of Catalan.

Of course, for s=2, Catalan’s numbers are:

n Cn value

1 C1 1

2 C2 2

3 C3 5

4 C4 14

5 C5 42

... ... ...

This shows that, in order to obtain the correct value for level n, we have to consider the next Catalan’s number Cn+1.

Experimental results show that the largest possible output is a 55-digit number (there is only a small number of possible test cases, so one can try them all during the competition). In conclusion, one needs to implement some simple big-number operations.

There is also an alternative solution to the problem, which may be considered easier. The solution is based on dynamic programming, using a bi-dimensional array. The relations are quite easy to find based on the tree-view from above. The number of operations performed by this solution is O(N2S), so this solution also runs in the given time limit.

#include <stdlib.h>

#include <stdio.h>

#define MAX 800

#define DIM 200

typedef char Huge[DIM+1];

//the two consecutive lines in Pascal triangle

Huge L1[MAX+2], L2[MAX+2];

Huge K;

int s, n;

FILE *Fin, *Fout;

void Citire(void)

{

Fin = fopen("ship.in", "r");

Fout = fopen("ship.out", "w");

fscanf(Fin, "%d %d", &s, &n);

fclose(Fin);

}

void WriteHuge(Huge X)

{

int i;

for (i=X[0]; i; i--)

fprintf(Fout, "%d", X[i]);

fprintf(Fout, "n");

}

void Atrib0(Huge H)

{

H[0]=0;

}

void AtribValue(Huge H, unsigned long X)

{

H[0]=0;

while (X)

{

H[++H[0]]=X%10;

X/=10;

}

}

void AtribHuge(Huge H, Huge X)

{

int i;

for (i=0; i<=X[0]; i++) H[i]=X[i];

}

void Add(Huge A, Huge B, Huge C)

{

int i, T=0; //A+B-->C

if (B[0]>A[0])

{

for (i=A[0]+1; i<=B[0]; ) A[i++]=0;

A[0]=B[0];

}

else

for (i=B[0]+1; i<=A[0]; ) B[i++]=0;

C[0]=A[0];

for (i=1; i<=A[0]; i++)

{

C[i]=A[i]+B[i]+T;

T=C[i]/10;

C[i]%=10;

}

if (T) C[++C[0]]=T;

}

void Subtract(Huge A, Huge B, Huge C)

{

int i, j; //A-B-->C

Huge X;

for (i=0; i<DIM; i++) X[i]=A[i]; //pastrez A

for (i=B[0]+1; i<=A[0]; ) B[i++]=0;

for (i=1; i<=A[0]; i++)

{ // A[i]+=(T=(A[i]-=B[i]+T)<0)?10:0;

if (A[i]>=B[i])

A[i]-=B[i];

else

{

j=i+1; //I start with the next digit

while (!A[j]) j++;//search for the first <> 0

A[j]--; //subtract 1 from them

j--; //back and

while (j>i) //every digit 0

{

A[j]=9; //became 9

j--;

}

//add 10 to A[i] and now I can subtract B[i]

A[i]=A[i]+10-B[i];

}

}

while (!A[A[0]]) A[0]--;

if (A[0]<0) A[0]=0;

for (i=0; i<DIM; i++) C[i]=A[i];

for (i=0; i<DIM; i++) A[i]=X[i];

}

void Subtract1(Huge A, Huge B)

{

int i, j; //A-B-->A

for (i=B[0]+1; i<=A[0]; ) B[i++]=0;

for (i=1; i<=A[0]; i++)

{ //A[i]+=(T=(A[i]-=B[i]+T)<0)?10:0;

if (A[i]>=B[i])

A[i]-=B[i];

else

{

j=i+1; //I start with the next digit

while (!A[j]) j++; //search for the first <> 0

A[j]--; //subtract 1 from them

j--; //back and

while (j>i) //every digit 0

{

A[j]=9; //became 9

j--;

}

//add 10 to A[i] and now I can subtract B[i]

A[i]=A[i] + 10 - B[i];

}

}

while (!A[A[0]]) A[0]--;

if (A[0]<0) A[0]=0;

}

void Shl(Huge H, int Count)

{

int i;

for (i=H[0]; i; i--)

H[i+Count]=H[i];

for (i=1; i<=Count; ) H[i++]=0;

H[0]+=Count;

}

void Shr(Huge H, int Count)

{

int i;

for (i=Count+1; i<=H[0]; i++) H[i-Count]=H[i];

H[0]-=Count;

}

int Sgn(Huge H1, Huge H2)

{

int i;

while (!H1[H1[0]] && H1[0]) H1[0]--;

while (!H2[H2[0]] && H2[0]) H2[0]--;

if (H1[0] != H2[0])

return H1[0]<H2[0]?-1:1;

i=H1[0];

while ((H1[i]==H2[i] && i)) i--;

return H1[i]<H2[i]?-1:H1[i]==H2[i]?0:1;

}

void Pascal(void)

{

int i, j;

for (i=0; i<=MAX; i++)

{

Atrib0(L1[i]);

Atrib0(L2[i]);

}

AtribValue(L1[1], 1);

for (i=1; i<=s*(n+1); i++)

{

for (j=1; j<=i+1; j++) Add(L1[j-1], L1[j], L2[j]);

for (j=1; j<=i+1; j++) AtribHuge(L1[j], L2[j]);

}

}

void MultHuge(Huge A, Huge B, Huge C)

{

int i, j, T=0; //A*B-->C

C[0]=A[0]+B[0]-1;

for (i=1; i<=A[0]+B[0]; ) C[i++]=0;

for (i=1; i<=A[0]; i++)

for (j=1; j<=B[0]; j++)

C[i+j-1]+=A[i]*B[j];

for (i=1; i<=C[0]; i++)

{

T=(C[i]+=T)/10;

C[i]%=10;

}

if (T) C[++C[0]]=T;

}

void Add1(Huge A, Huge B)

{

int i, T=0; //A+B-->A

Huge C;

for (i=0; i<=DIM; i++) C[i]=0;

if (B[0]>A[0])

{

for (i=A[0]+1; i<=B[0]; ) A[i++]=0;

A[0]=B[0];

}

else

for (i=B[0]+1; i<=A[0]; ) B[i++]=0;

C[0]=A[0];

for (i=1; i<=A[0]; i++)

{

C[i]=A[i]+B[i]+T;

T=C[i]/10;

C[i]%=10;

}

if (T) C[++C[0]]=T;

for (i=0; i<=DIM; i++) A[i]=C[i];

}

void DivideHuge(Huge A, Huge B, Huge C, Huge R)

{

int i;

Huge Aux;

R[0]=0; C[0]=A[0];

for (i=A[0]; i; i--)

{

Shl(R, 1); R[1]=A[i];

C[i]=0;

while (Sgn(B, R)!=1)

{

C[i]++;

Subtract1(R, B);

}

}

while (!C[C[0]]&&C[0]>1) C[0]--;

}

void DivideHuge1(Huge A, Huge B, Huge C, Huge R)

{

int i;

Huge Unu, Aux;

for (i=0; i<=DIM; i++) Unu[i]=C[i]=Aux[i]=0;

for (i=0; i<=A[0]+1; i++) R[i]=A[i];

Unu[0]=1; Unu[1]=1; C[0]=0;

while (Sgn(R, B)>0)

{

Subtract(R, B, Aux);

Add1(C, Unu);

AtribHuge(R, Aux);

}

if (Sgn(R, B)==0)

{

Add1(C, Unu);

Atrib0(R);

}

}

void Calcul(void)

{

Huge numitor;

Huge s_1, N, X, R;

AtribValue(s_1, s-1);

AtribValue(N, n+1);

MultHuge(s_1, N, X);

AtribHuge(numitor, X);

AtribValue(X, 1);

Add1(numitor, X);

DivideHuge(L1[n+2], numitor, K, R);

WriteHuge(K);

}

int main(void)

{

Citire();

Pascal();

Calcul();

fclose(Fout);

return(0);

}

Back

 
© 2003 Vâlsan Mihai Liviu & exist:create
Webmaster contact address: liviuvalsan@yahoo.com
Organisers contact address: ema@mail.dntis.ro