10328 - Coin Toss

[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 ^^

[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.

[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.

[dh3014]

my recurrence is:

Code: Select all

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

[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.

[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.

[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.

[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.

[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.

[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).

[Shih-Chia Cheng]

How do you send your program to the judge?
This may be a problem.

[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?

[Larry]

There's a simple recurrence for the problem, which you can solve by dynamic programming...

[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:

[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.