1572. Купоны

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

Вход. Каждая строка содержит натуральное число n, 1 ≤ n ≤ 33, количество типов купонов.

Выход. Для каждого значения n вывести ожидаемое число коробок, которое надо открыть, чтобы иметь купоны всех типов. Если искомое число коробок целое, то вывести его. Если результат не целый, то вывести его целую часть, пробел, и дробную часть как показано в примере. Дробную часть результата представлять несократимой дробью. Лишних пробелов в конце строк выводить не следует.

Пример входа	Пример выхода
2 5 17	3    5 11 --    12    340463 58 ------    720720

РЕШЕНИЕ

вероятность

Анализ алгоритма

Предположим, что у Вас уже имеется n – k разных купонов. Обозначим через a_k ожидаемое количество коробок, которое следует открыть для того чтобы собрать недостающие k разных купонов. С вероятностью (n – k) / n купон в следующей коробке будет бесполезным, а с вероятностью k / n он будет того типа, которого у Вас еще нет. Имеем соотношение:

a_k = (1 + a_k) * + (1 + a_k-1) * ,

a₀ = 0

Раскроем скобки и выразим a_k через a_k-1:

a_k = + a_k-1

Рекуррентность можно расписать в виде:

a_k = + a_k-1 = + + a_k-2 = + + + a_k-3 = … =

= + + + … + + a₀ = n *

Ответом задачи будет значение a_n – ожидаемое количество коробок, которое следует открыть для того чтобы собрать недостающие n разных купонов:

a_n = n *

Для вывода результата в требуемом формате остается реализовать суммирование при помощи рациональных чисел. Для сокращения дробей будем использовать функцию gcd, вычисляющую наибольший общий делитель.

Пример

Вычислим значения a₂ и a₃.

a₂ = 2 * (1 + ) = 3,

a₃ = 3 * (1 + + ) = 3 + + 1 = .

Реализация алгоритма

В структуре RatNumber храним рациональное число: числитель x и знаменатель y.

struct RatNumber

{

long long x,y;

} c, temp;

Сложение рациональных чисел a и b. Возвращаемая сумма является несократимой дробью. Функция gcd вычисляет наибольший общий делитель.

struct RatNumber add(struct RatNumber a,struct RatNumber b)

{

struct RatNumber res;

res.x = a.x*b.y + a.y*b.x;

res.y = a.y * b.y;

d = gcd(res.x,res.y);

if (d)

{

res.x /= d;res.y /= d;

}

return res;

}

Основной цикл программы. Читаем входное значение n.

while(scanf("%d",&n) == 1)

{

c.x = 0; c.y = 1; temp.x = 1;

Вычисление суммы c = n *

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

{

temp.y = i;

c = add(c,temp);

}

c.x = n * c.x;

d = gcd(c.x,c.y);

c.x /= d; c.y /= d;

d = c.x / c.y;

c.x -= d * c.y;

Переменная d содержит целую часть результата c. Если знаменатель результата равен 1, то выводим только числитель. Иначе форматируем вывод ответа, как показано в условии задачи. Функция digits находит количество знаков числа x.

if (c.y > 1)

{

for(i = 0; i <= digits(d); i++) printf(" ");

printf("%lld\n",c.x);

printf("%lld ",d);

for(i = 0; i < digits(c.y); i++) printf("-"); printf("\n");

for(i = 0; i <= digits(d); i++) printf(" ");

printf("%lld\n",c.y);

}

else printf("%lld\n",d);

}