## ECOO '16 R3 P1 - Nerd Poker

View as PDF

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 , , , , , and 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 sided dice, then do their sided, sided, etc. They roll all the dice of the same type at once, set aside any that show a , then roll the remaining dice, set aside the 's again, and continue this process until they have rolled a on every die.

For example, Brian has four-sided dice. On the first roll, they show: , , and , so he sets aside the and rolls the other two again. This time he gets a and , so he sets aside the and continues to roll the last die. It takes him more rolls before he gets a , for a total of 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 four-sided dice an arbitrarily large number of times, what would be the average number of rolls required?

The input will contain test cases. Each test case consists of a single line with positive integers and where is the number of dice and is the number of sides on each die . 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 's. Your answers should always be rounded up.

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

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