Danhyeon Land Casino
The Danhyun coal mine in Danhyun City used to be the livelihood of thousands of residents before it was taken over by the Ohsong Group. They used shady tactics to shut down the mine and transformed the land into a row of buildings, highlighted by the Danhyun Land Casino.
This is where notorious gamblers from all over the Danhyun region often gather to do business. But the corporation isn't that simple — they've devised all sorts of schemes to squeeze extra profit out of these "naive" players. One of them is tampering with the American Roulette game.
A bit about this game: the game is a wheel divided into 38 slots (slot 0, slot 00, and slots 1 through 36). If a player bets on a single number (from 1 to 36) and wins, they gain 35 times their stake. With a winning probability of only \(\frac{1}{38}\) to gain 35 coins, but a losing probability of \(\frac{37}{38}\) to lose 1 coin, the expected value for each coin bet is:
\(EV = (35 \times \frac{1}{38}) + (-1 \times \frac{37}{38}) = -\frac{2}{38} \approx -0.0526\).
Simply put, you lose \(0.0526\) coins per round on average.
The house has cheated by making slot 0 (which players never bet on) appear with probability \(p = \frac{a}{10^m}\). That is, the winning probability becomes only \(\frac{1-p}{37}\).
...
A certain tycoon is heading toward the casino, betting 1 coin per round. In theory, what is the smallest non-negative integer value \(a\) that the house must choose so that this tycoon will lose at least \(L\) coins after 1000 rounds of betting?
...
"The Case of Kang Woo Sung"
Input
- A single line containing two positive integers \(L, m \ (27\le L \le 1000; 2\le m \le 9)\).
Output
- The answer to the problem.
Scoring
- Subtask 1 (10%): \(m=2\).
- Subtask 2 (60%): \(m \le 6\).
- Subtask 3 (30%): No additional constraints.
Example
Example 1
input
50 2
output
3
Explanation
The winning probability of each round is \(\frac{1- \frac{3}{10^2} }{37} \approx 0.0262\).
On average, per round bet, the tycoon loses \((35 \times 0.0262) + (-1 \times (1-0.0262)) \approx -0.0568\). So after 1000 rounds, he loses about 56.8 coins.
Comments