Журнал "Компьютерра" N782

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

Тем более что первый шаг к визуализации организаторы давно сделали. К столу команды, решившей очередную задачу, прикрепляется воздушный шарик. Выглядит трогательно.

рекорды Стокгольмский синдрог м инимальны й л икбез

Сто студенческих команд приехало в Стокгольм, чтобы во время пятичасового финала мирового чемпионата по командному программированию (ACM ICPC) решить как можно больше задач из предложенного набора. Порядки довольно строгие. Компьютер на каждую «тройку» всего один. В подмогу, впрочем, дают калькулятор, если кому-то от этого легче. Выходить из зала во время соревнования нельзя. Пользоваться другими электронными устройствами тоже нельзя. Собственно, никаких запрещенных устройств у участников уже нет, у команд изымают все внушающие подозрение предметы (и шансов на то, что нарушителям изъятое вернут, немного). Разрешается иметь при себе лишь бумажный словарь и бумажный же блокнот.

На столиках в сторонке стоят пластиковые упаковки с едой и бутылки воды, но пока почти никто не ест, не до того. Чтобы победить в этом соревновании, нужно решить максимальное количество задач как можно быстрее. Все задачи за пять часов решить невозможно. По крайней мере, ни одной команде в истории ACM ICPC этого не удалось. Не последнюю роль в этом сыграли устроители соревнования. С каждым годом количество заданий увеличивается (в нынешнем году - одиннадцать), а сами задачи усложняются (организаторы пытаются бороться с тем, что команды решают все быстрее и быстрее). «Когда-то мы и подумать не могли, что на задачу можно потратить меньше получаса, - говорит Билл Паучер, в прошлом тренер, потом судья, а теперь исполнительный директор ACM ICPC, -а теперь…»

А теперь за первые пятнадцать минут с задачей А справилось четыре команды: Университет Ватерлоо (Канада), Стэнфорд, Университет Цинхуа и прошлогодние чемпионы, питерский ИТМО. Показатель довольно важный, поскольку на 1СРС имеет значение не только количество решенных задач, но и время, затраченное на их решение. Причем каждый раз отсчет начинается от начала соревнования. Поэтому сначала участникам необходимо решить метазадачу, а именно приблизительно оценить сложность предложенных заданий, и лишь затем приступить к решению простейшей, постепенно наращивая сложность.' Если обе команды решили равное количество за-

U НАТАЛЬЯ БОНДАРЕНКО И ДМИТРИЙ МАТОВ (КОМАНДА CrVJ

П КОМАНДА САНКТ-ПЕТЕРБУРГСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА

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

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

- принято или нет - команда получает довольно быстро, однако каждая неудачная попытка добавляет штрафное время (если задача решена)

Схитрить и взять количеством не получится. Уровень соперников таков, что претендент на победу обязан решить сложную задачу. Медалей АСМ не жалеет - на каждом чемпионате разыгрывается как минимум по четыре комплекта золотых, серебряных и бронзовых медалей. Но чемпион будет только один.

И последняя тонкость. Несмотря на то что команда ИТМО считается одним из фаворитов, в ее составе совсем не те люди, что выиграли чемпионат годом раньше. Жесткую ротацию участников обеспечивают два правила. Во-первых, ни один спортсмен не может участвовать в чемпионате больше двух раз. Во-вторых, ни один университет не может послать на всемирный финал больше одной команды. Таким образом, вчерашним чемпионам нужно заново доказывать право на участие в финале, проходя через внутривузовские и региональные соревнования. Это не очень справедливое по отношению к фаворитам правило подчеркивает, что ACM ICPC - соревнование, в первую очередь, межвузовское.

Уровень вуза, как ни странно, не имеет решающего значения. Ничуть не умаляя заслуг ИТМО (в прошлом