10328  Coin Toss
Moderator: Board moderators

 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. _;
Please help me ^^
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 ^^
my recurrence is:
Code: Select all
T(i) = 2T(i  1) + 2^(ik)  T(ik1)

 Experienced poster
 Posts: 106
 Joined: Sun Feb 17, 2002 2:00 am
 Location: Seoul, South Korea
 Contact:
^^
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.
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.

 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
Good Luck.
Code: Select all
T(i) = 2T(i  1) + 2^(ik1)  T(ik1)
More detail:
N  number of tooses, K  length of sequence. Two possible situations:
1. Sequence of length K appeared after N1 tooses  T(N1,K)
2. The last K tosses are heads, NK toss was tail (otherwise, if tosses through NK to N1 were heads, the sequence of length K would appear after N1 tosses). This situations apperars 2^(NK1)T(NK1,k) times, becouse 2^(NK1) is the number of possible combinations of first NK1 tosses, and we must subtract T(NK1,K)  the number of combinations, when in first NK1 tosses appears sequence of length K  they were added as a first situation.
N  number of tooses, K  length of sequence. Two possible situations:
1. Sequence of length K appeared after N1 tooses  T(N1,K)
2. The last K tosses are heads, NK toss was tail (otherwise, if tosses through NK to N1 were heads, the sequence of length K would appear after N1 tosses). This situations apperars 2^(NK1)T(NK1,k) times, becouse 2^(NK1) is the number of possible combinations of first NK1 tosses, and we must subtract T(NK1,K)  the number of combinations, when in first NK1 tosses appears sequence of length K  they were added as a first situation.
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.
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.

 New poster
 Posts: 17
 Joined: Fri May 24, 2002 4:24 am
 Location: Taiwan
 Contact:
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<(DIG1);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<(DIG1);i++)
{
n*=2;
}
refresh(n);
}
void add(int *n1,int *n2)
{
int i;
for(i=0;i<(DIG1);i++)
{
n1 += n2;
while(n1>=10)
{
n1=10;
n1[i+1]++;
}
}
}
void copy(int *n1,int *n2)
{
int i;
for(i=0;i<(DIG1);i++)
n1 = n2;
}
void print(int *n)
{
int i;
for(i=(DIG1);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 < (ni1);j++)
x2(tnum);
add(num,tnum);
return;
}
if(i < (n1))
{
if((ni+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?
[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<(DIG1);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<(DIG1);i++)
{
n*=2;
}
refresh(n);
}
void add(int *n1,int *n2)
{
int i;
for(i=0;i<(DIG1);i++)
{
n1 += n2;
while(n1>=10)
{
n1=10;
n1[i+1]++;
}
}
}
void copy(int *n1,int *n2)
{
int i;
for(i=0;i<(DIG1);i++)
n1 = n2;
}
void print(int *n)
{
int i;
for(i=(DIG1);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 < (ni1);j++)
x2(tnum);
add(num,tnum);
return;
}
if(i < (n1))
{
if((ni+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?
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 malfunction in the BIG int class.
Can someone verify the following input/output.
Input
Output
Thanks.
.. so there must be some malfunction 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
Code: Select all
1026935919671913581551557828400
354199570850176
6144
1
256
1
112
14547280048707942916