Problem Statement
N-1 of the bags contain placebo pills (i.e., pills that have no effect). The last bag contains magic pills. If you take a magic pill, it will take you away from this world and into the Matrix. This is a one-way process: once somebody gets transported to the Matrix, they stay there forever.
You have no idea which of the N bags is the one with the magic pills. In order to find it out, you decided to invite some friends and feed them some pills.
The experiment will be divided into turns. In each turn, you give some pills to each of your friends who are still present. You can assign the pills to friends arbitrarily. For example, some friends may get zero pills while another friend gets pills from multiple bags. Also, multiple friends may get pills from the same bag in each turn. Once you distributed the pills among the friends, each of them eats all the pills they received. The friends who ate a magic pill disappear into the Matrix. The turn ends.
Note that once somebody disappeared, they are gone for the rest of the experiment. You cannot give them more pills in the next rounds.
You are given the
You are looking for a strategy that will guarantee that you will find the bag with magic pills within the given number of turns. The strategy may be adaptive: When distributing the pills in any given round, you know the results of the previous rounds and you may use that information to decide who gets which pills.
Compute and return the smallest number F such that if you invite F friends there will be such a strategy.
Definition
- Class:
- IntoTheMatrix
- Method:
- takePills
- Parameters:
- int, int
- Returns:
- int
- Method signature:
- int takePills(int turns, int N)
- (be sure your method is public)
Constraints
- turns will be between 1 and 10 inclusive.
- N will be between 1 and 10^6 inclusive.
Examples
1
1
Returns: 0
There is only one bag. You don't need to invite any friends, you already know that it contains the magic pills.
2
10
Returns: 3
There are 10 bags and we only have 2 turns to find the correct one. We can easily convince ourselves that fewer than 3 friends are not enough in this case. Here is one possible strategy that uses three friends: Let's label the bags 1 through 10. In the first turn, give pills from bags {1,2,3} to the first friend, pills from {4,5,6} to the second friend, and pills from {7,8,9} to the third one. After the first turn, there are two possibilities: If neither of them disappeared into the Matrix, bag 10 has to be the one with the magic pills. The other case is that one of them disappeared. Without loss of generality, suppose that the first friend is now in the Matrix. We know that the magic pills are in one of the bags 1, 2, and 3. We also still have the two other friends who did not disappear. In the second round, we give a pill from bag 1 to one of them and a pill from bag 2 to the other.
2
1000
Returns: 7
10
2
Returns: 1
4
50
Returns: 3
1
2
Returns: 1
1
1000000
Returns: 20
1
256
Returns: 8
2
729
Returns: 6
2
730
Returns: 7
2
1520
Returns: 7
2
2048
Returns: 7
2
10000
Returns: 9
2
1000000
Returns: 13
3
343
Returns: 5
3
125256
Returns: 9
3
12345
Returns: 7
4
125
Returns: 3
4
126
Returns: 4
4
625
Returns: 4
4
626
Returns: 5
4
390625
Returns: 8
4
390626
Returns: 9
5
216
Returns: 3
5
217
Returns: 4
5
46656
Returns: 6
5
46657
Returns: 7
6
49
Returns: 2
6
50
Returns: 3
6
117649
Returns: 6
6
117650
Returns: 7
7
262144
Returns: 6
7
262145
Returns: 7
8
531441
Returns: 6
8
531442
Returns: 7
9
1000
Returns: 3
9
1001
Returns: 4
9
10000
Returns: 4
9
10001
Returns: 5
9
1000000
Returns: 6
10
121
Returns: 2
10
122
Returns: 3
10
1000
Returns: 3
10
1000000
Returns: 6
1
100
Returns: 7
1
10000
Returns: 14
1
999999
Returns: 20
8
59049
Returns: 5
1
100000
Returns: 17
3
3
Returns: 1