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

Задача взята с сайта e-olymp

Задача

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

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

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

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

Входные данные

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

Выходные данные

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

Тесты

#   ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 4
3 2
5 1
10 7
5 3
3
1
210
10
2 2
5 3
3 2
10
3
3 6
2 1
7 2
3 1
5 4
3 2
9 2
1
7
1
10
3
9

Код программы

Решение

Для каждой группы из $m-1$ бандитов существует замок такой, что его могут открыть все остальные группы, кроме этой. Потому что, просто обьеденив две группы с одинаковыми замками, мы получим одну большую чем $m-1$, которая не может открыть замок. Таким образом, всего должно быть столько замков, сколько существует способов выбрать $m-1$ группу из $n$ бандитов. То есть $C_{n}^{m-1}$.
Для нахождения биномиальных коэффициентов воспользуемся треугольником Паскаля, который будем хранить в двумерном массиве.

Ссылки

Условие задачи на e-olymp

Код программы на ideone

Треугольник Паскаля на Wikipedia

Related Images:

e-olymp 2666. Половина

Задача

Напишите программу, заполняющую массив [latex]n \times n[/latex] следующим образом: на побочной диагонали стоят нули, выше диагонали двойки, ниже единицы.

Входные данные

Дано натуральное число [latex]n[/latex] [latex](n \leqslant 20).[/latex]

Выходные данные

Выведите массив, заполненный по указанному правилу.

Тесты

# Входные данные Выходные данные
1 2 20
01
2 3 220
201
011
3 4 2220
2201
2011
0111
4 5 22220
22201
22011
20111
01111
5 10 2222222220
2222222201
2222222011
2222220111
2222201111
2222011111
2220111111
2201111111
2011111111
0111111111

Код программы

Решение задачи

Для решения задачи создадим двумерный массив, количество строк и столбцов которого не превышают [latex]20[/latex]. Заполнять его будем при помощи двойного цикла, как указано в решении задачи. Введем следующие обозначения:

  • [latex]i + j = n — 1[/latex], если ячейка [latex](i, j)[/latex] лежит на побочной диагонали;
  • [latex]i + j > n — 1[/latex], если ячейка [latex](i, j)[/latex] лежит ниже побочной диагонали;
  • [latex]i + j < n — 1[/latex], если ячейка [latex](i, j)[/latex] лежит выше побочной диагонали.

Далее заполняем массив в соответствии с введеными обозначениями и условием задачи, а затем выводим его на экран. Задача решена.

Ссылки

Ссылка на e-olymp
Ссылка на ideone

Related Images: