Кажется, монитор будет здесь.

Как уже упоминалось, мы живем в районе под названием Ikebukuro. Недалеко от станции метро находится большой торговый центр Sunshine 60. На верхнем этаже этого небоскреба -- небольшой зоопарк и большой аквариум. Туда с Виталиком мы и отправились. Sunshine 60 мы нашли без проблем. С некоторым трудом отыскали путь на самый верх, однако стоимость посещения аквариума приохладила наш пыл. Опечаленные мы поехали вниз, но по пути передумали и отправились на поиски обзорной площадки. Так как с этажа аквариума выходом не было, мы вышли на этаж ниже. Странные ощущения охватывают, когда спускаешься ниже всего на один этаж -- а там тишина и полный покой. Ни души. С некоторое время мы бродили по пустому этажу, полному странных офисов (некоторые были открыты). Нашли пожарную лестницу, которая вела наверх, куда мы и отправились. Поднявшись выше по ней, и пройдя пару дверей, мы обнаружили еще один лифт, который вел на 12-й этаж (хотя здание, утверждается, 11-этажное). Там, случайно заметили приоткрытую дверь, заглянув в которую, я обнаружил ... аквариум. Одна нога здесь, другая там!
Аквариум на самом деле это серия аквариумов: змей, черепахи, медузы, рыбы всех размеров и форм, скаты, морские котики. Понравилось. Небольшое неудобство доставило то, что вышли мы где-то в конце экспозиции, и, следовательно, двигались по направлению ко входу -- то есть навстречу потоку японцев и японочек. К сожалению, фотоаппарата с собой не было. Когда будем проникать в секретную библиотеку главного храма -- обязательно возьмем.

С 12 по 25 марта в этом журнале нами и компанией Mail.Ru будет проводится очередной ежегодный чемпионат по программированию для студентов и профессионалов.

В воскресенье, 11 марта, будет официально открыта регистрация (и открыта для тестирования пробная задача).
С понедельника 12 марта по воскресенье 18 марта включительно будет публиковаться по одной задаче в порядке возрастания сложности.

Уточнённые правила чемпионата будут опубликованы в воскресенье, 11 марта.

А ведь сегодня ночью (для меня ночью, по крайней мере) - финал.
Судя по расписанию контест начнется в 8:00 - 8:30 по токийскому времени, по московскому, соответственно, в 2:00 - 2:30.
(вычисления сделаны при помощи www.timeanddate.com/worldclock/)
Официальный сайт - icpc.baylor.edu/icpc/finals.
По ходу соревнования там будет ссылка на текщие результаты.
Однако, судя по опыту прошлых лет, правильная ссылка появится там не сразу (в пошлом году через 1 час после начала), а результаты будут обновляться не очень часто - где-то раз в 10 минут.
Также я надеюсь что, информацию о ходе соревнований нам будут поставлять тренеры и зрители через Internet - в этом случае она будет отображена либо здесь, либо на сайтах, ссылки на которые я дам позже.

В этом году наша делегация отбывает из Саратова 7 марта, то есть, уже завтра.

Состав команды: Алексей Климов, Виталий Гольдштейн, Сергей Назаров.
Тренер: Мирзаянов Михаил.
Руководитель: Фёдорова Антонина Гавриловна.

Жюри мини-чемпионата приняло решение не учитывать неудачные подходы с ошибками компиляции при финальном подсчете баллов. Таким образом, баллы за решение начисляются следующим образом:
max(100 - 5 * (попытки - 1), 50) - за полное решение
max(100 - 5 * (попытки - 1), 50) * долю пройденных / 2 - за неполное,
где в число попыток НЕ включаются попытки с результатом compilation error.

Сегодня мы переехали в Hilton Tokyo Bay Hotel. Поскольку выселили нас в 10 утра, то мы отправились в метро и доехали до района Tokyo Bay. Заселения в 15 часов ждать было долго, мы сдали вещи и отправились гулять по побережью.

Вид моря отличный, но пляжей нет, и даже просто спуститься к воде - проблема. Но не для нас В) Михаил Расихович даже искупался.

Несмотря на волнорезы, море очень сильно шумит. Заметив на противоположном берегу залива гору в снегах и облаках В) мы решили, что это Фудзияма. Факт проверяется В) Пока мы гуляли, вышло солнышко, температура поднялась выше 15 градусов.

По возвращении мы встретили Билла Пучера, который встретил нас очень радушно и со словами благодарности за свой визит в Саратов. Далее мы прошли официальные части регистрации - очень напоминает паспортный контроль В) и поужинали.

