Чемпионат мира? Легко!
Xakep, номер #032, стр. 032-025-1
Федор Добрянский (Dr.Cod@online.ru)
Что это за чемп и чем его едят? Вот о чем я хочу рассказать тебе, приятель, на этом клочке бумажки. Наглядевшись по телеку сообщений, как наши незагорелые бравые парни надрали по программированию всю планету, ты тихо млеешь. А я тем временем нашепчу тебе, как все бывает на самом деле. Ведь сегодня я в гостях у Московской команды, которая ездила на ЧМпП.
Как попасть?
Для участия ты должен быть студентом. Деканат твоего факультета должен послать тебя на какой-нибудь крупный региональный программер-матч, потом ты занимаешь место, например, в северо-восточном европейском раунде (что-то типа полуфинала) и выходишь на мировой чемпионат. Если честно, то я так до конца и не понял, как это все устроено. Часто деканаты не знают и не хотят знать о таких мероприятиях. Поэтому их придется заставить. Возьми нужную информацию на сайте и иди с нею к начальству. На страничке www.sgu.ru, например, валяются информационные письма к вузам. Вот с таким-то письмом и надо трясти свой деканат, а лучше - ректорат. Наверное, основная проблема в том, чтобы твоей команде выделили средства на поездку в разные города на четвертьфинал, полуфинал и финал (если разрешат).
Что за задачи?
Понятно, что твои программистские способности нужно как-то оценить. Для этого ты с друзьями должен будешь решить до десяти задач. Задачи эти делятся на несколько стандартных групп. В математических задачах нужно реализовать подсчет какой-нибудь формулы. В геометрических понадобится считать площади и длины. В задачах на теорию графов нужно будет париться с древесными алгоритмами, типа нахождения кратчайшего пути. Есть также задачи на перебор, сортировку и поиск слов или букв в строке. Эти задачи называются "из жизни"... Хотя тут сплошная математика или математическое программирование, как тебе больше нравится. При этом у заданий обычно сильно запутанная формулировка на английском языке. Т.е. важно быстро и правильно (!) понять, что от тебя хотят. После того как задача ясна, лучше использовать надежные стандартные алгоритмы.
Как оценивают?
Задачи решаются на скорость, кто быстрее - тот и победил. Никого программный код не волнует. Главное, чтобы программа прошла все тесты, которые держат в секрете. Программа должна уложиться по скорости своей работы в определенные временные рамки. Выигрывает та программа, которая работает быстрее.
Как проходит чемп?
В команде три человека и только один компьютер. Можно пользоваться только компиляторами Паскаля и С++. Каждой команде дают пакет задач на 3-4 часа. Очень важно правильно организоваться и не подраться у компа за клавиатуру. Хорошо, когда в команде есть специалисты по определенным темам. Например, в команде МГУ есть спец по геометрии с Физфака, все знают, что он решит любую задачу по геометрии за 15-30 минут.
Как готовиться?
Прежде всего ты должен отлично знать математику, геометрию, теорию графов, алгоритмы перебора и сортировки. Не помешает раз в неделю, а лучше каждый день решать конкурсные задачи по программированию. Такие задачи можно найти на contest.ur.ru, acm.gui.uva.es/problemset, www.ifmo.ru. Студенты ВМиК МГУ, например, сами организуют олимпиады по программированию для школьников. Им приходится постоянно придумывать и решать задачки.
