Замкнене скарб#7534
Розглянемо довільну групу з m - 1 бандита. За умовою вона не повинна відкрити двері. Тобто має існувати хоча б один замок, для якого ні в кого з цих m - 1 бандитів немає ключа.
Таким чином, для кожного підмножини бандитів розміру m - 1 має існувати свій замок, ключі від якого не видані нікому з них.
Розглянемо конструктивний алгоритм розподілу ключів:
Для кожного підмножини бандитів розміру m - 1 створимо один замок.
Ключі від цього замка видамо всім іншим бандитам, тобто ключі отримують n - (m - 1) = n - m + 1 людей.
Алгоритм коректний, тому що:
Для групи з m - 1 людей для їх власного замка ні у кого немає ключа. Тому двері не відкриються.
Розглянемо групу з людей. Візьмемо будь-який замок. Він "заборонений" тільки для одного конкретного набору з m - 1 бандитів. У групі з людей обов'язково є хтось поза цим набором. Отже, у групи є ключ від кожного замка.
Мінімальна кількість необхідних замків дорівнює C_n^{m-1} — кількості підмножин з елементів розміру m - 1.
Приклад
Нехай є n = 4 бандита.
При m = 1 кількість замків дорівнює C_4^0 = 1.
Замок | Підмножина | Ключі |
1 | {} | 1, 2, 3, 4 |
Кожному бандиту слід дати ключ від єдиного замка:
При m = 2 кількість замків дорівнює C_4^1 = 4.
Замок | Підмножина | Ключі |
1 | {1} | 2, 3, 4 |
2 | {2} | 1, 3, 4 |
3 | {3} | 1, 2, 4 |
4 | {4} | 1, 2, 3 |
Оптимальний розподіл замків серед бандитів наступний:
Будь-які два бандита зможуть відкрити всі чотири замки і забрати скарб.
При m = 3 кількість замків дорівнює C_4^2 = 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 кількість замків дорівнює C_4^3 = 4.
Замок | Підмножина | Ключі |
1 | {1, 2, 3} | 4 |
2 | {1, 2, 4} | 3 |
3 | {1, 3, 4} | 2 |
4 | {2, 3, 4} | 1 |
Оптимальний розподіл замків серед бандитів наступний:
Для того щоб відкрити всі замки, кожен бандит повинен принести свій єдиний унікальний ключ.
Розглянемо випадок n = 5, m = 3. Кількість замків дорівнює C_5^2 = 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] обчислюємо значення біноміальних коефіцієнтів C_n^k.
#define MAX 31
long long cnk[MAX][MAX];Функція FillCnk заповнює масив значеннями біноміальних коефіцієнтів.
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();Зчитуємо кількість тестів .
scanf("%d",&tests);
while (tests--)
{Зчитуємо вхідні дані чергового тесту і виводимо відповідь.
scanf("%d %d",&n,&m);
printf("%lld\n",cnk[n][m-1]);
}