Page 1 of 2

10328 - Coin Toss

Posted: Sun Jul 14, 2002 7:30 pm
by soyoja
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. -_-;

Please help me ^^

Posted: Tue Jul 16, 2002 5:05 am
by dh3014
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.

answer

Posted: Wed Jul 17, 2002 11:05 pm
by soyoja
Thank you for your answer. But I still don't know about solving method.

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
by dh3014
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
by soyoja
Thanks for your answer. But I feel that your explanation is not enough

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?

I hope your kindly answer, and please more detatiled explain if you can.

Posted: Mon Jul 22, 2002 8:14 am
by LittleJohn
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
by filipek
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
by filipek
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
by soyoja
Your explanation is not enough to find your problem.

Please show your pseudocode or algorithm.

The more detailed describe your program, the more helpful answer would be

posted.

Good luck.

Posted: Tue Aug 13, 2002 10:05 am
by filipek
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
by Shih-Chia Cheng
How do you send your program to the judge?
This may be a problem.

10328

Posted: Fri Feb 07, 2003 6:41 pm
by elf
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);
}

void add(int *n1,int *n2)
{
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)
{
add(num,sans[i]);
return;
}
}
if(counter >= k)
{
initnum(tnum);
tnum[0]=1;
for(j = 0;j < (n-i-1);j++)
x2(tnum);
add(num,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);
add(num,tans);
}
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
by Larry
There's a simple recurrence for the problem, which you can solve by dynamic programming...

Posted: Wed Apr 16, 2003 12:54 pm
by erfan
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
by sohel
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.