В Токио подведены итоги 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.

На контроле меня попросили включить ноутбук, и он повис. Пока я его реанимировал, обнаружилось две беспроводные сети - МТС и Билайн. Обе - за деньги.

Поэтому, сидя в интернете дедовским способом - через GPRS и пользуясь случаем, хочу передать привет всем читателям и пожелать успехов в решении задач.

Следующий выход в эфир - из Атланты.

А дьюти-фри в Шереметьево 2 - единственное дьюти-фри, где спиртное и выпивка дороже, чем в соседнем магазине.

Да, мягко скажем, challeging.

Управлять надо космическими кораблями. Одним большим и тремя маленькими дронами. Можно собирать энергию, стрелять патронами, использовать pulse (тоже оружие - распространяется круговыми волнами), включать щиты, передавать энергию между кораблями и на свою планету.

Это вкратце.

Участники финала писали Java Challenge, корабль команды СГУ назывался krosavcheg.
А команда составе я, Mike Mirzayanov и Sergey Orshansky писали Java Challenge Extreme Edition (и назывался наш корабль Saratov+IFMO).

Экстрим был на протяжении всего Java Challenge - и тренерского, и для обычных команд. И даже после. Складывалось впечатление, что они его написали за день и ни разу не отлаживали.
В самом начале рухнул сервер, на котором жили объекты участников. Затем был обнаружен баг в функции getDistanceTo (эгегей, кто посадит больше багов в функцию расстояния!). После этого вдруг неожиданно выяснилось, что расстреливая дохлые кораблики можно зарабатывать очки - и это также отключили.
Java Challenge продлили на 45 минут, за которые мы пытались написать что-то более менее сознательное.
Этого делать было не нужно. Совсем.

Вечером, во время ужина, нам пытались показать то, что получилось. И тут выяснилось, что:
1. У них неправильно отображается результат матча - не в том порядке, цифры не соответствуют именам команд.
2. Для турнира были взяты не самые последние версии кораблей, а какие-то предыдущие недоотлаженные классы.

Всё это организаторы поняли уже по окончании отборочных туров - 3 подхода по 13 матчей. Традиционно, организаторы решили переиграть чемпионат. Через час.
Запустили тренерскую часть. Здесь после четырёх матчей наш корабль занял 6 место. Наилучшим результатом среди российских кораблей может похвастаться Mr.Putin - 3 место.

А кто же занял первые 2 места в Extreme Edition, куда делся krosavcheg после переигровки, и как у IBM получилось так замечательно подготовить мероприятие?

Об этом я вам расскажу позже. После того, как вы вдоволь насмеётесь над выигрышной стратегией.
Готовы?

Не нужно никуда летать, ничего собирать, ни в кого стрелять. С первого хода нужно сливать всю энергию с дронов на большой корабль, а с большого корабля - на планету.
Теперь вы можете представить, как выглядел финал? На большом экране.
Те два корабля, что обыграли Мистера Путина, были устроены именно так. Четыре строчки кода в функции move.

Saratov+IFMO:

Аэропорт Сан-Антонио.

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

Yoki.ru (ссылка):
Приз - образовательные гранты по 10 тысяч долларов и компьютерные комплектующие от компании IBM. Команды Алтайского государственного университета и студенты из Техаса и Польши поделили второе место, а третье досталось команде Санкт-Петербургского государственного университета, Массачусетского Технологического Института и Университета Шанхая.

Сразу две вещи стали для нас сюрпризом. Образовательные гранты и компьютерные комплектующие ещё куда ни шло - при желании приз за первое место можно обозвать "образовательным грантом" (хотя вот сумма нас тоже удивила). Но вот то, что студенты Алтайского государственного (не технического) университета, а также студенты из Техаса и Польши поделили второе место просто ввело нас в состояние тихого ужаса.

В официальной таблице результатов отмечены команды в порядке убывания мест, при этом цветами указано, какие медали они получили. И, для справки, Twente - это Нидерланды.

Радио Голос России (ссылка):
Российские программисты также получили награды за второе и третье места, разделив их со студентами из других стран.

Получили, а потом пошли в гостиницу и поделили... поровну.
Да, там также было про гранты.

InfoRos (ссылка):
Второе и третье места также заняли российские команды из Алтайского и Петербургского университетов, однако призовые места им пришлось поделить со сверстниками из Техаса, Польши и Китая

Опять делим призовые, только на этот раз не награды, а второе и третье места.
Да, там написано "по информации РСН", так что с этой трактовкой мы ещё встретимся, видимо, в РСН.

