ECOO '16 R3 P1 - Nerd Poker

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.5s
Memory limit: 64M

Problem types

Nerd Poker is a podcast where you get to listen in on a group of people playing a game of Dungeons and Dragons. There is a lot of dice rolling in this game, using a lot of different types of dice. There are dice with 4, 6, 8, 10, 12, and 20 sides that are regularly used to play the game. In combat and at other critical junctures of the game, low rolls are often bad.

The Nerd Poker players are superstitious, so before entering combat they take their dice and "roll out the ones". They start with their 20 sided dice, then do their 12 sided, 10 sided, etc. They roll all the dice of the same type at once, set aside any that show a 1, then roll the remaining dice, set aside the 1's again, and continue this process until they have rolled a 1 on every die.

For example, Brian has 3 four-sided dice. On the first roll, they show: 1, 3, and 3, so he sets aside the 1 and rolls the other two again. This time he gets a 1 and 4, so he sets aside the 1 and continues to roll the last die. It takes him 3 more rolls before he gets a 1, for a total of 5 rolls. But how many rolls should Brian expect to have to make? Or to put it another way, if Brian rolled out the ones on his 3 four-sided dice an arbitrarily large number of times, what would be the average number of rolls required?

The input will contain 10 test cases. Each test case consists of a single line with 2 positive integers N and S where N is the number of dice and S is the number of sides on each die (1 \le N \times S \le 500). Your job is to output a line containing a single integer for each test case, representing the expected number of rolls required to roll out all the 1's. Your answers should always be rounded up.

Note that the sample input below contains only 3 test cases but the actual data files will contain 10.

Sample Input

1 20
125 4
25 20

Sample Output

20
20
75

Question Development Team

Sam Scott (Sheridan College)
Kevin Forest (Sheridan College)
Stella Lau (University of Cambridge)
Reyno Tilikaynen (University of Waterloo)
David Stermole (ECOO-CS President)
John Ketelaars (ECOO-CS Communications)

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org


Comments

There are no comments at the moment.