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^(i-k) - T(i-k-1)
-
- 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^(i-k-1) - T(i-k-1)
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.
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
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<(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?
[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?
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
Output
Thanks.
.. 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
Code: Select all
1026935919671913581551557828400
354199570850176
6144
1
256
1
112
14547280048707942916