zdnet.ru (ссылка):
В этом году вновь победила традиционная тактика, хорошо освоенная российскими тренерами и их подопечными: главное — быстрота и минимум поданных заявок (за каждую не принятую в качестве решения заявку начисляется штрафное время). При традиционном раскладе есть вероятность проиграть — если конкуренты решат большее количество задач. Но, как показывает опыт, такие случаи достаточно редки. Правда, в прошлом году жюри под занавес соревнований приняло у китайской команды очередную заявку, обеспечившую ей победу, несмотря на то, что эта команда далеко не лидировала по скорости.
На сей раз обошлось без подобных сюрпризов. Программистам из Саратовского государственного университета зачли пять задач из восьми поданных заявок. На втором месте оказались студенты Алтайского государственного технического университета с десятью поданными и пятью зачтенными заявками. Третье золото (жюри чемпионата традиционно распределяет три комплекта из четырех золотых, серебряных и бронзовых медалей) досталось университету Твенте, представлявшему Нидерланды (10 поданных, 4 принятые заявки). Лидер прошлого года, Шанхайский университет, занял четвертое место и стал последним золотым медалистом (13/4).

Просто песня. Корреспонденты zdnet.ru дисквалифицировали команду Jagiellonian University, отобрали у неё медали и отправили домой без призов. Хотя, надо сказать, заявки в жюри - очень удачная в художественном смысле находка. И Twente у них, слава богу, не в Техасе.

Хотя, я знаю, откуда растут уши у слуха и про Техас, и про то, что места поделились. Lenta.ru (ссылка) дала эту информацию со ссылкой на Associated Press. В оригинальной новости не было ни слова про Техасскую команду, но было очень обтекаемо написано про призовые места - "runner-up gold medal winners", "shared in $2,100 and a silver medal". Но, надо сказать, не было ни слова про команду Варшавского университета, занявую 7 место и также завоевавшую серебро.

Также при чтении нам встретились:
- доселе неизвестный нам участник команды по фамилии Кулкин (без мягкого знака);
- "Победители получили стипендию в размере $10 тыс. и компьютерную плату от компании IBM" (даже и не знаю);
- "3800 команд из почти 1500 университетов в 70 странах мира" (недолёт).

В целом мы приятно удивлены тем ажиотажем, который возник вокруг победы команды СГУ на соревнованиях, и безусловно благодарны средствам массовой информации, сделавшим эту победу главной новостью. То, что я тут описал - всего лишь смешные и досадные неточности.

Факт остаётся фактом.
Чемпионы мира.

Вчера я чуть чуть ошибся в пересказе условия Java Challenge 2003 - CodeRally. Неудивительно, 3 года прошло, мелкие детали забываются.

Но вот на этом сайте можно скачать условие и окружение для стравливания машинок друг с другом.

Сделав небольшой крюк в 2 часа мы прибыли в Токио. В Париже мы поздравили Антонину Гавриловну с замечательным праздником 8 марта. Я думаю это прекрасно встретить 8 марта в Париже. А побывать в Париже и не сфотографироваться с Эйфелевой башней -- ну просто смешно.
В Токио мы покатались на автобусе и поели самой популярной японской кухни (по крайней мере нам сказали 2 английских слова "popular" и "normal").

Сегодня ночью мы сядем в машину и по ночным дорогам Техаса помчимся в Сан-Антонио, откуда завтра утром вылетим в Москву через Атланту. На родину мы прилетим в понедельник, 17 апреля, в 10:30 утра в аэропорт Шереметьево-2 рейсом DL46 авиакомпании Delta Airlines.
Совсем на родину - в Саратов - мы прибудем 18 апреля, во вторник, в 9:08 утра поездом №9 (с особым режимом движения), вагон №12.

Завтра отправляемся на самое последнее и поэтому самое трудное соревнование - на финал ICPC. Для меня это уже вторая поездка на чемпионат. К сожалению, по правилам соревнований лишь дважды можно участвовать в финале. Ощущения выхода "на пенсию" в 19 лет вполне своебразны. Отличие, пожалуй, в том, что самое желанное - это не первый "день пенсии", а последний "рабочий день".
Впервые я принял участие в командных соревнованиях по программированию 5 лет назад. За это время поучаствовал в сотнях подобных соревнований. И вот осталось только одно. Значит, все предыдущие тренировки и соревнования были для того, чтобы успешно выступить 15 марта.
Мы будем стараться как можем, будем биться до конца. Нам нужна ваша поддержка и наша удача :-)
Болейте за нас.

В 5 утра на павелецком вокзале нас встретил представитель компании Mail.Ru. Оказалось, что в такое время метро еще закрыто, и, чтобы не рисковать мы поехали на такси. И вот, в отличном настроении, мы прибываем в Шереметьево 2 в ожидании check-in на рейс, который в общем - то уже начался :).

Настал момент оглашения результатов и награждения победителей нашего чемпионата.
Для начала хочу поблагодарить тех, благодаря кому этот чемпионат стал возможен:

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

