SubdividedSlimes
SRM 669 · 2015-08-31 · by sigma425
Problem Statement
The idols Ami and Mami like playing games.
Today they bought a new game.
At the beginning of the game a single slime appears on the screen.
You are given an
The game consists of K turns. In each turn of the game the player must choose a single slime and cut it into two smaller parts. More precisely, suppose that the player chose a slime of size z. When cutting this slime, the player must choose two positive integers x and y such that x+y = z. The player will then cut the slime into two smaller slimes. The sizes of those smaller slimes will be x and y, respectively. Note that the player must always choose a slime of size 2 or more, as it is not possible to cut a slime of size 1.
The player gets a reward for making each cut: whenever you cut a slime of size x+y into slimes of sizes x and y, the player is awarded x*y mascots.
Ami and Mami have just started a new game.
You are given two
Constraints
- S will be between 2 and 1000, inclusive.
- M will be between 1 and 10^9, inclusive.
3 2 Returns: 1
There is a single slime of size 3, and the players have to get at least two mascots. In this case, K = 1 is sufficient. In the only step, cut the only slime into two slimes with sizes 1 and 2. (This gives them 1*2 = 2 mascots.)
3 3 Returns: 2
There is a single slime of size 3, and the players have to get at least three mascots. They can get three mascots in two steps: In the first step, cut the only slime into two slimes with sizes 1 and 2. (This gives them 1*2 = 2 mascots.) In the second step, choose the slime of size 2 and cut it into two slimes of size 1 each. (This gives them 1*1 = 1 mascot.) The total number of mascots they obtained is 2 + 1 = 3.
3 4 Returns: -1
There is a single slime of size 3. The players cannot get 4 mascots in any way.
765 271828 Returns: 14
2 1 Returns: 1
Submissions are judged against all 181 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SubdividedSlimes with a public method int needCut(int S, int M) · 181 test cases · 2 s / 256 MB per case