2013-12-05 16:13:41Morris
[UVA] 11132 - Dice from pennies
Problem D: Dice from pennies
Colin likes to play role playing games. These games usually involve
dice with varying numbers of sides; a 20 sided die is known as a D20
(marked 1-20 inclusive), a regular six sided die a D6, and so on.
Unfortunately, Colin has forgotten his bag of dice, and has only a jar
full of pennies. Help him make his savings throw!
For each required roll, Colin will tip out the pennies and read off
whether they are heads or tails. This will serve as the random input
to a function that returns a number fitting the range
of the die. For example, to simulate a regular die, the pairing is as
follows:
HHH = 1 HHT = 2 HTH = 3 HTT = 4 THH = 5 THT = 6and analogously for other dice using the minimum number of pennies to encode all the needed die numbers. See sample input for examples. Note that some outputs from the coins will not match to a die number when read from the first position. In this case, use the next coins in the list to return a result. For example, in case of 6 sided dice, TTTHHH maps to the value 1, not 5 as someone may expect. The input will consist of multiple sets of input, each set consisting of a number of dice to be rolled and a type (e.g., 2D6 means roll 2 regular 6 sided dice), followed by the status of the pennies in the next line with no spaces. The last set will start with 0D0 and this set should not be processed. Output will be a single number for each set, consisting of the sum of the simulated dice. If there are insufficient coins to determine an outcome, return -1. There will be at most 1000 coins.
Sample input
1D6 HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH 1D6 TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT 1D6 HTTHHHHTHTHTTTTHTHTHHHTHTHTHTHTHTTHTHTTTTTTHTHHTT 2D2 THTHTHHHHTHHHHTTTTTHTHTHHTHTHTTHTHTHHTHTHTHTHHHHH 1D20 THHHTHHHHTTHTTTTTTHHHHTHTHHHHHHHHHTTTTHTHHHHHHTTT 0D0
Output for sample input
1 -1 4 3 18
題目完全沒看懂，不過還是 AC 了。
看了討論區的測資，輸入的字串應為當做二元串來讀，
而字串拆成好幾段，每一段應該可以被轉換成二進制數字，
在不超過骰子點數的情況下，要找到 n 組符合的骰子點數，並且加總。
字串拆的方式，根據骰子最大點數，以最少的二進制數字表示。
#include <stdio.h>
#include <string.h>
using namespace std;
int main() {
int n, m, i, j;
char s[1024];
while(scanf("%dD%d", &n, &m) == 2) {
if(n == 0 && m == 0)
break;
scanf("%s", s);
int d = 0;
for(i = 0; i < 30; i++)
if((m-1)&(1<<i))
d = i;
d++;
int l = strlen(s);
int sum = 0, cnt = 0;
for(i = 0; i+d <= l && n; i += d) {
int val = 0;
for(j = 0; j < d; j++) {
val = val << 1;
if(s[i+j] == 'T')
val |= 1;
}
val++;
if(val <= m) {
sum += val;
cnt++;
n--;
}
}
if(n == 0)
printf("%d\n", sum);
else
puts("-1");
}
return 0;
}
/*
18D19
TTTHHHHTTTHHHHTTHTTHTTTTHTTHTHTTTHTTTHTTTTTHTTHHTTHTTTTHTTTTTTTTTTHHHHHHHHHHHTT
*/