Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

Задача А. Глоссарий

Задачу добавил: alef

Успешно сдано решений: 28

Время на тест 4 с, память 256 Мб


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

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

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

Формат входного файла input.txt

Первая строка — целое число N (1 N 1000) — количество терминов в глоссарии

Каждая из следующих N строк содержит последовательность номеров страниц через пробел, на которые в описании термина с соответствующим номером есть гиперссылки (первая строка из этих N строк описывает первый термин, вторая — второй и т.д.). Завершается последовательность нулем. Номера страниц — целые положительные числа.

Номера страниц в последовательности могут повторяться (другой термин может встречаться в описании несколько раз). Также в последовательности может присутствовать номер страницы с самим термином (для перемещения между фрагментами страницы) — однако, поскольку эта гиперссылка не исходит с другой страницы, учитывать ее не нужно. Гарантируется, что циклических ссылок нет. Также гарантируется, что входной файл не превышает 4 Мб.

Формат выходного файла output.txt

Первая строка — целое число M, количество этапов, которое потребуется Кеше на изучение всего глоссария.

Вторая строка содержит M чисел через пробел. Каждое из чисел — количество терминов, которое Кеша изучил на соответствюущем этапе.

Пример входного файла

10

4 2 6 8 2 5 1 2 4 2 1 9 0

3 8 2 8 3 3 9 2 4 0

10 5 0

3 7 3 3 7 4 4 7 0

5 5 0

5 8 5 0

3 10 9 3 9 3 7 9 0

0

3 6 8 10 9 9 0

8 6 6 8 0

Пример выходного файла

4

5 1 3 1

Задача А.

Сдать задачу

Задать вопрос жюри по этой задаче