Page 1 of 2

### 10328 - Coin Toss

Posted: Sun Jul 14, 2002 7:30 pm
I want to solve this problem. But I don't know about solution.

Can you give me some hint to slove this problem?

I think that every coin toss condition appeared combination number.

if n = 4 and k = 1, then I calculate 4C1

if n = 4 and k = 2, then I calculate 4C2 and so on...

But how can I check to coin side sequnce?

I don't know about it. -_-;

Posted: Tue Jul 16, 2002 5:05 am
my solution uses no combination numbers.
I just maintain an array table[101],
which table means how many solutions in i coins.
Find the recurrence and use dynamic programming skills to solve the problem. The recurrence contains terms represented as power of 2, think of it.

Posted: Wed Jul 17, 2002 11:05 pm

Can you show me your recusive eqution for your dynamic programming ?

Maybe it's a greatest help for me. thanks.

Posted: Thu Jul 18, 2002 4:21 am
my recurrence is:

Code: Select all

``````T(i) = 2T(i - 1) + 2^(i-k) - T(i-k-1)
``````

### ^^

Posted: Sat Jul 20, 2002 9:15 pm

to understand... : )

What means i and k?

Maybe I think that "i" is number of coin, and "k" is input consecutive

value of coin face. ( Is it right? )

I temptatively calculated your recurrence formula, but some case

doesn't match correct output. ( For example, k = 1 )

And what is your initial equation?

Posted: Mon Jul 22, 2002 8:14 am
I believe there is a typing error on this recurrence. it could be

Code: Select all

``T(i) = 2T(i - 1) + 2^(i-k-1) - T(i-k-1) ``
Good Luck.

Posted: Thu Jul 25, 2002 10:47 am
More detail:

N - number of tooses, K - length of sequence. Two possible situations:
1. Sequence of length K appeared after N-1 tooses - T(N-1,K)
2. The last K tosses are heads, N-K toss was tail (otherwise, if tosses through N-K to N-1 were heads, the sequence of length K would appear after N-1 tosses). This situations apperars 2^(N-K-1)-T(N-K-1,k) times, becouse 2^(N-K-1) is the number of possible combinations of first N-K-1 tosses, and we must subtract T(N-K-1,K) - the number of combinations, when in first N-K-1 tosses appears sequence of length K - they were added as a first situation.

### 10328

Posted: Thu Jul 25, 2002 2:17 pm
Hello,
i've got a little problem with this task. I got WA, but i've checked my output with my friend's program, and in all tests we've got the same outputs, more: our output files were completely the same! My friend's program got AC, of course.

Posted: Fri Aug 02, 2002 10:49 pm

posted.

Good luck.

Posted: Tue Aug 13, 2002 10:05 am
The problem is not here. I would like to know, what problems may occur, when i'm adding two big numbers as strings in GNU Pascal, becouse - like i said - our outputs for every possible input were the same (so the problem is not in the way of adding them).

Posted: Wed Aug 14, 2002 6:39 am
How do you send your program to the judge?
This may be a problem.

### 10328

Posted: Fri Feb 07, 2003 6:41 pm
The following code runs very fast on my computer:

[cpp]
#include <stdio.h>
#include <math.h>

#define DIG 40
#define CMAX 102

typedef unsigned long int ULint;
ULint n,k;
int sans[CMAX ][DIG];

int num[DIG];
int tnum[DIG];

void refresh(int *n)
{
int i;
for(i=0;i<(DIG-1);i++)
{
while(n>=10)
{
n-=10;
n[i+1]++;
}
}
}

void initnum(int *n)
{
int i;
for(i=0;i<DIG;i++)
n=0;
}

void x2(int *n)
{
int i;
for(i=0;i<(DIG-1);i++)
{
n*=2;
}
refresh(n);
}

{
int i;
for(i=0;i<(DIG-1);i++)
{
n1 += n2;
while(n1>=10)
{
n1-=10;
n1[i+1]++;
}
}
}

void copy(int *n1,int *n2)
{
int i;
for(i=0;i<(DIG-1);i++)
n1 = n2;
}

void print(int *n)
{
int i;
for(i=(DIG-1);i>=0;i--)
{
if(n[i]>0)break;
}
for(;i>=0;i--)
printf("%d",n[i]);
printf("\n");
}

void permute(int i,int counter)
{
int tans[DIG];
int j;
if(counter == 0)
{
if(sans[i][0]!=-1)
{
return;
}
}
if(counter >= k)
{
initnum(tnum);
tnum[0]=1;
for(j = 0;j < (n-i-1);j++)
x2(tnum);
return;
}
if(i < (n-1))
{
if((n-i+counter) >= k)
{
if(sans[i+1][0]==-1)
{
copy(tans,num);
initnum(num);
}
permute(i+1,0);
if(sans[i+1][0]==-1)
{
copy(sans[i+1],num);
}
permute(i+1,counter+1);
}
}
}

int main()
{
int i;
while(scanf("%d %d",&n,&k)!=EOF)
{
for(i=0;i<CMAX;i++)sans[i][0] = -1;
initnum(num);
permute(0,0);
permute(0,1);
print(num);
}
return 0;
}
[/cpp]

However, I always get a time limit error. Is there anything wrong with it?

Posted: Thu Mar 13, 2003 6:14 pm
There's a simple recurrence for the problem, which you can solve by dynamic programming...

Posted: Wed Apr 16, 2003 12:54 pm
pial[1][1]=1;pial[2][1]=3;pial[2][2]=1;pial[3][1]=7;pial[3][2]=3;
pial[3][3]=1;
for(i=4;i<=50;i++)
for(j=1;j<=i;j++)
if(i==j)pial[j]=1;
else
pial[j]=2*pial[i-1][j]+pow(2,i-j-1)-pial[i-j-1][j];

what is wrong in here: or can anyone give me some sample input output:

### wa..

Posted: Tue May 24, 2005 11:41 am
I am getting WA for this problem.. and surprising thing is that my recurrence is identical to the one given above..
.. so there must be some mal-function in the BIG int class.

Can someone verify the following input/output.

Input

Code: Select all

``````100 5
50 6
50 40
30 30
29 23
8 8
65 60
65 6
``````
Output

Code: Select all

``````1026935919671913581551557828400
354199570850176
6144
1
256
1
112
14547280048707942916
``````
Thanks.