11132 - Dice from pennies

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

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

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?

[sohel]

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]

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]

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]

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]

There's no case where Dice = 0, because I would timeout from it.

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

Hm... this is strange.

For case

Code: Select all

2D2
TTHHTT

how do you get 4??

Frank

[helloneo]

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