[ читать дальше → ]

Сегодня был день пробных туров В) Их было аж два. Стоит отметить, что это единственная возможность нормально сфотографироваться на финальном рабочем месте.

Сразу же к нам подошел представитель американской команды Northwest University. Они заранее догадались, что будут сидеть недалеко от нас и поэтому в Team Notebook (кто не знает что это - читайте icpc.baylor.edu, рассказывать долго В( ) напечатали специально для нас страницу с надписью - "Саратов берегись, мы чувствуем что нам повезет" В))))

Была сессия ответов на вопросы, но лучше оставим за бортом впечатления от нее и от programming environment. Сейчас по-идее идут занятия по айкидо, каллиграфии иероглифов и оригами, а также аниме. Но у меня нет сил, времени, желания (ненужное вычеркнуть) туда идти. Буду отдыхать и настраиваться.

Давным-давно Вася играл в тетрис. К сожалению, самой игры у него не осталось, остались только записи об играх. По ним Вася хочет узнать некоторые подробности. Васин тетрис устроен так. Есть стакан шириной в W клеток. Сверху в него падают квадратики размером 1x1. Если нижняя строка оказывается полностью заполненной, то она исчезает, а Вася получает 1 очко. Из записей игры известно, какой ширины был стакан и в какую колонку Вася направлял очередной квадратик. Теперь он хочет узнать, сколько очков он набрал, и после каких квадратиков исчезала линия.

Входные данные:

В первой строке входного файла записано 2 целых числа N и W - количество падающих квадратиков и ширина стакана соответственно (0 ≤ N ≤ 100, 0 < W ≤ 100). Во второй строке записано N целых чисел Ai - номера колонок, в которые падает i-тый по номеру квадратик (1 ≤ Ai ≤ W). Можно считать, что стакан достаточно высокий, а Вася уверенно играет, так что квадратик просто падает сверху в Ai-той колонке. Колонки пронумерованы от 1 до W слева направо.

Выходные данные:

Выведите в первую строку M - количество очков, которые набрал Вася, а во вторую - M чисел, означающих номера квадратиков, после которых исчезала линия. Номера квадратиков выводить в возрастающем порядке.

Примеры:

	input.txt	output.txt
Пример #1	3 2 1 1 2	1 3
Пример #2	3 2 1 2 1	1 2
Пример #3	4 3 1 2 1 2	0

Ограничение времени: 2 секунды

Ограничение памяти: 64 мегабайта

Входной файл: input.txt

Выходной файл: output.txt

Берляндский алфавит состоит из 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

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

Сим официально сообщаю, что команда Саратовского Государственного Университета выиграла финальные соревнования и стала чемпионом мира 2006 года.

Сан-Антонио, Техас, 12 апреля 2006 года.

Международная организация Association for Computing Machinery (ACM) была основана в 1947 году в Филадельфии сотрудниками Пенсильванского университета, создавшими один из первых программируемых компьютеров ENIAC.
В настоящее время ACM является одной из наиболее авторитетных международных организаций в области компьютерных технологий. В ассоциацию входят 170 региональных отделений, более 500 отделений в университетах и колледжах, и 34 группы специальных интересов (special interest group, SIG), занимающихся различными проблемами computer science. ACM проводит конференции, издаёт журналы и книги, присуждает различные премии за достижения в области теоретической информатики и компьютерных технологий - в частности, знаменитую ACM Turing Award.

Первые соревнования, отдалённо напоминающие современный чемпионат мира по программированию ACM, состоялись в 1970 году в Техасском "A&M" университете (до 1963 года "колледж сельского хозяйства и механизации", Agricultural and Mechanical College - отсюда A&M в современном названии). Соревнования 1977 года считаются первым чемпионатом мира ACM - именно в этом году они впервые были организованы по многоуровневой системе, а финал состоялся в рамках конференции ACM Computer Science Conference.

С 1977 по 1989 году в чемпионате в основном участвовали команды вузов США и Канады. Затем в 1989 году руководство чемпионатом переместилось в университет Бэйлор (Baylor University), и с этого момента началось создание региональных полуфиналов во всём мире. В 2005 году в чемпионате принимали участие 5606 команд из 1737 университетов 84 стран (в 1997 году это были 840 команд из 560 университетов). В среднем, число участников растёт на 10-20% каждый год.

Путь к финалу для многих современных команд (в том числе российских) начинается с четвертьфинальных (подрегиональных) соревнований, победители которых получают право участвовать в полуфинальных (региональных) соревнованиях, в свою очередь, победители которых получают путёвку в финал.

Финальные соревнования являются завершением соревновательного сезона и представляют собой четырёхдневное насыщенное событиями мероприятие, проходящее при непосредственном участии генерального спонсора. В течении четырёх дней, кроме самих соревнований и церемонии награждения, для команд-участников проводятся презентации, конференции, и турнир по программированию Java Challenge.

В этом году организаторы отмечают юбилей - 30 лет чемпионату мира, и юбилейные соревнования проводятся в родном городе Baylor University - Сан-Антонио.

[ читать дальше → ]

Пока я ездил на финал Test-The-Best в Минск, мои товарищи по команде отдувались за меня на Открытом Кубке МГУ-CBOSS по программированию. И надо признать, неплохо отдувались - заняли третье место, опередив чемпионов России по программированию. Интересно, улучшились или ухудшились бы результаты, если бы я не уехал? :)
В Минске же мои дела обстояли не лучшим образом. Скажу лишь, что я занял не последнее место :) На своем опыте я убедился, что занятое место на соревновании обратно пропорционально занятому месту при вечерней игре в боулинг. Наверное, это не случайно, и этому есть какое-то разумное объяснение.

Итак, мы прибыли в аэропорт Атланты (Hartfield-Jackson Intl Airport). Я слегка ошибся со временем перелёта - перелёт наш длился почти 12 часов, и прилетели мы, соответственно, в 0 часов по московскому времени и в 16:00 по местному.

Команда, измученная долгим перелётом без еды пошла искать, что бы поесть, а я немного пофотографировал.
Кроме того, мне пришлось взломать аэропортовый wi-fi, потому что он тоже хотел денег. Но не пускает только http, а ssh работает совершенно бесплатно. Надеюсь, понятно, что нас такие смешные ограничения остановить не смогут.

Видимо, нам нужно продвигаться на следующий самолёт, поэтому фотографии из Атланты будут позже.

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

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

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

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

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

Необходимо сложить два целых числа.

Входной файл:
В файле написаны два целых числа A и B, не превосходящих 1000.

Выходной файл:
Выведите сумму чисел A и B.

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

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

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

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

Java challenge был действительно увлекательный и наша машина всех почти вынесла.



Творилось там примерно следующее:

Но если вы думаете, что кроме самого финала, это единственное интересное что там ещё происходило - вы глубоко заблуждаетесь.
Тот финал 2003-2004 года в Беверли-Хиллз был ознаменован появлением шпионов. Да-да, вы не ослышались, именно шпионов.
Они - люди, которые никого не стеснясь, приехали воровать чужой код! Они просто подходили, вставали за спиной и высматривали
все исходники. От начала до конца. На просьбы отойти не реагировали.

Да, и ещё. Мелинда Пучер. Дочь директора финальных соревнований. Комментарии излишни. :)

Сергей решил купить новый компьютер. Прежде чем ходить по магазинам, он решил позвонить друзьям, чтобы узнать цены. Сергей и все его друзья живут на главной улице в Берляндии Берлстрит, в каждом доме которой находится магазин. Друзья Сергея по его просьбе по дороге на работу зашли во все встретившиеся магазины, а вечером сообщили ему о том, сколько стоит самый дешевый компьютер. Если человек живет в доме с номером A и работает в доме с номером B, то он посещает все дома с номерами между A и B, включая их самих. Сергей знает, где живут и работают его друзья. Помогите Сергею определить, сколько может стоить компьютер в каждом магазине на главной улице.

Входные данные.

В первой строке входного файла записано два целых числа N, K, где N (1 ≤ N ≤ 100) -количество домов на Берлстрит, а K (1 ≤ K ≤ 100) - количество друзей Сергея. Следующие K строк содержат информацию о каждом друге Сергея: A (1 ≤ A ≤ N) - номер дома, в котором живет друг, B (1 ≤ B ≤ N) - номер дома, в котором он работает, и C (1 ≤ C ≤ 1000) - цена самого дешевого компьютера вдоль пути друга на работу (в бурлях). Все числа во входном файле целые.

Выходные данные.

В первую строку выходного файла выведите стоимость компьютера в каждом магазине, начиная с 1-ого и заканчивая N-ым. Если существует несколько решений, то выведите любое. Имейте в виду, что компьютер в каждом магазине стоит не менее 1 бурля, и не более 2000 бурлей. Все цены в Берляндии - целые числа. Если друзья Сергея ошиблись, и их информация противоречива, то выведите -1.

Примеры:

	input.txt	output.txt
Пример #1	3 1 1 2 100	100 200 79
Пример #2	5 3 1 4 100 4 5 200 3 2 150	100 150 157 314 200
Пример #3	3 2 1 1 100 2 1 175	-1

Ограничение времени: 2 секунды

Ограничение памяти: 64 мегабайта

Входной файл: input.txt

Выходной файл: output.txt