Старые олимпиады: 2007 - интернет - E
Если мне не изменяет память, тут закончилась первая порция задач
Лесной интернет
Ограничение по времени: 2 сек.
Ограничение по времени для Java: 4 сек.
Ограничение по памяти: 64 Мб
Предыстория
...Белый Кролик и Сферический Лев сидели за празднично накрытым столом и пили чай. Еще бы - у них был отличный повод для празднования - в 3 часа ночи наконец-то выложили новые задачи на acm.ksu.ru. Кроме того, Сферический Лев прибыл в Двоичный Лес с дипломатическим визитом из Троичных Джунглей - предстояла встреча глав Союза 2-3-4-лесов - и друзья отмечали его приезд в Лес.
Белый Кролик и Сферический Лев были знакомы уже давно. Первый раз они встретились на крокете у Королевы. Кролик был тогда и в Двоичном Лесу известен только немногим, а Лев уже тогда был знаменит - еще бы, ведь первым в космосе побывал именно Сферический Лев! Тогда они и познакомились.
С тех пор многое изменилось - любой в Двоичном Лесу знал Кролика, да и за пределами Леса многие о нем слышали. А вот известность Льва уменьшилась. Лев так и остался единственным космонавтом - в космосе не было найдено ничего интересного. Космодром потихоньку приходил в упадок. Было решено обратить больше внимания социальной политике и финансирование космической программы совсем прекратилось. Конечно, Льва все еще узнавали - единственный космонавт все-таки. Но львята уже не приклеивали его фотографии у себя над кроватью и уже давно звери не просили автографов, когда Лев выходил на улицу. Времена поменялись, появились новые кумиры.
Лев ко всему этому относился философски - ему и раньше не нравилась его известность. Он хотел выполнять свою работу хорошо и не хотел, чтобы известность мешала этому. Вот и сейчас, неторопливо беседуя с Кроликом, он чувствовал себя лучше, чем во время официальных церемоний.
Чаепитие шло прекрасно. Чай был замечательным, конфеты - сладкими, варенье - вкусным. Ни Кролик, ни Лев не могли бы сказать, почему им так уютно. Или чай, приготовленный Белой Крольчихой по фамильному рецепту, вышел особенно удачно, или влиял сам Лев (как установили ученые Троичных Джунглей, он испускал сферически-симметричное поле идеальности, в котором все происходило просто идеально), но друзья выпили по 10 кружек чая и все не могли остановиться.
Кролик отвернулся - хотел взять новую банку варенья. Повернулся обратно - и банка выпала из его ослабевших лапок. Лев исчез.
- Ах мои усики, ах мои лапки! - воскликнул Белый Кролик. - Что я скажу Герцогине?! Такая неприятность! Такой ужас!
Тут его взгляд упал на телефон. Белый Кролик набрал 10-значный номер Черного Кролика.
- Такое несчастье! Такой ужас! Ах мои бедные лапки!
- Что случилось, кузен? Что за беда стряслась? - спросил Черный Кролик спокойным голосом.
- Пропал Лев! ТОТ САМЫЙ ЛЕВ - космонавт! Помнишь, он заходил к нам на чай? Такой скандал! Что я скажу Королеве? Она велит срубить мне голову!
- Да, да помню. Успокойся. Никому сейчас голов не рубят. Лев что, совсем пропал? И ничего не осталось?
- Ничего.
- Как, совсем-совсем ничего?
- Нет, просто ничего - вот, тут лежит.
- Ну... Может Лев просто куда-нибудь ушел? Вспомнил что-то важное и ушел, не попрощавшись? Просто подожди его - он обязательно вернется!
- Не знаю, не знаю... Лучше я поищу его сам!..
Условие задачи
Двоичный Лес - очень высокотехнологичный лес. У каждого его обитателя есть компьютер, ноутбук или хотя бы калькулятор.
А вот интернета в Двоичном Лесу не было... До недавних пор.
В последний месяц все почтальоны Двоичного Леса просто сбились с ног, доставляя письма с просьбами подключить интернет. Все письма были подписаны известными бобрами. Куда только эти письма не были адресованы! Одно из них пришло и Белому Кролику. Белый Кролик решил помочь бедным бобрам, не имеющим доступа к интернету. К его предложению подключить Двоичный Лес к интернету прислушались, и вот - решение о подключении утверждено!
Для управления сетью был создан Центр Интернета. Его директором жители Двоичного Леса единогласно избрали Белого Кролика, как самого умного. Белый Кролик долго отказывался, ссылаясь на то, что он по горло загружен делом о пропаже льва, но его все же удалось уговорить.
На следующий же день после выборов оказалось, что жители Двоичного Леса уже выбрали себе IP-адреса и не хотят их менять без особых причин. Но Кролик должен был соединить все компьютеры в сеть! Ему срочно было нужно знать все IP-адреса.
Поскольку Белый Кролик был умным, он решил просто составить список IP-адресов. А так как он был не просто умным, а очень умным, он поручил составлять список своим заместителям (в Двоичном Лесу, по традиции, каждый чиновник имеет двух заместителей - не больше и не меньше). Те, в свою очередь, поручили это дело своим заместителям, и так далее. И
так как каждый заместитель, выполнив свою часть работы, бежал отчитываться перед своим начальником, вскоре у Кролика был очень большой и очень неупорядоченный список.
Белый Кролик очень любит порядок. Он просит вас написать программу, которая упорядочила бы его список, поскольку он должен отыскать Льва и у него нет времени сортировать список вручную.
Формат входных данных
Первая строка содержит число N (1<=N<=1000000) жителей Двоичного Леса. Следующие N строк содержат IP-адреса жителей, по одному в строке
Формат выходных данных
Отсортированный по неубыванию список IP-адресов, по одному IP-адресу в строке
Лесной интернет
Ограничение по времени: 2 сек.
Ограничение по времени для Java: 4 сек.
Ограничение по памяти: 64 Мб
Предыстория
...Белый Кролик и Сферический Лев сидели за празднично накрытым столом и пили чай. Еще бы - у них был отличный повод для празднования - в 3 часа ночи наконец-то выложили новые задачи на acm.ksu.ru. Кроме того, Сферический Лев прибыл в Двоичный Лес с дипломатическим визитом из Троичных Джунглей - предстояла встреча глав Союза 2-3-4-лесов - и друзья отмечали его приезд в Лес.
Белый Кролик и Сферический Лев были знакомы уже давно. Первый раз они встретились на крокете у Королевы. Кролик был тогда и в Двоичном Лесу известен только немногим, а Лев уже тогда был знаменит - еще бы, ведь первым в космосе побывал именно Сферический Лев! Тогда они и познакомились.
С тех пор многое изменилось - любой в Двоичном Лесу знал Кролика, да и за пределами Леса многие о нем слышали. А вот известность Льва уменьшилась. Лев так и остался единственным космонавтом - в космосе не было найдено ничего интересного. Космодром потихоньку приходил в упадок. Было решено обратить больше внимания социальной политике и финансирование космической программы совсем прекратилось. Конечно, Льва все еще узнавали - единственный космонавт все-таки. Но львята уже не приклеивали его фотографии у себя над кроватью и уже давно звери не просили автографов, когда Лев выходил на улицу. Времена поменялись, появились новые кумиры.
Лев ко всему этому относился философски - ему и раньше не нравилась его известность. Он хотел выполнять свою работу хорошо и не хотел, чтобы известность мешала этому. Вот и сейчас, неторопливо беседуя с Кроликом, он чувствовал себя лучше, чем во время официальных церемоний.
Чаепитие шло прекрасно. Чай был замечательным, конфеты - сладкими, варенье - вкусным. Ни Кролик, ни Лев не могли бы сказать, почему им так уютно. Или чай, приготовленный Белой Крольчихой по фамильному рецепту, вышел особенно удачно, или влиял сам Лев (как установили ученые Троичных Джунглей, он испускал сферически-симметричное поле идеальности, в котором все происходило просто идеально), но друзья выпили по 10 кружек чая и все не могли остановиться.
Кролик отвернулся - хотел взять новую банку варенья. Повернулся обратно - и банка выпала из его ослабевших лапок. Лев исчез.
- Ах мои усики, ах мои лапки! - воскликнул Белый Кролик. - Что я скажу Герцогине?! Такая неприятность! Такой ужас!
Тут его взгляд упал на телефон. Белый Кролик набрал 10-значный номер Черного Кролика.
- Такое несчастье! Такой ужас! Ах мои бедные лапки!
- Что случилось, кузен? Что за беда стряслась? - спросил Черный Кролик спокойным голосом.
- Пропал Лев! ТОТ САМЫЙ ЛЕВ - космонавт! Помнишь, он заходил к нам на чай? Такой скандал! Что я скажу Королеве? Она велит срубить мне голову!
- Да, да помню. Успокойся. Никому сейчас голов не рубят. Лев что, совсем пропал? И ничего не осталось?
- Ничего.
- Как, совсем-совсем ничего?
- Нет, просто ничего - вот, тут лежит.
- Ну... Может Лев просто куда-нибудь ушел? Вспомнил что-то важное и ушел, не попрощавшись? Просто подожди его - он обязательно вернется!
- Не знаю, не знаю... Лучше я поищу его сам!..
Условие задачи
Двоичный Лес - очень высокотехнологичный лес. У каждого его обитателя есть компьютер, ноутбук или хотя бы калькулятор.
А вот интернета в Двоичном Лесу не было... До недавних пор.
В последний месяц все почтальоны Двоичного Леса просто сбились с ног, доставляя письма с просьбами подключить интернет. Все письма были подписаны известными бобрами. Куда только эти письма не были адресованы! Одно из них пришло и Белому Кролику. Белый Кролик решил помочь бедным бобрам, не имеющим доступа к интернету. К его предложению подключить Двоичный Лес к интернету прислушались, и вот - решение о подключении утверждено!
Для управления сетью был создан Центр Интернета. Его директором жители Двоичного Леса единогласно избрали Белого Кролика, как самого умного. Белый Кролик долго отказывался, ссылаясь на то, что он по горло загружен делом о пропаже льва, но его все же удалось уговорить.
На следующий же день после выборов оказалось, что жители Двоичного Леса уже выбрали себе IP-адреса и не хотят их менять без особых причин. Но Кролик должен был соединить все компьютеры в сеть! Ему срочно было нужно знать все IP-адреса.
Поскольку Белый Кролик был умным, он решил просто составить список IP-адресов. А так как он был не просто умным, а очень умным, он поручил составлять список своим заместителям (в Двоичном Лесу, по традиции, каждый чиновник имеет двух заместителей - не больше и не меньше). Те, в свою очередь, поручили это дело своим заместителям, и так далее. И
так как каждый заместитель, выполнив свою часть работы, бежал отчитываться перед своим начальником, вскоре у Кролика был очень большой и очень неупорядоченный список.
Белый Кролик очень любит порядок. Он просит вас написать программу, которая упорядочила бы его список, поскольку он должен отыскать Льва и у него нет времени сортировать список вручную.
Формат входных данных
Первая строка содержит число N (1<=N<=1000000) жителей Двоичного Леса. Следующие N строк содержат IP-адреса жителей, по одному в строке
Формат выходных данных
Отсортированный по неубыванию список IP-адресов, по одному IP-адресу в строке