Locked Treasure#7534
Consider an arbitrary group of m - 1 bandits. According to the conditions, this group must not be able to open the door. That means there must exist at least one lock for which none of these m - 1 bandits has a key.
Therefore, for every subset of bandits of size m - 1, there must exist a corresponding lock whose keys are not given to any member of that subset.
Consider the following constructive key distribution algorithm:
For each subset of bandits of size m - 1, create one lock.
The keys to this lock are given to all the remaining bandits; that is, the keys are received by n - (m - 1) = n - m + 1 bandits.
The algorithm is correct because:
For a group of m - 1 people, none of them has a key to their corresponding lock. Therefore, the door cannot be opened.
Now consider a group of people. Take any lock. It is "forbidden" only for one specific subset of m - 1 bandits. In a group of people, there is necessarily at least one person outside this subset. Hence, the group has a key to every lock.
The minimum number of required locks is equal to C_n^{m-1}, which is the number of subsets of size m - 1 taken from a set of elements.
Example
Let there be n = 4 bandits.
For m = 1, the number of locks is C_4^0 = 1.
Lock | Subset | Keys |
1 | {} | 1, 2, 3, 4 |
Each bandit should be given a key to the single lock.
For m = 2, the number of locks is C_4^1 = 4.
Lock | Subset | Keys |
1 | {1} | 2, 3, 4 |
2 | {2} | 1, 3, 4 |
3 | {3} | 1, 2, 4 |
4 | {4} | 1, 2, 3 |
The optimal distribution of locks among the bandits is as follows:
Any two bandits will be able to open all four locks and take the treasure.
For m = 3, the number of locks is C_4^2 = 6.
Lock | Subset | Keys |
1 | {1, 2} | 3, 4 |
2 | {1, 3} | 2, 4 |
3 | {1, 4} | 2, 3 |
4 | {2, 3} | 1, 4 |
5 | {2, 4} | 1, 3 |
6 | {3, 4} | 1, 2 |
The optimal distribution of locks among the bandits is as follows:
Any two bandits will be missing the key to exactly one lock. Any three bandits will be able to open all six locks and take the treasure.
For m = 4, the number of locks is C_4^3 = 4.
Lock | Subset | Keys |
1 | {1, 2, 3} | 4 |
2 | {1, 2, 4} | 3 |
3 | {1, 3, 4} | 2 |
4 | {2, 3, 4} | 1 |
The optimal distribution of locks among the bandits is as follows:
In order to open all four locks, each bandit must bring his single unique key.
Now consider the case n = 5, m = 3. The number of locks is C_5^2 = 10.
Lock | Subset | Keys | Lock | Subset | Keys | |
1 | {1, 2} | 3, 4, 5 | 6 | {2, 4} | 1, 3, 5 | |
2 | {1, 3} | 2, 4, 5 | 7 | {2, 5} | 1, 3, 4 | |
3 | {1, 4} | 2, 3, 5 | 8 | {3, 4} | 1, 2, 5 | |
4 | {1, 5} | 2, 3, 4 | 9 | {3, 5} | 1, 2, 4 | |
5 | {2, 3} | 1, 4, 5 | 10 | {4, 5} | 1, 2, 3 |
The optimal distribution of locks among the bandits is as follows:
Algorithm implementation
In the cells cnk[n][k] we compute the values of the binomial coefficients C_n^k.
#define MAX 31
long long cnk[MAX][MAX];The function FillCnk fills the array with the values of the binomial coefficients.
void FillCnk(void)
{
memset(cnk,0,sizeof(cnk));
for (int n = 0; n < MAX; n++) cnk[n][0] = 1;
for (int n = 1; n < MAX; n++)
for (int k = 1; k <= MAX; k++)
cnk[n][k] = cnk[n-1][k] + cnk[n-1][k-1];
}The main part of the program. Call the function FillCnk.
FillCnk();Read the number of test cases .
scanf("%d",&tests);
while (tests--)
{Read the input data for the current test case and print the answer.
scanf("%d %d",&n,&m);
printf("%lld\n",cnk[n][m-1]);
}