QuangAndNam
SRM 794 · 2020-11-24 · by misof
Problem Statement
Quang and Nam are playing a game.
Nam has N stones.
Quang has secretly chosen two integers L and R such that 1 <= L <= R <= N. The integers between L and R, inclusive, are called good. All other integers are called bad.
Nam's task is to determine the values L and R.
Nam can ask Quang an abitrary number of questions. For each question, Nam will partition all N stones into one or more non-empty piles. He will then show the partition to Quang and ask: "Are all these pile sizes good?" Quang will always truthfully answer "yes" or "no".
Nam is very smart, so he can deduce all information contained in Quang's answers. On the other hand, he does not want to guess, so he will only announce the pair (L, R) if he is 100% sure what the two numbers are.
Given N, count all admissible pairs (L, R) such that Nam can win the game.
Constraints
- N will be between 1 and 10^6, inclusive.
2 Returns: 3
For N = 2 there are 3 possible pairs (L, R) Quang can choose: (1, 1), (1, 2) and (2, 2). Nam can play the game as follows: Partition the stones into two piles, each containing a single stone. Show the configuration to Quang. If he gets the answer "no", he can deduce that L = R = 2, and he wins the game. Leave both stones on the same pile. Show the configuration to Quang. If he gets the answer "yes" in both cases, Quang chose L = 1 and R = 2. If the second answer was "no", we must have L = R = 1. Thus, for N = 2 Nam can always win the game.
3 Returns: 4
Nam can only win the game if the pair (L, R) chosen by Quang is one of the pairs (1, 1), (1, 2), (1, 3) and (2, 2). If Quang chooses one of the pairs (2, 3) or (3, 3), Nam will not be able to win the game. In both situations, Nam will get the answer "yes" if he shows Quang all three stones on the same pile, and the answer "no" for all other partitions of stones. In more detail, suppose (L, R) = (2, 3) and Nam produces the partition with two stones on one pile and one stone on the other pile. When Quang looks at this partition, he sees pile sizes 2 and 1. The number 2 is good, but the number 1 is bad. Hence, the correct answer to the question "Are all these pile sizes good?" is "no".
10 Returns: 23
1 Returns: 1
4 Returns: 6
Submissions are judged against all 150 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class QuangAndNam with a public method long long count(int N) · 150 test cases · 2 s / 256 MB per case