10328 - Coin Toss

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10328 - Coin Toss

Post by soyoja » Sun Jul 14, 2002 7:30 pm

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
New poster
Posts: 24
Joined: Tue Mar 26, 2002 2:00 am
Location: Taiwan
Contact:

Post by dh3014 » Tue Jul 16, 2002 5:05 am

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

answer

Post by soyoja » Wed Jul 17, 2002 11:05 pm

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
New poster
Posts: 24
Joined: Tue Mar 26, 2002 2:00 am
Location: Taiwan
Contact:

Post by dh3014 » Thu Jul 18, 2002 4:21 am

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:

^^

Post by soyoja » Sat Jul 20, 2002 9:15 pm

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

Post by LittleJohn » Mon Jul 22, 2002 8:14 am

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.

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

Post by filipek » Thu Jul 25, 2002 10:47 am

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.

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

10328

Post by filipek » Thu Jul 25, 2002 2:17 pm

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:

Post by soyoja » Fri Aug 02, 2002 10:49 pm

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.

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

Post by filipek » Tue Aug 13, 2002 10:05 am

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:

Post by Shih-Chia Cheng » Wed Aug 14, 2002 6:39 am

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

Post by elf » Fri Feb 07, 2003 6:41 pm

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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Thu Mar 13, 2003 6:14 pm

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
Location: Chittagong,Bangladesh
Contact:

Post by erfan » Wed Apr 16, 2003 12:54 pm

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:

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

wa..

Post by sohel » Tue May 24, 2005 11:41 am

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.

Post Reply

Return to “Volume 103 (10300-10399)”