Task 89. Сейф
UniLecsЗадача: В банке у N сотрудников есть доступ к секретному сейфу. На этом сейфе есть несколько замков. Каждый замок может иметь до N ключей, распределенных среди некоторого подмножества сотрудников банка, имеющих доступ к сейфу. Группа сотрудников может открыть замок, только если кто-то в группе имеет ключ к этому замку.
Банк хочет сделать так, что открыть этот сейф можно только, если этого захотят не менее M сотрудников.
По имеющимся значениям N, M определить такое наименьшее кол-во замков, что если ключи от них правильно распределить среди сотрудников банка, то каждая группа состоящая из не менее чем M сотрудников сможет открыть все замки сейфа, но никакая группа из меньшего числа сотрудников открыть все замки не сможет.
Входные данные: N, M; где N меньше или равно 30, M меньше или равно N.
Вывод: минимальное кол-во необходимых замков.
Пример: если N = 3, M = 2, то достаточно 3х замков:
- ключи от 1го замка имеют 1й и 2й сотрудник
- ключи от 2го замка имеют 1й и 3й сотрудник
- ключи от 3го замка имеют 2й и 3й сотрудник.
Ни один из сотрудников не может открыть все замки самостоятельно, но любая группа из 2 сотрудников может открыть все замки сейфа.
Идея: по определнию биномиального коэффициента, ответов на задачу будет значение Cn(m-1). Давайте рассмотрим это на нескольких примерах:
Пусть N = 4.
- Для M = 1 кол-во замков необходимо C(4)(1-0) = 1. Каждому сотруднику просто нужно дать ключ от единственного замка на сейфе, тогда любой из них сможет открыть сейф.
- Для M = 2 кол-во замков необходимо C(4)(2-1) = 4. Смотри рис.:
Любые 2 сотрудника смогут открыть все 4 замка и открыть сейф.
- Для M = 3 кол-во замков необходимо C(4)(3-1)= 6. Смотри рис.:
У любых 2х сотрудников не будет хватать ключа всего лишь от одного замка. Любые 3 сотрудника смогут открыть все шесть замков и открыть сейф.
- При M = 4 кол-во замков необходимо С(4)(4-1) = 4. 1й сотрудник получит ключ от 1го замка, 2й сотрудник получит ключ от 2го, 3й от 3го замка и 4й сотрудник от 4го замка.
Напоследок, рассмотрим случай для N = 5, M = 3. В этом случае кол-во замков необходимо C(5)(3-1) = 10. Смотри рис.:
Реализация:
https://gist.github.com/unilecs/0a3a5c27a44628a64d04c9385018bd34
Test: