Откройте свой Мир!

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

К сожалению, пишу поздно. Открытие было вчера, сегодня были пробные туры (точнее, одна практическая сессия и один пробный тур), конференция Collaborative Learning, так что мы были слегка заняты.

Я постараюсь восполнить недостаток информации, но это скорее всего будет после окончания мероприятия, так сказать, в ретроспективе (у меня есть 5 гигабайт фотографий и 2 видеоклипа ужасного качества).

В этом году всё мероприятие проходит в Стокгольме, в университете под названием KTH (не спрашивайте меня как полностью пишется, а переводится как королевский технический университет). Церемония открытия была в city hall (там где обычно вручают нобелевские премии). Подробнее программу мероприятий и всякую бесполезную информацию можно узнать, как обычно, на сайте. В этом году у них новшество - видеорепортажи :)

Ну а завтра примерно с 12:00 по москве будет основной тур, попробую здесь постить апдейты, какие будут.

Enjoy.

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

• компанию 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-е место;

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

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

Жюри подвело итоги чемпионата и пытается связаться по электронной почте с некоторыми участниками для установления их личности :) Публикация результатов состоится совсем скоро.

Как я и обещал, в 0:00 московского времени наш чемпионат закончился. Решения больше не принимаются, жюри подводит итоги и готовит список победителей к награждению.

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

На Петрозаводских сборах и на финале чемпионата мира наша команда заняла 6 место. (В Петрозаводских сборах участвовала команда Варшавского университета и все российские команды).

Но это еще не все!!
Номер нашей команды (ID) на полуфинале и на финале был 40. На полуфинале мы сдали задачу в последние 10 минут и на финале тоже.


P.s.
Для тех кто был на финале: Сумма всех чисел в этом сообщение до P.s. равна 56 (я ничего особенного сказать не хотел :-) )

Нефтяные месторождения в Берляндии имеют очень небольшие размеры и считаются точками. В Берляндии всего N месторождений, для каждого из которых известны его координаты (x_i, y_i). Скрудж вкладывает немалые деньги в покупку месторождений. Для этого целый день он выкупает прямоугольные участки земли, стороны которых параллельны осям координат. Будучи увлекающейся натурой, Скрудж не замечает, что, покупая очередной участок, часть этого участка (а, возможно, и весь) уже куплена им до этого. Всего он выкупил M участков, для каждого из них известны пары координат противоположных углов (X_1,j , Y_1,j),(X_2,j , Y_2,j). После утомительного рабочего дня Скрудж задался вопросом, сколько же всего нефтяных месторождений находится на его территории. Нефтяное месторождение находится на территории Скруджа, если оно расположено внутри или на границе хотя бы одного из M прямоугольников. Более того, для каждого нефтяного месторождения Скрудж хочет знать количество принадлежащих ему участков, на территории которых оно находится.
Входные данные.
В первой строке входного файла содержится целое число N (1 ≤ N ≤ 100000), где N - количество месторождений. Далее в N строках записаны описания месторождений, заданные своими целочисленными координатами x_i, y_i. Два или более месторождения могут находиться в одной точке. Следующая строка содержит целое число M (1 ≤ M ≤ 100000), где M - количество прямоугольников. Далее в M строках заданы описания прямоугольников четверками целых чисел X_1,j , Y_1,j, X_2,j, Y_2,j. Два или более прямоугольника могут совпадать. Прямоугольники не могут вырождаться в отрезки или точки.
Все координаты во входном файле не превосходят 10^9 по абсолютной величине.
Выходные данные.
Выходной файл должен содержать N строк, i-ая строка должна содержать количество участков, содержащих i-ое месторождение. Месторождения следует нумеровать в соответствии с их порядком во входных данных.
Примеры:

	input.txt	output.txt
Пример #1	4 0 0 10 0 10 10 0 10 3 0 1 1 0 9 11 11 9 9 -1 100 100	1 1 2 0
Пример #2	4 0 1 1 0 1 1 0 0 1 0 0 1 1	1 1 1 1

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

Вот мы и в Саратове. Всего за 44 часа мы переместились из поздней весны в зиму.
Спасибо всем, кто болел за нас! Надеюсь, мы вас не подвели.

Связная структура данных "дерево" предполагает наличие вершин и связей между ними. Циклов в дереве нет. Одна вершина дерева называется корнем, все вершины достижимы из нее. В этой задаче корнем всегда будет вершина 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
Про компиляторы можно почитать здесь

