NumberMagic
SRM 484 · 2010-03-12 · by rng_58
SRM 484 · 2010-03-12 · by rng_58 · Greedy, Math
Problem Statement
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.
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.
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
3)
1000000000 58585858 Returns: 101
4)
1000000000 999999999 Returns: 999999999
Submissions are judged against all 89 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class NumberMagic with a public method int theMin(int N, int M) · 89 test cases · 2 s / 256 MB per case