7534. Замкнутое сокровище

 

Группа из n бандитов спрятала украденное сокровище в комнате. Дверь в эту комнату следует отпирать только тогда, когда понадобится вынести сокровище. Поскольку бандиты не доверяют друг другу, они хотят иметь возможность открыть комнату и забрать добычу лишь в том случае, если этого пожелают как минимум m из них.

Они решили установить на дверь несколько замков так, чтобы она открывалась только тогда, когда открыты все замки. Каждый замок может иметь до n ключей, распределённых между некоторым подмножеством бандитов. Группа бандитов может открыть замок тогда и только тогда, когда хотя бы один из членов группы обладает ключом от этого замка.

По заданным значениям n и m определите наименьшее возможное количество замков такое, что при корректном распределении ключей каждая группа, состоящая как минимум из m бандитов, сможет открыть все замки, а никакая группа меньшего размера открыть все замки не сможет.

Например, при n = 3 и m = 2 достаточно 3 замков. Ключи от замка 1 получают бандиты 1 и 2, от замка 2 – бандиты 1 и 3, а от замка 3 – бандиты 2 и 3. Ни один бандит не может открыть все замки в одиночку, однако любая группа из двух бандитов способна открыть их все. Нетрудно убедиться, что в этом случае двух замков недостаточно.

 

Вход. Первая строка содержит количество тестов. Каждая следующая строка является отдельным тестом и содержит два числа n (1 ≤ n ≤ 30) и m (1 ≤ m ≤ n).

 

Выход. Для каждого теста в отдельной строке выведите минимальное количество необходимых замков.

 

Пример входа

Пример выхода

4

3 2

5 1

10 7

5 3

3

1

210

10

 

 

РЕШЕНИЕ

комбинаторика

 

Анализ алгоритма

Рассмотрим произвольную группу из m – 1 бандита. По условию она не должна открыть дверь. То есть должен существовать хотя бы один замок, для которого ни у кого из этих m – 1 бандитов нет ключа.

Таким образом, для каждого подмножества бандитов размера m – 1 должен существовать свой замок, ключи от которого не выданы ни одному из них.

 

Рассмотрим конструктивный алгоритм распределения ключей:

·        Для каждого подмножества бандитов размера m – 1 создадим один замок.

·        Ключи от этого замка выдадим всем остальным бандитам, то есть ключи получают n – (m – 1) = n – m + 1 человек.

 

Алгоритм корректный, так как:

·        Для группы из m – 1 человек для их собственного замка ни у кого нет ключа. Поэтому дверь не откроется.

·        Рассмотрим группу из m человек. Возьмём любой замок. Он “запрещён” только для одного конкретного набора из m – 1 бандитов. В группе из m человек обязательно есть кто-то вне этого набора. Значит, у группы есть ключ от каждого замка.

 

Минимальное количество необходимых замков равно  – количеству подмножеств из n элементов размера m – 1.

 

Пример

Пусть имеется n = 4 бандита.

При m = 1 количество замков равно  = 1.

 

Замок

Подмножество

Ключи

1

{}

1, 2, 3, 4

 

Каждому бандиту следует дать ключ от единственного замка:

 

При m = 2 количество замков равно  = 4.

 

Замок

Подмножество

Ключи

1

{1}

2, 3, 4

2

{2}

1, 3, 4

3

{3}

1, 2, 4

4

{4}

1, 2, 3

 

Оптимальное распределение замков среди бандитов следующее:

 

 

Любые два бандита смогут открыть все четыре замка и забрать сокровище.

 

При m = 3 количество замков равно  = 6.

 

Замок

Подмножество

Ключи

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

 

Оптимальное распределение замков среди бандитов следующее:

 

У любых двух бандитов не будет хватать ключа всего лишь от одного замка. Любые три бандита смогут открыть все шесть замков и забрать сокровище.

 

При m = 4 количество замков равно  = 4.

 

Замок

Подмножество

Ключи

1

{1, 2, 3}

4

2

{1, 2, 4}

3

3

{1, 3, 4}

2

4

{2, 3, 4}

1

 

Оптимальное распределение замков среди бандитов следующее:

Для того чтобы открыть все 4 замка, каждый бандит должен принести его единственный уникальный ключ.

 

Рассмотрим случай n = 5, m = 3. Количество замков равно  = 10.

 

Замок

Подмножество

Ключи

Замок

Подмножество

Ключи

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

 

Оптимальное распределение замков среди бандитов следующее:

 

Реализация алгоритма

В ячейках cnk[n][k] вычисляем значения биномиальных коэффициентов .

 

#define MAX 31

long long cnk[MAX][MAX];

 

Функция FillCnk заполняет массив cnk значениями биномиальных коэффициентов.

 

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

}

 

Основная часть программы. Вызываем функцию FillCnk.

 

FillCnk();

 

Читаем количество тестов tests.

 

scanf("%d",&tests);

while (tests--)

{

 

Читаем входные данные очередного теста и выводим ответ.

 

  scanf("%d %d",&n,&m);

  printf("%lld\n",cnk[n][m-1]);

}