Известный ученый-самоучка Шурик изобрел машину времени и теперь хочет осуществить заветную мечту - стать свидетелем одного исторического события. Он уже было собрался ввести в машину желаемую дату, но обнаружил, что мощность машины сильно ограничена. А именно, по причине питания от бытовой электрической сети машина не может совершить переход более чем на 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
Про компиляторы можно почитать здесь

В дальнейшем появятся задачи, в которых ограничения по времени будут различны для разных компиляторов. Для этого мы разделили все компиляторы на две группы: 16-и битные и 32-х биитные. К 16-и битным мы относим:

• Borland Pascal 7.0 (PAS)
• Borland C/C++ 3.1 (C, CPP)

К 32-х битным - соответственно все остальные:

• Borland Delphi 7 (DPR)
• Microsoft Visual Studio .NET 2005 C++ (CXX)
• Java - J2SE 1.5 (JAVA)
• Python 2.5 (PY)

По непонятным техническим причинам в блог не попала запись двухчасовой давности, гласящая

Закрытие завершилось. Мы - 6е, серебрянная медаль.
Спасибо всем болельщикам!
Нас зовут на празднование.

Но теперь у вас есть результаты Top 12. Еще раз спасибо!

Берляндский алфавит состоит из N букв. Петя пишет письмо Маше. Он хочет зашифровать письмо, заменив каждую букву последовательностью цифр, в которой можно использовать цифры от 0 до K (0 ≤ K ≤ 9) включительно. Для каждой буквы алфавита известна длина p_i соответствующей последовательности цифр. Во избежание возможности неправильного толкования Петя хочет, чтобы любое зашифрованное сообщение имело только один вариант расшифровки. Найдите такой набор последовательностей цифр, или укажите, что его не существует.
Входные данные.
В первой строке входного файла содержатся целые числа N, K (1 ≤ N ≤ 100; 0 ≤ K ≤ 9), где N - количество букв в алфавите, а K - наибольшая цифра, которую можно использовать. Во второй строке записана последовательность целых чисел p_1, p_2, …, p_N (1 ≤ p_i ≤ 100).
Выходные данные.
Выведите N строк, i-ая строка должна содержать последовательность цифр, которой следует шифровать i-ую букву алфавита. Если решение несколько, выведите любое. Если искомого набора не существует, выведите в выходной файл строку "NO SOLUTION".
Примеры:

	input.txt	output.txt
Пример #1	3 1 2 1 2	00 1 10
Пример #2	5 1 2 2 2 2 2	NO SOLUTION
Пример #3	4 2 1 2 1 2	0 10 2 11

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

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

В Токио подведены итоги XXXI финала Чемпионата Мира по программированию.

* Команда Warsaw U получает золотые медали и становится чемпионом мира и Европы 2007 года!
* Команда Tsinghua University заняла 2 место и получила золотые медали.
* Команда СПбГУ ИТМО заняла 3 место и получила золотые медали.
* Команда Massachusetts Institute of Technology заняла 4 место и получила золотые медали.
* Команда Новосибирского ГУ заняла 5 место и получила серебряные медали.
* Команда Саратовского ГУ заняла 6 место и получила серебряные медали.
* Команда Twente U заняла 7 место и получила серебряные медали.
* Команда Shanghai JTU заняла 8 место и получила серебряные медали.
* Команда U Waterloo заняла 9 место и получила бронзовые медали.
* Команда МГУ заняла 10 место и получила бронзовые медали.
* Команда U of Auckland заняла 11 место и получила бронзовые медали.
* Команда California I of Technology заняла 12 место и получила бронзовые медали.
* Чемпионом Африки и Ближнего Востока стала команда University of Cape Town.
* Чемпионом South Pacific стала команда University of Auckland.
* Чемпионом Южной Америки стала команда U de Buenos Aires.
* Чемпионом Северной Америки стала команда MIT.
* Чемпионом Азии стала команда Tsinghua U.
* Чемпионом Европы стала команда Warsaw U.

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

Итак, прошло 4 часа соревнования и монитор заморожен. Как вы наверное видели, наша команда ушла на последний час соревнований на 7-й позиции с 5-ю решенными задачами. Официальные результаты можно будет узнать где-то здесь, после награждения. Ну а мы идем спать и надеяться. Спокойного дня :)Е.

