IntoTheMatrix
TCO14 Round 3B · 2014-03-26 · by ltaravilse
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.
Constraints
- turns will be between 1 and 10 inclusive.
- N will be between 1 and 10^6 inclusive.
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
Submissions are judged against all 50 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class IntoTheMatrix with a public method int takePills(int turns, int N) · 50 test cases · 2 s / 256 MB per case