Problem Statement | |||||||||||||
A die has 6 sides, numbered 1-6, and each side is equally likely to come up after a roll. In this problem, you are to consider rolling N dice in K rounds. In each round, you select a subset of the dice rolled in the previous round (you have to roll them all in the first round) and reroll that subset (note that a subset can be all the dice from the previous round). After K rounds, you pick a number between 1 and 6 inclusive and multiply it by the number of dice showing that number. Your goal is to maximize this value. Assuming optimal play, what is the maximum expected score for a given N and K? | |||||||||||||
Definition | |||||||||||||
| |||||||||||||
Notes | |||||||||||||
- | If you elect not to reroll a die in one round, you may not reroll it in any subsequent round. | ||||||||||||
Constraints | |||||||||||||
- | N will be between 1 and 10, inclusive. | ||||||||||||
- | K will be between 1 and 100, inclusive. | ||||||||||||
Examples | |||||||||||||
0) | |||||||||||||
| |||||||||||||
1) | |||||||||||||
| |||||||||||||
2) | |||||||||||||
|