Программисты, на старт!

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

Уже из названия турнира видно, что он проводится между учащимися вузов. Это и понятно: ведь к лучшим студентам как к потенциальным работникам присматриваются ведущие hi-tech-фирмы (IBM, Microsoft и др.).

Этому чемпионату уже исполнилось четверть века. В сезоне 2001/2002 в нем принимали участие более трех тысяч команд из семидесяти стран мира. Численность команды строго ограничена - три человека, причем на время решения задач команда получает в пользование только один компьютер.

Чемпионат включает три этапа: четвертьфинальный, полуфинальный и финальный. Первенство на каждом из этапов присуждается команде, решившей больше задач или (в случае равенства по этому показателю)затратившей меньше времени.

На полуфинальных этапах команды соревнуются в 29 региональных группах. Победители полуфинальных состязаний выходят в финал, который состоится 20-24 марта 2002 года в Гонолулу (что, кроме всего прочего, означает поездку в курортный рай - на Гавайские острова).

Россия организует собственную группу (она называется Северо-Восточной Европейской) начиная с 1996 года. В этом году полуфинальные соревнования одновременно прошли в Санкт-Петербурге, Барнауле и Тбилиси. По результатам состязаний были определены семь команд-участниц финала чемпионата мира, а также чемпион России по программированию 2001 года. Новые чемпионы России - студенты кафедры компьютерных технологий факультета информационных технологий и программирования СПбГИТМО Евгений Южаков, Тимофей Бородин и Александр Штучкин (на фото слева направо). Закончив средние школы в Костроме, Саратове и Котласе, они были приглашены в СПбГИТМО за успехи на Всероссийских олимпиадах школьников. Тренер этой команды - студент 4-го курса этой же кафедры, серебряный медалист «Орландо-2000» и золотой медалист «Ванкувера-2001» Андрей Станкевич. Результат победителей - семь решенных задач из восьми.

В первую шестерку вошли также команда Саратовского университете, вторая команда СПбГИТМО, две команды МГУ и команда Минского университета.

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

Поле для игры - прямоугольник 4x4, на котором лежат 16 фишек. Одна сторона каждой фишки черная, а другая - белая (как в реверси).

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

Некоторые (но не все) наборы костяшек домино можно уложить в незамкнутую цепочку по стандартным правилам. Например, если дан набор (1:5), (1:6), (5:5) и два экземпляра (2:4), то уложить его в цепочку не удастся, но если добавить к ним «доминошку» (2:5), это уже получится:

Однако нужного результата можно достичь и иначе - добавив две костяшки (1:2):

Заметим, что во втором случае сумма очков на добавленных «доминошках» меньше (1+2+1+2=6, а 2+5=7). Требуется написать программу, которая для данного множества костяшек определит дополняющий набор с минимальной суммой очков, дающий возможность выложить все кости в цепочку.

Триатлон - это соревнование на скорость (и выносливость), состоящее из трех этапов. Первый этап - плавание, второй - велогонка, третий - бег. Известна скорость спортсмена на каждом из этапов. Требуется определить, может ли судья так задать три дистанции, которые придется преодолеть участникам, чтобы победителем в триатлоне стал определенный участник? (Точнее, от вашей программы требуется ответ «да, сможет» или «нет, не сможет» для каждого из N участников.)

Хакер Билл случайно потерял всю информацию со своего жесткого диска. Однако у него сохранились распечатки, по которым он восстановил полные пути для папок (такого типа: WINNT\SYSTEM32\CERTSRV\CERTCO~1\ X86). Помогите Биллу - напишите программу, которая по этим данным построит дерево папок жесткого диска (то есть текстовый файл, в котором корневые папки выписаны в строках с первой позиции, а вложенные - в нужном месте, причем с отступом относительно той папки, в которой они находятся).

Остальные задачи (на английском языке), а также тестовые примеры можно найти на сайте http://neerc.ifmo.ru/online.