Теперь нам пора спать...

Финальную расстановку комманд вместе с числом решенных задач и количеством набранного пенальти можно увидеть здесь.

Вчера вечером мы были в Асакусе - район старых храмов. Поскольку дело было вечером, сумели посмотреть лишь храмы снаружи с подсветкой.

Сегодня были в Камакуре. Доехать туда нам помогли двое дружелюбных японцев по имени Masaya и Noriko.

Там побывали в храмах и музеях, а также посмотрели большого Будду.

Да и вообще виды тут красивые:

Связная структура данных "дерево" предполагает наличие вершин и связей между ними. Циклов в дереве нет. Одна вершина дерева называется корнем, все вершины достижимы из нее. В этой задаче корнем всегда будет вершина 1.
На одной из вершин дерева находится белка. За один прыжок она может перепрыгнуть на любую вершину, находящуюся от нее на расстоянии не более чем K. Расстоянием называется количество ребер на пути из одной вершины до другой. Величину K будем называть прыгучестью белки.
Например, для дерева на рисунке, если K = 2 и белка находится в вершине 5, то белка может перепрыгнуть на вершины 1, 2, 3, 7, 8 и 9.

Первоначально, белка находится в вершине 1. Она хочет совершить последовательность прыжков, чтобы побывать на каждой вершине дерева, не посещая никакую два или более раза. Какой наименьшей прыгучестью должна обладать белка, чтобы совершить такое путешествие? Найдите и сам маршрут.
Все деревья в этой задаче удовлетворяют интересному свойству: для каждой вершины количество ее сыновей отлично от 1. Сыновьями вершины называются такие смежные с ней вершины, которые расположены дальше от корня, чем она сама.
Входные данные.
В первой строке входного файла записано целое число N (3 ≤ N ≤ 30000), где N - количество вершин в дереве. Далее следует строка, содержащая N - 1 число, описывающее дерево. Первое из этих чисел содержит номер вершины, смежной со второй, но расположенной ближе к корню, чем она сама. Второе из чисел содержит подобную информацию для третьей вершины, и т.д. Таким образом, i-ое число содержит подобную информацию для вершины i +1.
Выходные данные.
В первую строку выведите наименьшую возможную прыгучесть белки. Во вторую строку выведите последовательность номеров вершин в порядке посещения. Последовательность следует начинать с корня. Если существует несколько решений, выведите любое.
Примеры:

	input.txt	output.txt
Пример #1	9 1 5 2 1 2 1 5 5	2 1 3 8 9 5 7 2 4 6
Пример #2	12 1 2 3 2 2 6 5 6 1 3 5	3 1 2 4 11 3 7 9 5 8 12 6 10

Ограничение времени для 32-х битного компилятора: 1 секунда
Ограничение времени для 16-и битного компилятора: 8 секунд
Ограничение памяти: 64 мегабайта
Входной файл: input.txt
Выходной файл: output.txt
Про компиляторы можно почитать здесь

Хотя в названии и присутствует слово "программирование", это всё-таки чемпионат мира. Многоуровневое спортивное состязание, в котором присуждают первые места и дают медали.
Соревнования, в которых принимают участие 5606 команд со всего мира.
Про которые мы вам здесь и расскажем.

В программе также:
- экскурсии по месту проведения финала, городу Сан-Антонио (штат Техас);
- история чемпионатов и олимпиад по программированию;
- конкурс для читателей - мини-соревнование по программированию.

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

Входной файл
В первой строке записано натуральное число N (1 <= N <= 102) - количество клеток в доске. В доске всегда присутствуют первые N клеток, то есть N клеток с наименьшими номерами. В следующей строке записано
N / 2 чисел - номера клеток, с которых Кирилл делал ходы. В третьей строке записано натуральное число K
(0 < K <= 20) - количество клеток, на которое может пойти ладья. В четвертой строке записано K натуральных чисел (непревосходящих 100) - стоимость (в конфетах) движения ладьи на 1, 2 и так далее клеток.

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

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

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

Пояснение:



Ограничение времени: 1 секунда
Ограничение памяти: 64 мегабайта
Входной файл: input.txt
Выходной файл: output.txt

Итак, наш чемпионат завершен и пора подводить его итоги, но прежде я хотел бы поблагодарить тех, благодаря кому прошел этот чемпионат:

• компанию Mail.Ru и директора по маркетингу и PR Mail.Ru Анну Артамонову за хостинг, спонсорство, и призы;
• Павла Комкова aka Stingray за его тестирующую систему и управление ей;
• Алексея Климова за помощь в управлении тестирующей системой;
• тренера нашей команды Михаила Мирзаянова за задачи;
• и, конечно, участников за активное участи в нашем чемпионате.

