Матч 391, Ключи в коробке (KeysInBoxes)

Дивизион 1, Уровень 2

Имеется n коробок, пронумерованных с 1 до n, а также n ключей, пронумерованных с 1 до n. i - ый ключ может открыть только i - ую коробку. Произвольным образом расположим каждый ключ в отдельную коробку, после чего закроем все коробки. Имеются m бомб, каждой из которых можно открыть одну коробку. Открыв при помощи бомбы коробку и достав из нее ключ, возможно, этим ключом можно открыть еще одну коробку (если этот ключ не от коробки, в которой он лежал). Таким образом продолжаем процесс подрыва коробок, доставания ключей и открывание коробок извлеченными ключами.

В задаче необходимо найти вероятность того, что можно открыть все коробки. Возвращаемое значение является строкой “A/B”, содержащую искомую вероятность в виде дроби. Значения A и B являются натуральными числами, не содержат ведущих нулей и являются взаимно простыми.

Класс: KeysInBoxes

Метод: string getAllKeys(int n, int m)

Ограничения: 1 £ n £ 20, 1 £ m £ n.

Вход. Целые числа n и m.

Выход. Строка, содержащая вероятность того, что можно открыть все коробки.

Пример входа

n	m
2	1
3	1
4	2

Пример выхода

“1/2”

“1/3”

“17/24”

РЕШЕНИЕ

математика

Взорвав бомбой коробку, можно достать ключ из другой коробки. Ключом из другой коробки можно открыть следующую. И так далее, пока не будет вскрыта коробка, в которой лежит ключ от первой коробки. Одной бомбой можно открыть такое множество коробок, которые образуют цикл в перестановке ключей. Количество циклов в перестановке ключей равно числу бомб, необходимых для открытия всех коробок.

Например, пусть ключи образуют перестановку (2, 1, 3, 5, 4) = (12)(345). Она состоит из двух циклов, поэтому для извлечения всех ключей требуется две бомбы.

Количество перестановок из n элементов, имеющих k циклов, равно числу Стирлинга первого рода s(n, k), которые вычисляются по рекуррентной формуле:

s(n, k) = s(n – 1, k – 1) + (n – 1) * s(n – 1, k)

Искомая вероятность равна количеству разных перестановок, состоящих из не более чем m циклов, деленная на количество всех перестановок n!.

В массиве s[21][21] вычисляются числа Стирлинга, причем s[n][k] = s(n, k). В переменной a вычисляется сумма s(n, 1) + s(n, 2) + … + s(n, m), в переменной b – число перестановок n!. Возвращаем результат в виде строки “a/b”, предварительно сократив числитель и знаменатель на их наибольший общий делитель.

ПРОГРАММА

#include <cstdio>

#include <string>

#include <memory>

using namespace std;

long long s[21][21];

long long gcd(long long a, long long b)

{

return (!b) ? a : gcd(b,a % b);

}

class KeysInBoxes

{

public:

string getAllKeys(int n, int m)

{

int i, k;

long long a, b, d;

char str[50];

memset(s,0,sizeof(s));

s[0][0] = 1;

for(i = 1; i <= n; i++)

for(k = 1; k <= n; k++)

s[i][k] = s[i-1][k-1] + (i-1) * s[i-1][k];

// s(n,1) + s(n,2) + ... + s(n,m)

for (a = 0, i = 1; i<= m; i++) a += s[n][i];

for(b = i = 1; i <= n; i++) b *= i; // n!

d = gcd(a,b);

a /= d; b /= d;

sprintf(str,"%lld/%lld",a,b);

return (string)str;

}

};