Наука побеждать, или тяжело в ученье...
АрхивШесть задач для программистов
Это было недавно...
С 8 по 12 апреля в Технологическом университете голландского города Эйндховена проходил финал командного первенства мира по программированию среди студентов (ACM International Collegiate Programming Contest). В числе 62 команд, получивших право участвовать в финале, было и пять российских. Отрадно, что две из них - команды Санкт-Петербургского института точной механики и оптики и Санкт-Петербургского университета - вошли в десятку лучших команд мира, заняв соответственно третье и девятое места. Питерцы из СПбГИТМО оставили позади команды таких известнейших университетов, как Беркли и Гарвард (подробные результаты см. на acm.baylor.edu/acmicpc/finals/Standings.htm). И ведь такой успех приходит к нашим командам уже не первый раз...
Менее полугода назад, в начале декабря, в Санкт-Петербурге и Барнауле состоялся полуфинал нынешнего первенства. Именно там и решалось, какие команды завоюют право поехать в Голландию. Вот уже третий год подряд Санкт-Петербург и Барнаул становятся своеобразными "программистскими Мекками" для студентов из России и ближнего зарубежья. С каждым разом в соревнование вовлекается все больше и больше вузов, а значит, будущие программисты получают возможность оценить свои силы реально, по гамбургскому счету. В этом году в России впервые состоялись не только полуфинал, но и четвертьфиналы (ибо два полуфинала просто физически не смогли бы принять всех желающих). Что же это за чемпионат, о котором подавляющее большинство читателей даже и не слышало?
...Это было давно
Давным-давно, когда еще не родились ни Билл Гейтс, ни другие отцы современного компьютерного бизнеса... В общем, в 1946 году сотрудники Пенсильванского университета создали первый компьютер - ENIAC. Год спустя разработчики ENIAC'а объединились и основали Association for Computing Machinery (ACM). Ныне ACM выросла в авторитетнейшую международную организацию со штаб-квартирой в центре Манхэттена. Ежегодно в феврале-марте на компьютерную неделю ACM съезжаются все ведущие разработчики харда и софта, а награду ACM Annual Meeting Turing Award заслуженно называют нобелевской премией в области компьютеров. В рамках компьютерной недели проводятся самые разнообразные мероприятия. Например, в 1996 году Гарри Каспаров играл здесь свой первый матч с Deep Blue.
С тех пор вот уже более двадцати лет в рамках этой ежегодной недели проводятся командные чемпионаты мира среди студентов высших учебных заведений. Как и в профессиональном хоккее, сначала это были междусобойчики для североамериканских команд, но постепенно европейцы, австралийцы и новозеландцы начали их "бить" и все больше приближаться к заветным чемпионским званиям. Расширившаяся география привела к тому, что ныне в Европе проводится не один, а несколько региональных полуфиналов. Благодаря успехам питерских команд в соревнованиях Северо-Западного Европейского региона в 1995-96 годах, право проведения соревнований в Северо-Восточном регионе было отдано Санкт-Петербургу.
Как это происходит?
Я не был в Голландии, но могу рассказать о полуфинале. В уютных помещениях Аничкова Дворца расставлены компьютеры, проложена локальная сеть. Организаторы запускают контролирующую программу, участники получают задания, и... поехали! По правилам чемпионатов ACM связь с жюри во время тура происходит в режиме реального времени. Если программа проходит все тесты, задача считается решенной, если нет - засчитывается штрафная попытка. Успехи или неудачи участников видны прямо по ходу решения задач, а команда-победитель определяется сразу же по истечении времени, не отходя от кассы: кто решил больше задач и набрал меньше штрафного времени, тот и победил.
Гладко это выглядит только на бумаге. А вот представьте, что вы сидите втроем у одного компьютера, бьете пальцами по слегка не новой клавиатуре и в условиях слегка неработающей сети лихорадочно пытаетесь решить, запустить и сдать жюри восемь задач. На все про все - шесть часов...
Я выбрал для публикации несколько понравившихся мне задач с санкт-петербургского полуфинала и одну - с финала. Прошу прощения за то, что в целях экономии места я опустил технические подробности, спецификации и примеры. Пусть словам будет тесно, а мыслям - просторно. Все хорошее, что есть в этих задачах, заложено туда их авторами, а за погрешности перевода и сокращения текста отвечаю я.
Желающие увидеть канонические тексты задач (причем не только задач этого года, но и архивы прошлых лет) могут сходить на www.ifmo.ru/neerc. В частности, задачи последнего полуфинала можно загрузить с www.ifmo.ru/neerc/98/neerc98.zip.
Финальные задачи (в формате Word) можно увидеть на acm.baylor.edu/acmicpc/finals/Problems/Problems.doc. О региональных студенческих соревнованиях, проводимых в России, можно узнать на сервере Уральского университета: www.usu.ru/win/usu/events/1998/contest98 и www.usu.ru/win/usu/events/1997/contest. В частности, на второй из этих страниц есть ссылка на интереснейшую статью уральских студентов "Как стать чемпионом мира по программированию, или Разбор полетов". Наконец, подробная информация на английском языке (правила соревнований, задачи, решения, ссылки на другие страницы) есть на acm.baylor.edu.
Фальшивая монета
Банк "Gold Bar" получил достоверную информацию, что в выпущенной им группе из N монет одна монета является фальшивой и отличается по весу от других (все остальные монеты весят одинаково). После экономического кризиса в банке остались только простые рычажные весы.
Чтобы обнаружить фальшивую монету, служащие банка перенумеровали все монеты целыми числами от 1 до N. Затем они стали взвешивать различные группы монет, помещая равные количества монет на левой и правой чашах весов. Номера монет и результаты взвешиваний фиксировались.
Напишите программу, которая по результатам взвешиваний определит номер фальшивой монеты.
Забор
Участок ограничен забором высотой h. Проекция участка на плоскость имеет форму многоугольника (без самопересечений), определенного декартовыми координатами (Xi, Yi) своих N вершин. В точку с координатами (0, 0) помещена лампа. Лампа может быть расположена вне или внутри участка, но не на его стороне (см. рис.).
Забор совершенно черный, то есть не отражает, не рассеивает и не пропускает свет. Интенсивность света, падающего на произвольную точку забора, определяется по формуле , где k - известное постоянное значение, не зависящее от местоположения точки, r - расстояние между точкой и лампой. Освещенность бесконечно узкого вертикального кусочка шириной dl и высотой h равно,
dl=I0*|cos alpha|*dI*hНапишите программу вычисления полной освещенности забора, то есть суммы освещенностей всех сторон.
Парламент
Парламент Глупландии нового созыва состоит из N делегатов. По правилам, делегаты должны быть разделены на непересекающиеся фракции разной численности, и ежедневно каждая фракция должна посылать одного делегата в согласительную комиссию. Состав согласительной комиссии каждый день должен быть различным. Парламент работает до тех пор, пока может формировать согласительные комиссии, удовлетворяющие этим правилам.
Напишите программу, которая определит, сколько делегатов должно быть в парламентских фракциях, чтобы парламент мог работать максимально долго.
Дефрагментация
Вы - член группы разработчиков операционной системы New Generation и файловой системы NG. В системе все дисковое пространство разделено на N равных кластеров, пронумерованных от 1 до N. Каждый файл занимает один или больше кластеров в произвольных местах диска. Все кластеры, не занятые файлами, считаются свободными. Файл читается с диска быстрее всего, если все его кластеры расположены в последовательных кластерах диска в естественном порядке.
Так как диск вращается с постоянной скоростью, то для доступа к кластерам требуются различные промежутки времени. Кластеры, расположенные в начале диска, читаются быстрее, чем расположенные в конце. Поэтому все файлы заранее нумеруются целыми числами от 1 до K - в порядке убывания частоты, с которой бывает необходимо к ним обращаться. При оптимальном размещении файлов на диске файл 1 будет занимать кластеры 1, 2, ..., S1; файл 2 будет занимать кластеры S1 + 1, S1 + 2, ..., S1 + S2 и так далее (здесь Si - число кластеров, занимаемых i-м файлом).
Чтобы разместить файлы на диске оптимальным образом, выполняется серия перемещений кластеров. Одно перемещение включает чтение одного занятого кластера с диска в память и запись его содержимого в некоторый свободный кластер. После того как это сделано, первый из них освобождается, а второй объявляется занятым.
Разместите файлы на диске оптимальным способом, выполнив минимально возможное число перемещений кластеров.
Spell checker
Вы, как член команды разработчиков новой программы проверки правописания, должны написать модуль, проверяющий правильность данных слов с помощью известного словаря всех правильных слов во всех их формах.
Если слово отсутствует в словаре, оно может быть заменено правильными словами (из словаря), полученными одним из следующих действий:
Напишите программу, которая найдет все возможные замены для каждого данного слова.
Ограда участка
В тридевятом царстве жил-был король, который владел большой коллекцией ценных и редких деревьев, собранной усилиями многих поколений предков. Дабы защитить коллекцию от воров, король поручил своему визирю соорудить ограду вокруг участка с ценными деревьями.
Визирь, однако, сообразил, что изготовить ограду можно из тех же деревьев. Другими словами, он должен срубить часть деревьев так, чтобы древесины хватило на возведение забора вокруг остальных деревьев. Разумеется, визирь хочет сделать ограду, срубив наименее ценные деревья.
Ваша задача - написать программу, минимизирующую суммарную цену срубленных деревьев. Исходные данные: общее количество деревьев, координаты каждого дерева на участке, цена и длина забора, который можно сделать из данного дерева.
