## 10328 - Coin Toss

Moderator: Board moderators

soyoja
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:

### 10328 - Coin Toss

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

dh3014
New poster
Posts: 24
Joined: Tue Mar 26, 2002 2:00 am
Location: Taiwan
Contact:
my solution uses no combination numbers.
I just maintain an array table,
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.

soyoja
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:

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

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

dh3014
New poster
Posts: 24
Joined: Tue Mar 26, 2002 2:00 am
Location: Taiwan
Contact:
my recurrence is:

Code: Select all

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

soyoja
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:

### ^^

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?

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan
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.

filipek
New poster
Posts: 9
Joined: Sat Jun 22, 2002 12:16 pm
Location: Poland
Contact:
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.

filipek
New poster
Posts: 9
Joined: Sat Jun 22, 2002 12:16 pm
Location: Poland
Contact:

### 10328

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.

soyoja
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:

posted.

Good luck.

filipek
New poster
Posts: 9
Joined: Sat Jun 22, 2002 12:16 pm
Location: Poland
Contact:
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).

Shih-Chia Cheng
New poster
Posts: 17
Joined: Fri May 24, 2002 4:24 am
Location: Taiwan
Contact:
How do you send your program to the judge?
This may be a problem.

elf
New poster
Posts: 1
Joined: Sun Jan 26, 2003 7:43 pm

### 10328

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]!=-1)
{
return;
}
}
if(counter >= k)
{
initnum(tnum);
tnum=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]==-1)
{
copy(tans,num);
initnum(num);
}
permute(i+1,0);
if(sans[i+1]==-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] = -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?

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
There's a simple recurrence for the problem, which you can solve by dynamic programming...

erfan
New poster
Posts: 44
Joined: Tue Apr 15, 2003 4:31 pm
Contact:
pial=1;pial=3;pial=1;pial=7;pial=3;
pial=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:

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### wa..

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.