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 | |||||||||||||
| |||||||||||||
Constraints | |||||||||||||
- | N will be between 2 and 1,000,000,000, inclusive. | ||||||||||||
- | M will be between 1 and N-1, inclusive. | ||||||||||||
Examples | |||||||||||||
0) | |||||||||||||
| |||||||||||||
1) | |||||||||||||
| |||||||||||||
2) | |||||||||||||
|