SubdividedSlimes | Topcoder Archive

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.

Definition

Class:: SubdividedSlimes
Method:: needCut
Parameters:: int, int
Returns:: int
Method signature:: int needCut(int S, int M)
(be sure your method is public)

Constraints

S will be between 2 and 1000, inclusive.
M will be between 1 and 10^9, inclusive.

Examples

```
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
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.