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

0)

 `16` `8`
`Returns: 4`
 The example from the statement.
1)

 `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.
2)

 `3` `1`
`Returns: 2`

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=11133

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14237&pm=11133

rng_58

Testers:

PabloGilberto , ivan_metelsky , pieguy

Greedy, Math