Другой монитор, по моему более красивый, - http://dimon.xgm.ru/pcms/

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

На данный момент я нашел следующие ресурсы (помимо нашего), на которых возможно появление комментариев происходящего по ходу финала:
блог Aldanur'a, страничка Олега Христенко, блог Петра Митричева ну и естественно не забываем про официальный сайт. Если кто найдет еще что нибудь - плз, киньте линк в комментариях.

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

Ну и напоследок - фото делегации России и бывшего СНГ:

Все, мы идем спать.

PS По возвращении выложу полноразмерную фотографию.

Язык программирования Berland Pascal 7.0 очень прост. Каждая его строка содержит один оператор, который является либо оператором присваивания, либо оператором вывода. Оператор присваивания имеет вид:
        <переменная>:=<выражение>;
Оператор вывода имеет вид:
        WRITELN(<выражение>);
Имя переменной всегда состоит из одной строчной буквы латинского алфавита ('A':'Z'), а выражение содержит переменные, знаки бинарных арифметических операций "#", "%", "&", круглые скобки и целочисленные константы. Выражение корректно с точки зрения стандартных математических правил.
Оптимизация программы состоит из двух фаз. Во время первой фазы в программе помечаются все строки, содержащие оператор присваивания вида "<переменная>:=<константа>;". Непомеченные в первой фазе строки подаются на вход оптимизатору. Относительный порядок следования строк при этом сохраняется.
Оператор присваивания может быть убран оптимизатором, если его удаление не влияет на результат вывода программы (следует учитывать, что этот оптимизатор не знает о возможном существовании строк, помеченных в первой фазе). Оптимизатор работает на ранней стадии компиляции и не может пользоваться правилами вычисления "#", "%", "&", а воспринимает их как некоторые абстрактные арифметические операции.
Ваша задача реализовать функциональность оптимизатора. На вход оптимизатору подаются строки программы, не помеченные в первой фазе. Вывод оптимизатора состоит из строк, поданных ему на вход, которые он не может убрать. Изменять выражения, переменные или еще как-то модифицировать программу нельзя.
Входные данные.
В первой строке входного файла содержится натуральное число N (1 ≤ N ≤ 100), где N - это количество строк, поданных на вход оптимизатору. Далее следует N строк, каждая из которых содержит оператор присваивания или оператор вывода. Все строки не содержат никаких лишних символов, комментариев и строго соответствуют описанному выше формату. Их длины не превосходят 32 символа. Входные данные не содержат пробелов. Во входных данных отсутствуют строки вида "<переменная>:=<константа>;", так как они были помечены на первой фазе.
Выходные данные.
Выведите строки программы, удалив все лишние операторы присваивания. Относительный порядок операторов менять нельзя.
Примеры:

	input.txt	output.txt
Пример #1	5 A:=B; A:=B#C; WRITELN(A); C:=A; WRITELN(B&2);	A:=B#C; WRITELN(A); WRITELN(B&2);
Пример #2	5 C:=5#1; A:=X#Y&(Z#A); A:=A#1; B:=A&B; WRITELN(C#A);	C:=5#1; A:=X#Y&(Z#A); A:=A#1; WRITELN(C#A);
Пример #3	7 A:=B; WRITELN(A); A:=B; WRITELN(A); Z:=Z; X:=Y; WRITELN(Z);	A:=B; WRITELN(A); A:=B; WRITELN(A); WRITELN(Z);

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

Интересно, много ли читающих этот блог хотели бы оказаться в Японии на чемпионате мира про программированию? Ну или хотя бы просто в Японии?

Даже если у вас нет такой возможности, хотя бы попробуйте себя почувствовать там. Этому поможет новый сервис video.mail.ru. Специально для тех, кому это интересно - альбом с видеороликами из Японии здесь.

Там можно найти фрагменты IBM TechTrek, похода в DisneySea, выступления девочек с мечами, игра на ямисен (японская гитара), прогулка по побережью:

Посмотреть ролик Автор: Alex Klimov, альбом: Tokyo	Посмотреть ролик Автор: Alex Klimov, альбом: Tokyo	Посмотреть ролик Автор: Alex Klimov, альбом: Tokyo
Посмотреть ролик Автор: Alex Klimov, альбом: Tokyo	Посмотреть ролик Автор: Alex Klimov, альбом: Tokyo

Надеюсь, со временем альбом пополнится новыми интересными роликами.