27 ноября в Санкт-Петербурге, Барнауле и Тбилиси прошел полуфинал командного чемпионата мира по программированию в Северо-Восточной Европейской отборочной группе. Этот турнир, проводящийся под эгидой международной ассоциации по компьютерной технике, является престижнейшим и самым массовым соревнованием по программированию в мире. Шутка ли: в отборочном цикле нынешнего года участвуют команды трех тысяч вузов со всего света!
Традиционно турнирная борьба в ходе состязаний ведется по достаточно жестким, почти спартанским правилам. В течение пяти часов команда из трех студентов, в распоряжение которой выделяется один компьютер, должна решить как можно больше задач и сдать их автоматической системе проверки, тестирующей полученные программы-решения на множестве исходных данных. Cданной считается лишь программа, успешно прошедшая все до единого предложенные тесты. При этом участников подгоняет неумолимо "тикающее" время: в зачет идут также минуты, прошедшие от начала соревнований до момента сдачи очередного задания, а также 20 "штрафных" за каждую неудачную попытку.
На старт российских соревнований вышло 117 команд. Чемпионский Кубок-2002 завоевала команда Московского университета, укомплектованная питомцами механико-математического факультета в составе Петра Митричева, Евгения Черепанова и Максима Бабенко. Посланцам столицы удалось добиться феноменального результата, разделавшись со всеми задачами за час с лишним до конца соревнований! "Серебро" завоевала команда Нижегородского университета, а "бронзу" - команда Саратовского университета, сдавшие соответственно 8 и 7 задач. Призеры российского первенства, а также вошедшие в заветную восьмерку лучших команды Санкт-Петербургского университета, Вологодского педагогического и Самарского муниципального университетов будут отстаивать честь России на мировом финале, который состоится в конце марта будущего года в американском Беверли-Хиллз.
Несмотря на то, что далеко не каждому подфартило поучаствовать в полуфинальных баталиях, на официальном сайте соревнований neerc.ifmo.ru любой может "помахать после драки кулаками", сразившись с беспристрастной судейской машиной в онлайне. Там же любители программистских посиделок могут ознакомиться с полными условиями задач на английском языке, а также правилами соревнований и итоговой таблицей полуфинальных боев. Мы, в свою очередь, представляем вниманию читателей газеты "избранное" - "русифицированную" версию трех самых простых задач прошедшего первенства.

Забавные числа
С задачей справились 27 команд, первый успех - на 17-й минуте у команды Московского университета.
Попробуем расставить в лексикографическом (словарном) порядке множество целых чисел между 1 и N. В случае для N=11 у нас получится следующая последовательность: 1, 10, 11, 2, 3, 4, 5, 6, 7, 8, 9.
Обозначим позицию числа K в этой последовательности как Q(N, K). К примеру, Q(11, 2) = 4. Требуется написать программу, по заданным числам K и M (каждое из которых лежит в диапазоне от 1 до миллиарда) находящую такое минимальное N, чтобы Q(N, K) равнялось M. В случае если такого числа найти не удалось, в качестве ответа должен быть выдан 0.

Кирпичики
С задачей справились 55 команд, первый успех - на 28?й минуте у второй команды Московского университета.
Узник замка "IF" решил бежать, разобрав по кирпичику стену своей темницы. Для того чтобы скрыть свою работу от надзирателей, он решил избавляться от вывороченных из стены камней через вентиляционное отверстие в полу. Каждый кирпич имеет форму параллелепипеда размером A на B на C дюймов, при этом он настолько прочен, что его невозможно разбить на части. Размер прямоугольного отверстия составляет D на E дюймов (см. рисунок). Целеустремленный пленник до десятых долей дюйма измерил все необходимые параметры и был бы весьма не против узнать, реальна ли его затея.
Необходимо написать программу, которая по исходным значениям A, B, C, D и E выдаст строку "YES", если параллелепипед пройдет в отверстие, и "NO" в противном случае. Все заданные числа лежат в пределах 1 и 10 и могут иметь один десятичный знак после точки.

Сжатие строки
С задачей справились 43 команды, первый успех - на 21-й минуте у команды Нижегородского университета.
Введем понятие сжатой строки, получающейся из исходной строки путем сокращения числа повторяющихся комбинаций. К примеру, строку AAAAAAAAAABABABCCD можно привести к следующему виду: 10(A)2(BA)B2(C)D.
Пусть заданы следующие правила:
· строка, состоящая из прописной латинской буквы, является сжатой;
· если строки S и Q сжаты, то SQ также является сжатой строкой;
· если при разжатии строка S переходит в S', а Q' - в Q', то, будучи разжатой, SQ перейдет в S'Q';
· если строка S является сжатой строкой, то же самое можно сказать и о строке X(S), где X - целое число, большее 1;
· если строка S разжимается в S', то строка X(S) разожмется в повторяющуюся X раз строку S'.
Требуется написать программу, которая сможет сжать заданную строку длиной от 1 до 100 букв так, чтобы получаемая на выходе строка оказалась самой короткой из всех возможных.

Денис Коновальчик