Kilidli xəzinə#7534
Gəlin m - 1 quldurdan ibarət təsviredici bir qrup nəzərdən keçirək. Şərtə görə bu qrup qapını aça bilməməlidir. Yəni bu m - 1 quldurun heç birinin açarı olmadığı ən azı bir qıfıl mövcud olmalıdır.
Beləliklə, ölçüsü m - 1 olan hər bir quldur alt dəsti üçün heç birindən açarı olmayan xüsusi qıfıl olmalıdır.
Açarların bölüşdürülməsi üçün quruluşçu alqoritmi nəzərdən keçirək:
m - 1 ölçülü hər bir quldur alt dəsti üçün bir qıfıl yaradılır.
Bu qıfılın açarları qalan quldurlara paylanır, yəni açarları n - (m - 1) = n - m + 1 insan alır.
Alqoritm düzgündür, çünki:
m - 1 nəfərlik qrup üçün öz qıfıllarına heç kimdə açar yoxdur. Beləliklə, qapı açılmır.
nəfərlik qrupu nəzərdən keçirək. Hər hansı bir qıfıl götürək. Bu yalnız tərkibində m - 1 quldur olan konkret təsviredici qrup üçün "qadağandır". nəfərlik qrupda bu quruluşa daxil olmayan kimsə mütləq var. Deməli, qrupun hər bir qıfılın açarı var.
Lazım olan minimal qıfıl sayı C_n^{m-1} - elementlərindən m - 1 ölçülü alt dəstlərin sayına bərabərdir.
Misal
Tutaq ki, n = 4 quldur var.
m = 1 üçün qıfıl sayı C_4^0 = 1.
Qıfıl | Alt Dəst | Açarlar |
1 | {} | 1, 2, 3, 4 |
Hər quldura tək qıfılın açarı verilməlidir:
m = 2 üçün qıfıl sayı C_4^1 = 4.
Qıfıl | Alt Dəst | Açarlar |
1 | {1} | 2, 3, 4 |
2 | {2} | 1, 3, 4 |
3 | {3} | 1, 2, 4 |
4 | {4} | 1, 2, 3 |
Qıfılların quldurlar arasında optimal paylanması belədir:
Hər hansı iki quldur bütün dörd qıfılı aça bilər və xəzinəni götürə bilər.
m = 3 üçün qıfıl sayı C_4^2 = 6.
Qıfıl | Alt Dəst | Açarlar |
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 |
Qıfılların quldurlar arasında optimal paylanması belədir:
İki quldurun yalnız bir qıfılın açarı çatışmazlığı olacaq. Hər hansı üç quldur bütün altı qıfılı aça bilər və xəzinəni götürə bilər.
m = 4 üçün qıfıl sayı C_4^3 = 4.
Qıfıl | Alt Dəst | Açarlar |
1 | {1, 2, 3} | 4 |
2 | {1, 2, 4} | 3 |
3 | {1, 3, 4} | 2 |
4 | {2, 3, 4} | 1 |
Qıfılların quldurlar arasında optimal paylanması belədir:
Bütün qıfılı açmaq üçün hər bir quldur özünəməxsus açarını gətirməlidir.
n = 5, m = 3 halını nəzərdən keçirək. Qıfıl sayı C_5^2 = 10.
Qıfıl | Alt Dəst | Açarlar | Qıfıl | Alt Dəst | Açarlar |
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 |
Qıfılların quldurlar arasında optimal paylanması belədir:
Alqoritmin İcrası
cnk[n][k] hüceyrələrində binom koeffisiyentlərinin dəyərləri C_n^k hesablanır.
#define MAX 31
long long cnk[MAX][MAX];FillCnk funksiyası massivini binom koeffisiyentlərinin dəyərləri ilə doldurur.
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];
}Proqramın əsas hissəsi. FillCnk funksiyasını çağırırıq.
FillCnk();Testlərin sayını oxuyun.
scanf("%d",&tests);
while (tests--)
{Cari test üçün giriş məlumatlarını oxuyun və cavab yazdırın.
scanf("%d %d",&n,&m);
printf("%lld\n",cnk[n][m-1]);
}