Предположим, перед вами стопка бумаги – работы участников литературного конкурса. На верхнем колонтитуле каждой страницы указаны контакты и имя автора, причём произведения отсортированы по фамилии участников. Коллеги посоветовали прочитать определённого автора, и вот вы смотрите на огромную кучу работ, не решаясь приступить к поиску нужной. За плечо заглядывает друг-программист и с насмешкой заявляет, что ему достаточно увидеть 10 фамилий, что бы отыскать интересующую. Это при том, что работ на столе чуть больше тысячи!
Легко! Ведь это традиционная задача для пробного тура большинства олимпиад по программированию!
В это воскресенье (7 октября) состоялся квалификационный этап международного соревнования ICPC (International Collegiate Programming Contest). В выходной день с 11-00 до 16-00 студенты и аспиранты вузов центрального региона соревновались в скорости написания программ.
Первое место, решив все задачи, заняла команда из МГУ “Red Panda” (в составе Ипатов Михаил, Резников Григорий и Макеев Владислав). Всего приняло участие 370 команд из центрального региона, 88 из них прошли в следующий этап. Четвертьфинал соревнования состоится 20 октября по результатам которого отберут лучшие команды для участия в полуфинале в Санкт-Петербурге. Финалистов в этом учебном году примет португальский город Порту (Porto).
- Как же мне найти нужную работу?
Программист, широко улыбаясь, делит стопку бумаг пополам, читает фамилию верхнего автора и молча откладывает одну часть в сторону. Повторив это действие 9-10 раз, друг протягивает искомое произведение.
- Как так получилось?
- Зная что авторы отсортированы в лексикографическом порядке, я могу посмотрев в середину стопки отбросить из рассмотрения ту половину, в которой интересующей нас фамилии точно нет. Таким образом, после первого деления останется примерно 500 работ, после второго – 250, а после десятого - максимум одна. Если бы на столе лежало миллион работ, нужную я бы нашёл за 20 попыток.
Россия с 1993 года участвует в международном соревновании по программированию и последние 7 лет занимает первое место в финале. Пожелаем нашим ребятам удачи в новом сезоне!
Невструев Дмитрий Сергеевич