Международная студенческая олимпиада по программированию
Международная студенческая олимпиада по программированию (в английском принято сокращение ACM/ICPC или просто ICPC) — крупнейшая студенческая командная олимпиада по программированию.
История
Международный командный чемпионат по программированию уходит своими корнями в соревнование, проводившееся в Техасском университете в 1970. Свой нынешний облик чемпионат принял в 1977, когда первый финал был проведен в рамках научной конференции ACM, и с тех пор проводится ежегодно.
Организатором олимпиады является влиятельная в компьютерном мире организация Association for Computer Machinery (ACM), а спонсорами соревнований в последние годы являлись компании IBM и Microsoft. С 1977 по 1989 в олимпиаде преимущественно участвовали команды вузов из США и Канады. К настоящему моменту олимпиада превратилась во всемирное соревнование: в 2009 году в ней приняло участие 7109 команд из 88 стран, 100 из которых сошлись в борьбе за главный трофей в финальном турнире. Количество команд продолжает расти на 10-20% в год, так что в будущем соревнования обещают стать ещё представительнее.
Россия и такие страны бывшего СССР, как Азербайджан, Армения, Беларусь, Грузия, Казахстан, Киргизия, Латвия, Литва, Узбекистан, Эстония, входят в Северо-Восточный Европейский регион, ежегодно делегирующий на финальный турнир 10-12 своих лучших команд.
Правила
Олимпиада — командное соревнование. Каждая команда состоит из троих студентов. К участию допускаются студенты высших учебных заведений, а также аспиранты первого года обучения. Студенты, дважды участвовавшие в финальной стадии олимпиады, или пятикратно принимавшие участие в региональном отборе, не допускаются к участию.
Тур олимпиады происходит следующим образом: каждой команде выдаётся компьютер и от восьми до двенадцати задач на пять часов. Команды пишут решения на алгоритмических языках программирования C, C++, Паскале (Паскаль разрешается использовать только на четвертьфинальных и полуфинальных соревнованиях до 2009 года включительно) или Java и посылают их на тестирующий сервер. Программы тестируются на большом количестве различных входных тестов, неизвестных участникам. Если программа выдала неправильный ответ или не уложилась в ограничения по времени или памяти, то пославшая её команда получает об этом сообщение и может послать исправленную версию. Задача считается решённой, если программа выдала правильные ответы на всех тестах. В отличие от других олимпиад, частичные решения не учитываются.
Побеждает команда, решившая правильно наибольшее число задач. Если несколько команд решают одинаковое количество задач, то их положение в рейтинге определяется штрафным временем. Изначально штрафное время каждой команды равно нулю. За каждую правильно сданную задачу к штрафному времени команды прибавляют время, прошедшее с начала соревнования до момента сдачи задачи. Кроме того, если зачтённой попытке предшествовало несколько неудачных попыток сдать ту же задачу, то за каждую из них к штрафному времени прибавляют двадцать минут. За неудачные попытки сдать задачу, которую команде в итоге так и не удалось решить, штрафного времени не начисляется.
От других олимпиад по информатике эта олимпиада отличается повышенным количеством задач, на которые отводится сравнительно небольшое время. Учитывая, что в распоряжении каждой команды находится только один компьютер, навыки эффективной и слаженной командной работы выходят на первый план.
Многие университеты проводят свои олимпиады используя формат ACM ICPC, поскольку данный формат может считаться одним из самых удачных.
Этапы
Олимпиада проводится на нескольких уровнях. Многие университеты проводят внутренние соревнования, чтобы определить своих представителей на региональном уровне. Затем проводятся региональные олимпиады, победители которых отправляются на финальный этап мирового первенства. В региональных соревнованиях один университет может быть представлен несколькими командами, но на финал может отправиться только одна команда от университета.
Победители
Чемпионами мира с 1977 года становились:
Год | Место проведения | Победитель | Состав команды | Тренер |
---|---|---|---|---|
2014 | Россия, Санкт-Петербург | |||
2013 | ?? | |||
2012 | Польша, Варшава | |||
2011 | Малайзия, Куала-Лумпур | |||
2010 | Китай, Харбин | |||
2009 | Швеция, Стокгольм | СПбГУ ИТМО | Владислав Исенбаев, Максим Буздалов, Евгений Капун | Андрей Станкевич |
2008 | Канада, Банфф | СПбГУ ИТМО | Дмитрий Абдрашитов, Дмитрий Паращенко, Федор Царев | Андрей Станкевич |
2007 | Япония, Токио | Варшавский университет | Filip Wolski, Marcin Pilipczuk, Marek Cygan | Jan Madey |
2006 | США, Сан-Антонио | Саратовский государственный университет | Роман Алексеенков, Игорь Кулькин, Иван Романов | Михаил Мирзаянов |
2005 | Китай, Шанхай | Шанхайский университет | Wenyuan Dai, Shuang Zhao, Bohai Yang | Yong Yu |
2004 | Чехия, Прага | СПбГУ ИТМО | Дмитрий Павлов, Павел Маврин, Сергей Оршанский | Андрей Станкевич |
2003 | США, Беверли-Хиллс | Варшавский университет | ||
2002 | США, Гонолулу | Шанхайский университет | Chenxi Lin, Jian Zhou, Jing Lu | Yong Yu |
2001 | Канада, Ванкувер | Санкт-Петербургский государственный университет | Николай Дуров, Андрей Лопатин, Виктор Петров | Дмитрий Ломов |
2000 | США, Орландо | Санкт-Петербургский государственный университет | Николай Дуров, Андрей Лопатин, Олег Етеревский | Наталья Вояковская |
1999 | Нидерланды, Эйнтховен | Университет Ватерлоо | Ondrej Lhotak, Viet-Trung Luu, David Kennedy, Donny Cheung | Gordon Cormack |
1998 | США, Атланта | Пражский университет | Jiri Hajek, Pavel Machek, Martin Mares | Pavel Töpfer |
1997 | США, Сан-Хосе | Харви Мадд Колледж | Brian Carnes, Brian Johnson, Kevin Watkins, Dominic Mazzoni | Robert Keller |
1996 | США, Филадельфия | Университет Беркли | Ben Rudiak-Gould, Amit Sahai, Scott McPeak | Paul Hilfinger |
1995 | США, Нэшвил | Фрайбургский университет | Matthias Ruhl, Christian Wetzel, Phillip Zembrod | |
1994 | США, Феникс | Университет Ватерлоо | Seiji Ando, Ian Goldberg, Ka-Ping Yee | Jo Ebergen |
1993 | США, Индианаполис | Гарвардский университет | Derrick Bass, Tony Hsieh, Craig Silverstein | |
1992 | США, Канзас Сити | Мельбурнский университет | Andrew Conway, Craig Dillon, Stephen Simmons | |
1991 | США, Сан-Антонио | Стэнфордский университет | Michael Patrick Frank, Sean Quinlan, David Magerman, Carl Witty | |
1990 | США, Вашингтон | Университет Отаго | John Gee, Craig McNaughton, Paul Sharp, Bruce Warrington | |
1989 | США, Луисвилл | Университет Лос-Анджелеса | Seth Goldman, Alex Quilici, Matthew Marzbacher, Scott Turner | |
1988 | США, Атланта | Калифорнийский технологический институт | Dave Gillespie, Adam Greenblatt, Ron Goodman, Scott Hemphill | |
1987 | США, Сент-Луис | Стэнфордский университет | Bob Alverson, Tomas Rokicki, Ali Tabibian, Lei Zhu | |
1986 | США, Цинциннати | Калифорнийский технологический институт | Steve Burns, Tim Kay, Dave Gillespie, Steve Rabin, Rajiv Gupta | |
1985 | США, Новый Орлеан | Стэнфордский университет | Michael Dixon, Micheal Hewett, Vivek Sarkar, Joseph Weening | |
1984 | США, Филадельфия | Университет Джона Хопкинса | Michael Baldwin, Robert Strandh, John Walker, Richard Washington | Joseph O'Rourke |
1983 | США, Мельбурн | Университет Небраски | Mark Tuttle, Thane Plambeck, David Leavitt, Paul Petersen | |
1982 | США, Индианаполис | Университет Бэйлора | Keith Hall, Patrick Keane, Jennifer Harmon, Terry Talley | Don Gaitros |
1981 | США, Сент-Луис | Университет Миссури | Christopher Freund, Michael Richey, James Simmons, Catherine Pyron Fieseler | |
1980 | США, Канзас Сити | Университет Сент-Луиса | Steve Karasek, Nathan Schroeder, Mike Zyda, Dave Camp | |
1979 | США, Дэйтон | Университет Сент-Луиса | Steve Karasek, Nathan Schroeder, David Doty, Dave Camp | |
1978 | США, Детройт | Массачусетский технологический институт | ||
1977 | США, Атланта | Мичиганский университет |
Ссылки
- ACM/ICPC — главная страница олимпиады.
- Архив задач Университета Вальядолида
- Архив задач Уральского Государственного Университета
- Архив задач Саратовского Государственного Университета
- Новости соревнований по программированию
- Архив задач Пекинского Университета
- Архив задач Sphere Online Judge (поддерживается более 30 языков программирования)
- Олимпиады по программированию на Физтехе: информация, online-контест МФТИ, учебные материалы по алгоритмам и языкам программирования
- Сообщество русских участников чемпионата в ЖЖ
- Международные индивидуальные соревнования. Могут участвовать не только студенты