Task 89_1. Сейф
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 сотрудников может открыть все замки сейфа.
Реализация:
- @tvolf, PHP
https://gist.github.com/tvolf/e410563a8b7e8243495e040caa8bfb6a
2. @mikhail_01, Python
https://gist.github.com/mikhail-01/2f2fe6778368f80553b9e2dae188447d
3. @jinxonik, Python
https://gist.github.com/jin-x/75609a6eff91e25479ff99b1cf288019
Test:
https://repl.it/@jin_x/UniLecs-89
4. @pavelm12, Go
https://gist.github.com/pavelm12/3cb90b5891a7f9487fdb8655a086a836
5. @LostInKadath, Python
https://gist.github.com/LostInKadath/aa793255d8e257f61fe4812751eb24b6
6. @dbond762, Go
https://gist.github.com/dbond762/0c9592c208fb54e049b76807f1f15c12
Test: