11132 - Dice from pennies

Moderator: Board moderators

Naani
New poster
Posts: 12
Joined: Mon Sep 25, 2006 11:10 am
Location: India
Contact:

11132 - Dice from pennies

First please correct me if my understanding of what is being asked is wrong. ADB means we have A B-sided dice and we want to simulate these dice using pennies. With A B-sided 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?
I am signing an important document!

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
No, you misunderstood the way it goes - you look for one throw, then if you find it look for another and so on...

And you are right, they never said you can't expect 1000-sided die or something. But integers work fine.

Naani
New poster
Posts: 12
Joined: Mon Sep 25, 2006 11:10 am
Location: India
Contact:
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?
I am signing an important document!

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
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.
The above is the best description that Chris has come up with. Trying to sort out what he meant is part of the challenge.
Hmm... And what a challenge it was !!!!!!

oulongbin
Learning poster
Posts: 53
Joined: Sat Jul 10, 2004 5:57 pm
Location: Shanghai China
Hi sohel,i just obey your way to solve this problem,but always get WA.
Could you give me some samples or this problem have any tricks in it??
thanks

taha
New poster
Posts: 12
Joined: Mon Oct 31, 2005 10:17 am
Location: Egypt
if side=0 or dice=0 but not both printf("0\n");
Take care also from the case where the input string size is not multiple of B (where B is the required number of bits to represent each throw)

oulongbin
Learning poster
Posts: 53
Joined: Sat Jul 10, 2004 5:57 pm
Location: Shanghai China
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+l-1<len)
ts=number(i,i+l-1);
if(ts!=-1)
{
sum+=ts;
i+=l;
break;
}
}
}
if(sum>0)
cout<<sum<<endl;
else
cout<<-1<<endl;
}
}
return 0;
}
``````

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

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan
some inputs and outputs

Code: Select all

``````1D1
TTTTH
2D2
TTHHTT
18D19
TTTHHHHTTTHHHHTTHTTHTTTTHTTHTHTTTHTTTHTTTTTHTTHHTTHTTTTHTTTTTTTTTTHHHHHHHHHHHTT
18D5
TTTHHHHTTTHHHHTTHTTHTTTTHTTHTHTTTHTTTHTTTTTHTTHHTTHTTTTHTTTTTTTTTTHHHHHHHHHHHTT
18D3
TTTHHHHTTTHHHHTTHTTHTTTTHTTHTHTTTHTTTHTTTTTHTTHHTTHTTTTHTTTTTTTTTTHHHHHHHHHHHTT
0D0``````

Code: Select all

``````1
4
-1
-1
38``````
Hope it helps.

fpmc
New poster
Posts: 23
Joined: Tue Sep 30, 2003 11:44 pm
Hm... this is strange.

For case

Code: Select all

``````2D2
TTHHTT``````
how do you get 4??

Frank

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
fpmc wrote:Hm... this is strange.

For case

Code: Select all

``````2D2
TTHHTT``````
how do you get 4??

Frank

It's 2-side dice so we only need 1 coin for 1 throw..
'H' is 1 and 'T' is 2
We got 2 for the first 'T' and 2 again for the 2nd 'T' so total 4..
We don't need the rest of them..