Итак, верхняя 5-ка лидеров, каждый из которых решил все 8 задач, выглядит следующим образом:

• 1-е место: Роман Милючихин (miluchihin@mail.ru) - 800 баллов;
• 2-е место: Юрьев Александр (alexander.yuriev@mail.ru) - 790 баллов;
• 3-е место: Виктор Баринов (marilyn_manson@bk.ru) - 775 баллов;
• 4-е место: Владислав Симоненко (simonenko.ua@mail.ru) - 770 баллов;
• 5-е место: Илья Гребнов (Ilya.Grebnov@mail.ru) - 760 баллов;

Они награждаются футболками от компании Mail.Ru.

Также, по результатам нашего мини-чемпионата ПРИЗЫ от компании Mail.Ru вручаются:

• Роману Милючихину - Стереогарнитура Sagem BT SH1 - за 1-е место;
• Юрьеву Александру - Карманный накопитель WD Passport - за 2-е место;
• Виктору Баринову - Сумка - за 3-е место;

Я свяжусь с победителями позднее чтобы обсудить вручение призов.

[ Полную таблицу результатов можно увидеть здесь → ]

Вернувшись в отель мы с Мишей решили проведать баньку в отеле. Мы о ней никогда не узнали, если бы не надпись в лифте "на этом лифте нельзя добраться до бани, используйте лифт в основном здании". Банька удивила нас двумя вещами: во-первых, она бесплатная, а во-вторых, огромная. Температура была неплохая - 90 градусов (у японцов тоже цельсии). Как выяснилось японцы моются сидя на маленьком сидении. Мы попробовали, оказалось вполне удобно.

Спокойной ночи.

Обедать пошли в наиболее японский ресторан из всех, что видели до. Официантка говорила по английски! Четыре слова. Забавно было, когда, указав на длинный список иероглифов, она дала понять, что я должен выбрать себе напиток. Выбрал. Ткнул пальцем во второй справа (надо сказать, что предпочитают писать они по вертикали). Если вы когда-либо будете в этом ресторане, выберете что-нибудь другое! Принесли мне что-то зеленое и темное. Для человека выросшего на Волге, единственная ассоциация -- очень сильно зецветшая вода. На вкус тоже было не далеко. Короче, китайскую кухню предпочитаю больше!

Возможно, читателям нашей рубрики будет интересно узнать, что очередной, девятый четвертьфинал чемпионата мира по программированию состоится, как обычно, в начале октября, в Саратовском государственном университете.
Вся информация, как обычно, на сайте http://contest.sgu.ru.

Enjoy.

Итак, монитор заморожен, и вы можете видеть, что наша команда под заморозку ушла лидером с 5 решёнными задачами. На пятки нам наступает Алтай.
По мнению авторитетного тренера, у чемпионов мира этого года будет 7 решённых задач.

Открыл русско-японский разговорник. Почему-то всегда думал, что японский более лаконичный, нежели русский. Читаю: "Я тоже -- Ватаси мо сансэй дэс". Интересно, причем здесь "сансэй"?

А еще: интересно, какой умник догадался не ставить ударения в разговорнике?

Сегодня днем с удивлением для себя обраружил, что уезжаем мы не вечером 7-го, а с утра :). Вот теперь думаю, как бы все успеть, ну хотя бы что-либо.

Угадайте, что я обязательно забуду взять?

Передышку в ожидании рейса в Ш2 я всегда воспринимаю как отдых перед продолжительным марафоном. Два часа до Парижа, а затем еще двенадцать до Токио. Последние несколько дней очень жалею, что не поехали в Токио на поезде! Поспали бы...

Аэропорт Шереметьево 2 радушно встретил нас бесплатным интернетом. Для этого надо зайти в сеть VIP. Весь http редиректится на форму типа Login-Password, куда я не долго думая сразу же ввел guest/guest. Отличный интернет! Только никому не слова!

Сразу спасибо всем кто за нас болел. Для вас сообщаю, что мы решили 6 задач со временем около 960 минут. Прогнозов делать не буду, монитор у всех перед глазами. Награждение не скоро (примерно через 5 часов), но как только будет возможность уточним все результаты.

Российским болельщикам уточняю, что по московскому времени финал уже
СЕГОДНЯ!
Начало - в 17:00, по Москве.
Попытки смотреть официальный монитор могут начинаться с сайта финала 2006.
Саратов ГУ-2, мы желаем вам удачи и успехов!

