ePig

Андрей и Аня разрабатывают новую P2P сеть для обмена файлами, они назвали свою сеть ePig. В этой задаче вам предлагается смоделировать работу сети при распространении одного большого файла.

Пусть сетью пользуются n клиентов, пронумерованных от 1 до n. Исходно файл целиком доступен на клиенте номер 1. Остальные клиенты хотели бы получить этот файл. Для оптимизации процесса файл разбивается на k идентичных фрагментов, пронумерованных от 1 до k. Передача файла состоит из нескольких раундов. Каждый раунд занимает одну минуту, за время раунда каждый клиент может получить ровно один фрагмент и/или передать ровно один фрагмент. После того как клиент скачивает фрагмент файла, он может раздавать его другим клиентам.

Перед каждым раундом каждый клиент решает, какой фрагмент он будет запрашивать. Клиент запрашивает фрагмент, который предоставляется наименьшим числом клиентов (разумеется, кроме тех фрагментов, которые у него уже есть). Если таких фрагментов несколько, он выбирает тот, у которого минимальный номер.

После этого клиенты делают запросы на фрагменты. Каждый клиент выбирает другого клиента, у которого он запрашивает выбранный фрагмент. Если несколько клиентов предоставляют необходимый фрагмент, то выбирается клиент, у которого минимальное количество предоставляемых им фрагментов. Если и таких клиентов несколько, выбирается клиент с минимальным номером.

Каждый клиент рассматривает все запросы, которые к нему поступили, и выбирает один их них. Клиент X удовлетворяет тот из запросов, который приходит от самого ценного клиента. Ценность клиента определяется количеством фрагментов, которые клиент X получал от него ранее. Если имеется несколько клиентов с одинаковой ценностью, то фрагмент отдается тому из клиентов, у которого перед раундом имеется минимальное количество фрагментов. Если и таких клиентов несколько, то фрагмент отдается клиенту с минимальным номером.

После того, как выбрано, какие запросы будут удовлетворены, начинается раунд. Клиенты, запросы которых были отклонены, ничего не скачивают в этот раунд, а остальные клиенты скачивают запрошенные фрагменты. После этого начинается новый раунд, и т. д.

По заданным n и k для каждого клиента определите число раундов, которое потребуется, чтобы он получил файл целиком.

Входные данные

Входной файл INPUT.TXT содержит два целых числа: n и k (2 ≤ n ≤ 100, 1 ≤ k ≤ 200).

Выходные данные

В выходной файл OUTPUT.TXT выведите для каждого клиента кроме первого одно число – количество раундов перед тем, как он скачает файл целиком.

Пример

Пояснение

Распространение файла в данном случае происходит следующим образом: в первом раунде клиенты 2 и 3 запрашивают фрагмент 1 от клиента 1. Удовлетворяется запрос от клиента 2. После этого клиенты 2 и 3 запрашивают фрагмент 2 у клиента 1. Удовлетворяется клиент 3. Наконец в третьем раунде клиент 2 запрашивает фрагмент 2 у клиента 3, а клиент 3 запрашивает фрагмент 1 у клиента 2, оба запроса удовлетворяются и у каждого теперь есть целый файл.

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]