7534. Locked Treasure

 

A group of n bandits has hidden a stolen treasure in a room. The door to the room should be unlocked only when it is necessary to take the treasure out. Since the bandits do not trust each other, they want to be able to open the room and take the loot only if at least m of them agree to do so.

They decided to install several locks on the door in such a way that it opens only when all the locks are opened. Each lock may have up to n keys, distributed among some subset of the bandits. A group of bandits can open a lock if and only if at least one member of the group possesses a key to that lock.

Given the values n and m, determine the minimum possible number of locks such that, with a proper distribution of keys every group consisting of at least m bandits can open all the locks, while no group of smaller size can open all the locks.

For example, when n = 3 and m = 2, it is sufficient to have 3 locks. The keys to lock 1 are given to bandits 1 and 2, the keys to lock 2 are given to bandits 1 and 3, and the keys to lock 3 are given to bandits 2 and 3. No bandit can open all the locks alone, but any group of two bandits can open all of them. It is easy to see that two locks are not sufficient in this case.

 

Input. The first line contains the number of test cases. Each of the following lines corresponds to one test case and contains two integers n (1 ≤ n ≤ 30) and m (1 ≤ m ≤ n).

 

Output. For each test case, print the minimum number of required locks on a separate line.

 

Sample input

Sample output

4

3 2

5 1

10 7

5 3

3

1

210

10

 

 

SOLUTION

combinatorics

 

Algorithm analysis

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 m people. Take any lock. It is “forbidden” only for one specific subset of m – 1 bandits. In a group of m 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 , which is the number of subsets of size m – 1 taken from a set of n elements.

 

Example

Let there be n = 4 bandits.

For m = 1, the number of locks is  = 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  = 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  = 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  = 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  = 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 .

 

#define MAX 31

long long cnk[MAX][MAX];

 

The function FillCnk fills the array cnk 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 tests.

 

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]);

}