Connection Status:
Competition Arena > SubdividedSlimes
SRM 669 · 2015-08-31 · by sigma425 · Simple Math
Class Name: SubdividedSlimes
Return Type: int
Method Name: needCut
Arg Types: (int, int)
Problem Statement

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 int S: the size of the slime.

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 ints S and M. Calculate and return the smallest possible K (the number of turns in the game) such that Ami and Mami can get at least M mascots in the game. If there exists no such K, return -1 instead.

Constraints

  • S will be between 2 and 1000, inclusive.
  • M will be between 1 and 10^9, inclusive.
Examples
0)
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.)

1)
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.

2)
3
4
Returns: -1

There is a single slime of size 3. The players cannot get 4 mascots in any way.

3)
765
271828
Returns: 14
4)
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.

Coding Area

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

Submitting as anonymous