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

Турнир. Основное соревнование прошло на наборе из восьми задач (A,B,C,..,I). Предложенные задачи были призваны выявить не только умение владеть навыками программирования, но и способность отыскать в ее вербальной формулировке формальную постановку задачи, позволяющую найти алгоритм решения. Запрограммировав этот алгоритм, участник должен получить результат на предложенных тестовых примерах, что и послужит основанием для оценки жюри олимпиады. Программная поддержка работы жюри в ходе соревнования реализовывалась не только в виде учетных протоколов результатов. Участники могли видеть на своих мониторах общую картину соревнования: кто и сколько задач сделал, затраченное на них время и штрафное время за непринятые попытки представить решения.

В итоге ни одной из команд не удалось решить все задачи, наилучшего результата добились две команды, решившие по шесть задач. Интересно, что всего девять минут понадобилось первой команде-участнице на решение задачи D (см. ее формулировку на сайте http://acm.msu.ru/ или в полной версии статьи на «Мир ПК - диске»), которую решили почти все соревновавшиеся. По нашему мнению, эта задача по своей формулировке, похоже, была очень близка к типовым тренировочным задачам.

В то же время, никому не удалось решить задачу I (см. ее формулировку на сайте http://acm.msu.ru/ или во врезке). Возможная причина -- отношение к игре в теннис, который у этой социальной группы мало популярен.

Ретроспектива и перспектива. Вспоминая события полувековой давности, отмечу, что коллектив, в котором я тогда работал после окончания мехмата МГУ, решал множество задач комбинаторно-вероятностного характера. Их трудно было ставить на ЭВМ из-за ограниченных возможностей машин, и потому приходилось искать точные решения на протяжении продолжительного времени. А сейчас я с удовольствием наблюдаю, как нынешние студенты справляются с подобными задачами в темпе спортивного соревнования. Однако у них возникают другие проблемы -- даже тренеры отмечают, что испытывают серьезные трудности при подготовке команд из-за их слабого образования в рамках обязательных курсов по дискретной математике. И это в таких вузах, как Физтех и МИФИ.

По словам председателя оргкомитета академика В.П. Иванникова, соревнования уже не первый год находят широкий отклик в студенческой среде. Приятно, что интерес к программированию держится на высоком уровне. А заместитель декана факультета ВМК Московского университета Б.И. Березин заметил, что есть надежда провести следующие уже на суперкомпьютере.

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

 

Пример олимпиадной задачи.

Задача D. Пути в графе
Имя входного файла: paths.in
Имя выходного файла: paths.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 Мбайт

Информация о том, что несколько институтов получили нетривиальные результаты после консультации с экспертами корпорации МИФ, распространилась довольно быстро, и Аазу предложили выступить на общем собрании Академии наук с докладом «Научное администрирование: изверги вместо извращенцев».

Однако за час до выступления Ааза поймал запыхавшийся Вася, в этот день работавший на ИСПУГ: «Ааз, у нас снова проблемы. Графы, полученные из последовательностей, не являются совсем простыми, а они требуют позитивный результат».

Оказывается, что от ИСПУГ потребовали, помимо исследования графов на предмет совсем простого устройства (обычно закачивающегося отрицательным вердиктом), отчета по как минимум одной простой задаче с совсем просто устроенными графами. Схема с последовательностями, предложенными Аазом, их уже не устраивала: «Им нужна простая задача на совсем просто устроенные графы? Хорошо. Запиши формулировку: дан неориентированый граф. Сколько в нем простых путей из вершины 1 в вершину N, в которых номера вершин возрастают?»

Аза ушел делать доклад, а Вася задумался, как же эту задачу решать. Помогите ему.

Формат входного файла: файл состоит из одного или нескольких тестов (не более 50). В первой строке каждого теста записаны два числа, N и M, – числа вершин и ребер графа (1< N<20). Далее следуют M строк, каждая из которых описывает одно ребро графа. Строка имеет вид aibi, где ai и bi вершины, соединенные i-м ребром. Граф не содержит кратных ребер и петель. Файл завершается строкой из двух нулей.

Формат выходного файла: Для каждого теста выведите в выходной файл на отдельной строке количество путей. Следуйте формату примера точно.

Задача I. Теннис.

Имя входного файла: tennis.in
Имя выходного файла: tennis.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 Мбайт

Перед отбытием в штаб-квартиру корпорации МИФ Ааз был приглашен вместе с руководителями институтов на теннисный матч. Игра была очень упорной, и матч затягивался.

«Вы не опоздаете?» -- поинтересовался у Ааза секретарь отделения Академии наук.

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

Секретарь отделения, работавший заместителем директора Института вероятностного анализа статистической информации (ИВАСИ), понял, что договор с Федерацией тенниса его институту как минимум не помешает, и тут же на листке бумаги набросал техническое задание.

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

  1. Игрок выиграл шесть геймов, а его противник не более четырех.
  2. Игрок выиграл семь геймов, а его противник пять.

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

Вопрос о подаче решается так: первый подает в нечетных геймах, а второй в четных. Если был тай-брейк в первом сете или в нем было проведено нечетное количество геймов, то второй сет начинается с подачи второго игрока.

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

Для победы на тай-брейке игрок должен выиграть семь розыгрышей при условии, что соперник выиграет не более пяти. Если оба выиграли по шесть розыгрышей, тай-брейк продолжается, пока один из соперников не выиграет количество розыгрышей на два больше. В первом, четвертом, пятом, восьмом, ... розыгрышах на тай-брейке подает первый игрок, во втором, третьем, шестом, седьмом, … розыгрышах -- соперник.

Задача состоит в том, что для заданных вероятностей выигрыша розыгрыша на своей подаче и при предположении независимости друг от друга розыгрышей, необходимо найти математическое ожидание количества розыгрышей в теннисном матче.

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

Формат входного файла: Входной файл состоит из одного или нескольких тестов (не более 100). Тест -- это строка, содержащая два вещественных числа p1,p2, разделенных пробелом, pi -- вероятность победы в розыгрыше на подаче i-го игрока. Вещественные числа содержат не более трех цифр после точки. Файл завершается двумя нулями.

Формат выходного файла: Следуйте максимально точно формату примера. Необходимо вывести не менее шести точных знаков после десятичной точки.