RedDragonInn
TCO18 Fun 1A · 2018-04-20 · by Nickolas
Problem Statement
Red Dragon Inn is a board game in which the players' characters spend time in an inn brawling and drinking.
At any moment each character has some gold coins. If a character has "too much fun" during the game, they pass out. When that happens, the gold they have is divided between the inn and all other characters who are left standing. This works as follows:
- The inn takes half of the coins, rounded up to the nearest integer.
- The remaining coins, if any, are split evenly among the remaining characters.
- The remaining coins, if any, are taken by the inn again. (This occurs whenever in step 2 the number of coins isn't divisible by the number of players.)
A character just passed out.
Let C be the number of coins they had.
You do not know the value of C.
You are given the
Constraints
- N will be between 2 and 100, inclusive.
- X will be between 1 and 100,000, inclusive.
3 2 Returns: 17
The process of dividing 17 coins between the inn and three characters looks as follows: First, the inn gets 9 coins (half of all coins, rounded up). Next, the remaining 8 coins are divided between the three characters. This means that each of them gets 2 coins (i.e., 8/3, rounded down). Finally, the inn takes the 2 coins that were left over. It can be shown that 17 is the largest initial amount of coins for which the players receive two coins each. For example, when dividing 18 coins the inn takes 9 and then each player takes 3.
8 13 Returns: 223
42 1234 Returns: 103739
2 1 Returns: 7
100 100000 Returns: 20000199
Submissions are judged against all 43 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RedDragonInn with a public method int maxGold(int N, int X) · 43 test cases · 2 s / 256 MB per case