NumberMagic | Topcoder Archive

Problem Statement

NOTE: This problem statement contains images that may not display properly if viewed outside of the applet.

Taro shows a magic trick to Hanako.

Taro: Hello Hanako. I'll show you a magic trick. Please imagine a positive integer less than or equal to 16.
Hanako: OK. I imagined it.
Taro: (Taro shows card 1 to Hanako.) Does this card contain your number?
Hanako: Yes.
Taro: (Taro shows card 2 to Hanako.) Does this card contain your number?
Hanako: No.
Taro: (Taro shows card 3 to Hanako.) Does this card contain your number?
Hanako: Yes.
Taro: (Taro shows card 4 to Hanako.) Does this card contain your number?
Hanako: Yes.
Taro: Your number is 5!

(Card 1 contains 1, 2, 3, 4, 5, 6, 7 and 8. Card 2 contains 1, 2, 3, 4, 9, 10, 11 and 12. Card 3 contains 1, 2, 5, 6, 9, 10, 13 and 14. Card 4 contains 1, 3, 5, 7, 9, 11, 13 and 15.)

Let's generalize this magic trick. Hanako imagines a positive integer less than or equal to N. Each card must contain exactly M different integers between 1 and N, inclusive. Taro must be able to determine Hanako's number correctly using her answers to his questions. Return the minimal number of cards required to perform this magic trick successfully every time.

Definition

Class:: NumberMagic
Method:: theMin
Parameters:: int, int
Returns:: int
Method signature:: int theMin(int N, int M)
(be sure your method is public)

Constraints

N will be between 2 and 1,000,000,000, inclusive.
M will be between 1 and N-1, inclusive.

Examples

```
16
```
```
8
```
```
Returns: 4
```
The example from the statement.
```
2
```
```
1
```
```
Returns: 1
```
Write 1 on the only card. If Hanako answers "yes", her number is 1. If she answers "no", her number is 2.
```
3
```
```
1
```
```
Returns: 2
```

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.