Корпорация (25 баллов)
Задачу добавил: alef
Успешно сдано решений: 33
Сгруктура некоторой корпорации такова, что каждый служащий, кроме служащих нижнего звена, является непосредственным начальником не менее чем одного другого служащего (возможно, служащего нижнего звена). Во главе компании стоит Президент, которому подчиняются либо непосредственно, либо по должностной иерархии все остальные служащие. Каждый служащий (разумеется, кроме Президента) имеет одного непосредственного начальника. Все служащие в этой структуре имеют индивидуальные номера от 1 до N (2 < N < 10000). Пример описания такой структуры приведен на рисунке, где сотрудник с номером 3 является Президентом и непосредственным начальником сотрудников с номерами 1 и 4, а сотрудник с номером 4 является непосредственным начальником сотрудника с номером 2. Структура корпорации является корпоративной тайной и строго охраняется.
По итогам года Президент компании, довольный работой всех служащих нижнего звена, решил направить в адрес каждого их них благодарственное письмо. Передача писем этим служащим осуществлялась через их непосредственных начальников с использованием сайта корпорации. В результате этого каждый служащий нижнего звена получил благодарственное письмо от Президента компании, но на сайте оказался доступным перечень всех путей следования писем от Президента до каждого служащего нижнего звена.
Требуется написать программу, которая по сведениям, доступным на сайте, восстанавливает структуру корпорации.
Технические требования:
Имя входного файла: INPUT.TXT
Имя выходного файла: OUTPUT.TXT
Ограничение по времени тестирования: 1 секунда на один тест
Формат входных данных:
Во входном файле INPUT.TXT на одной строке содержится последовательность чисел, определяющая все пути следования писем от Президента до каждого служащего нижнего звена. Каждый путь описывается соответствующими номерами служащих, разделенных пробелами. Например, для приведенной на рисунке структуры таких путей будет два: 3-4-2 и 3-1.Пути в последовательности указываются в произвольном порядке. Гарантируется, что заданная последовательность корректна, то есть существует корпорация, ей соответствующая.
Формат выходных данных;
Выходной файл OUTPUT.TXT должен содержать N строк. В каждой i-ой строке (1 < i < N) должны располагаться в порядке увеличения номеров все номера служащих, непосредственно подчиненных i-ому служащему. Все числа в строке разделены пробелом. Последним в каждой строке должно быть число 0. Если решений несколько, необходимо вывести любое.
Пример файлов входных и выходных данных:
|
INPUT.TXT |
OUTPUT.TXT |
| 3 4 2 3 1 |
0 0 1 4 0 2 0 |