11132 - Dice from pennies

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

Moderator: Board moderators

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

11132 - Dice from pennies

Post by Naani »

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
Location: Calgary, Canada

Post by Darko »

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:

Post by Naani »

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

Post by sohel »

Yes it is wrong ... :D

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

Post by oulongbin »

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

taha
New poster
Posts: 12
Joined: Mon Oct 31, 2005 10:17 am
Location: Egypt

Post by taha »

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

Post by oulongbin »

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:

Post by Larry »

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

Post by Wei-Ming Chen »

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

Post by fpmc »

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

Post by helloneo »

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

Post Reply

Return to “Volume 111 (11100-11199)”