Сейчас 8 утра, и с вами в прямом эфире я.
Сегодня и завтра мы живём в большом доме с красной крышей.

Состоялся четвертьфинал чемпионата мира по программированию Южного подрегиона.
Первые 3 места заняли команды Саратовского госуниверситета. Неудивительно, ведь одна из этих команд уже принимала участие в финале, а две других - в полуфинале.
В этом году на соревнованиях присутствовал директор ACM ICPC William B. Poucher, который особо отметил высокий уровень организации чемпионата и пообещал приехать к нам ещё :)

Результаты доступны по адресу http://contest.sgu.ru/monitor/

Известный ученый-самоучка Шурик изобрел машину времени и теперь хочет осуществить заветную мечту - стать свидетелем одного исторического события. Он уже было собрался ввести в машину желаемую дату, но обнаружил, что мощность машины сильно ограничена. А именно, по причине питания от бытовой электрической сети машина не может совершить переход более чем на K дней. Сообразив, что придется путешествовать через промежуточные даты, Шурик составил список интервалов времени в прошлом, куда попадать ему совершенно не хочется из-за войн, революций, эпидемий, катастроф и т.п. У Шурика нет времени на расчеты, поэтому он просит вас определить последовательность переходов во времени к желаемой дате с минимальным числом промежуточных дат или же сказать, что при данных условиях событие недостижимо. Учтите, что машина времени может совершать переходы во времени как вперед так и назад, но не может прыгнуть в дату позднее начала путешествия.
Входные данные.
В первой строке записана дата изобретения машины времени, которая является стартовой для путешествия. Во второй строке записана дата, в которую нужно попасть. Эта дата является более ранней, чем стартовая. В третьей строке записано неотрицательное целое K (1 ≤ K ≤ 10^9) - величина максимального прыжка машины времени. В следующей строке записано целое число M (0 ≤ M ≤ 60000) - количество нежелательных интервалов времени. В последующих M строках заданы сами интервалы: датой начала и датой конца (обе границы включаются в интервал). Интервалы могут пересекаться. Гарантируется, что дата начала любого интервала не превосходит дату его завершения. Все даты во входном файле корректны и заданы в формате ДД.ММ.ГОД, где год находится в интервале от 1 до 3*10^6. Даты начала и завершения интервалов разделяются ровно одним пробелом.
Все вычисления следует проводить в соответствии с обычным грегорианским календарем, то есть считать, что год високосный, если он делится на 4, но не делится на 100 или год делится на 400. Например, годы 2012, 2000 - високосные, а 2007, 1900 - нет.
Гарантируется, что даты начала и конца путешествия не попадают ни в один из заданных интервалов.
Выходные данные.
В случае если желаемой даты достичь нельзя, выведите "NO SOLUTION". В противном случае выдайте в первой строке минимальное число дат в путешествии (включая начальную и конечную). Если это количество не превосходит 10^4, в следующих строках выведите сами даты по одной в строке, следуя формату, описанному для входных данных.
Примеры:

	input.txt	output.txt
Пример #1	30.07.1988 23.07.1988 2 2 26.07.1988 26.07.1988 22.06.1941 09.05.1945	5 30.07.1988 29.07.1988 27.07.1988 25.07.1988 23.07.1988
Пример #2	12.04.2006 01.01.1 1 0	732413

Ограничение времени для 32-х битного компилятора: 2 секунд
Ограничение времени для 16-и битного компилятора: 8 секунд
Ограничение памяти: 64 мегабайта
Входной файл: input.txt
Выходной файл: output.txt
Про компиляторы можно почитать здесь

После похода в аквариум мы решили плотно перекусить. Нас не испугала зеленая жидкость, поэтому мы отправились в СУШИ-бар. В этом баре все сложилось довольно удачно. Обычно приходилось долго объяснять, что мы хотим (при этом что это и сколько стоит мы узнавали только после того как уже съели). Здесь же все было на виду. Нужно было лишь выбрать то, что тебе нравиться, взять и съесть. Еда можно сказать так и лезла в рот. Суши, ролы и еще что-то не опознанное ездило на "беговой дорожке". Когда "суша" проезжала мимо тебя, можно было ее взять и съесть. Если то, что тебе нравиться на картинке не ездеет мимо тебя, то надо громко по-японски крикнуть ее название, и ее тут же приготовят для тебя. Удобно было и то, что все стоило одинаково (одна порция - 138 японских рублей, k порций - k * 138 японских рублей ). Короче, ролов и суш мы наелись хорошенько. Ну и по традиции всю трапезу закончили в бане в гостинице.