11132  Dice from pennies
Moderator: Board moderators
11132  Dice from pennies
First please correct me if my understanding of what is being asked is wrong. ADB means we have A Bsided dice and we want to simulate these dice using pennies. With A Bsided dice the maximum sum we can get is A*B, so the number of pennies needed is minimum N such that 2^N >=A*B. After this point, we check every N bits and calculate the sum they represent, If this sum is in the range [A,A*B], we return that sum, otherwise return 1.
Am i correct? It says at max we can have 1000 pennies, does that mean we need to consider cases when N can be 1000 as well, which means we have to use BigInteger arithmetic?
Am i correct? It says at max we can have 1000 pennies, does that mean we need to consider cases when N can be 1000 as well, which means we have to use BigInteger arithmetic?
I am signing an important document!
Could you explain it with an example? What i think is suppose we have 2D6, so we need 4 pennies to describe a throw, suppose the sequence is
TTTHTTTHHHHH. "TTTH" is 15, so we look at next "TTTH", this is not possible as well, so we look at "HHHH". This is possible with sum being 1, so we return 1, Is this wrong?
TTTHTTTHHHHH. "TTTH" is 15, so we look at next "TTTH", this is not possible as well, so we look at "HHHH". This is possible with sum being 1, so we return 1, Is this wrong?
I am signing an important document!
Yes it is wrong ...
For 2D6:
You need 3 pennies to describe each throw.
Break TTTHTTTHHHHH into parts of 3.
> TTT HTT THH HHH
TTT is 8 (>6) so ignore
HTT is 4 (valid) ..... found 1
THH is 5 (valid) ...... found 2.
Since we found 2 of them, we stop.
So the answer is 4 + 5 = 9.
For 2D6:
You need 3 pennies to describe each throw.
Break TTTHTTTHHHHH into parts of 3.
> TTT HTT THH HHH
TTT is 8 (>6) so ignore
HTT is 4 (valid) ..... found 1
THH is 5 (valid) ...... found 2.
Since we found 2 of them, we stop.
So the answer is 4 + 5 = 9.
Hmm... And what a challenge it was !!!!!!The above is the best description that Chris has come up with. Trying to sort out what he meant is part of the challenge.
hi taha,thank you very much for your reply,i changed my code ,but still get WA,i'm so confused.This is my code, could you help me to check it,thank you!!!!
Code: Select all
#include <iostream>
using namespace std;
#include <cstring>
#include <cmath>
char str[1001];
int roll,side;
int length(int t)
{
int l;
l=0;
t;
while(t!=0)
{
l++;
t/=2;
}
return l;
}
int number(int a,int b)
{
int i,j;
int sum;
sum=0;
for(i=b,j=0;i>=a;i,j++)
{
if(str[i]=='T')
{
sum+=(int)pow(2.0,(double)j);
}
}
if(sum+1<=side)
return sum+1;
else
return 1;
}
int main()
{
char t;
int len;
int i;
int sum;
int ts;
int l;
while(cin>>roll>>t>>side)
{
if(roll==0 && side==0)
break;
cin>>str;
len=strlen(str);
if(side==1)
l=1;
else
l=length(side);
if(roll==0  side==0)
{
cout<<0<<endl;
}
else
{
sum=0;
i=0;
while(roll)
{
for(;i<len;i+=l)
{
ts=1;
if(i+l1<len)
ts=number(i,i+l1);
if(ts!=1)
{
sum+=ts;
i+=l;
break;
}
}
}
if(sum>0)
cout<<sum<<endl;
else
cout<<1<<endl;
}
}
return 0;
}

 Guru
 Posts: 647
 Joined: Wed Jun 26, 2002 10:12 pm
 Location: Hong Kong and New York City
 Contact:
There's no case where Dice = 0, because I would timeout from it.
Check out http://www.algorithmist.com !

 Experienced poster
 Posts: 122
 Joined: Sun Nov 13, 2005 10:25 am
 Location: Taiwan
some inputs and outputs
Hope it helps.
Code: Select all
1D1
TTTTH
2D2
TTHHTT
18D19
TTTHHHHTTTHHHHTTHTTHTTTTHTTHTHTTTHTTTHTTTTTHTTHHTTHTTTTHTTTTTTTTTTHHHHHHHHHHHTT
18D5
TTTHHHHTTTHHHHTTHTTHTTTTHTTHTHTTTHTTTHTTTTTHTTHHTTHTTTTHTTTTTTTTTTHHHHHHHHHHHTT
18D3
TTTHHHHTTTHHHHTTHTTHTTTTHTTHTHTTTHTTTHTTTTTHTTHHTTHTTTTHTTTTTTTTTTHHHHHHHHHHHTT
0D0
Code: Select all
1
4
1
1
38