Архивы: по дате | по разделам | по авторам

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

Архив
автор : Дмитрий Гориловский   29.01.2002

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

В последнее время в компьютерной периодике часто встречались сообщения о чемпионатах России или мира по той или иной компьютерной игре. Основным движителем в этой сфере стала компания Samsung, организовавшая WCGC, но многие из читателей наверняка задавались вопросом: «А как же соревнования по программированию? Кто их проводит? Кто первый в России? А в мире? А как принять участие?» Пользуясь поводом (недавно закончился полуфинал первенства мира на кубок «ACM International Collegiate Programming Contest»), я постараюсь ответить на эти вопросы.

Уже из названия турнира видно, что он проводится между учащимися вузов. Это и понятно: ведь к лучшим студентам как к потенциальным работникам присматриваются ведущие 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 участников.)

Disk Tree

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

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

© ООО "Компьютерра-Онлайн", 1997-2024
При цитировании и использовании любых материалов ссылка на "Компьютерру" обязательна.