127.0.0.1: /* Форматы правил */

2020-08-30T06:13:16Z

Форматы правил

Новая страница

{{nohate}}
{{moar|лулзов, сфейлившихся участников, фотографий, заданий и программ-решений}}

[[Файл:Zhirobas.jpg|200px|thumb|Типичный участник]]
'''Спортивное программирование''' (''олимпиадное программирование'', ''олимпиады по программированию'', {{Lang-en|competitive programming}}) — решение весёлых и неповторимых абстрактных задач [[задрот]]ами-[[школьник]]ами и к ним приравненными.

== Задачи ==
В зависимости от формата и степени доставления участникам бывают:
* '''алгоритмические''' — несколько задач на контест, которые возможно решить полностью или чуть менее, чем полностью.
* '''оптимизационные''' — одна большая задача, полного решения не существует. Оценивается насколько далеко продвинулось решение участника(ов). В некоторых задачах решения участников взаимодействуют (игры).
* '''исследовательские''' — как в ICFPC, где очки могут начисляются за успешное обнаружение чего-то в объекте.

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

По разным форматам правил проводятся региональные и мировые онсайт-соревнования, интернет-соревнования и онсайт-финалы, ну или просто соревнование проводится один раз в год.

Также существуют сайты, позволяющие задрачивать в любое время суток.

Наиболее успешны обычно те, кто начинает упарываться со школьного возраста.

Особо преуспел как в подготовке спортсменов-программистов, так и в распиаривании этой деятельности, [[Университет ИТМО]].

В этой стране ICFPC широко популяризировался после [http://users.livejournal.com/_adept_/24049.html этого] поста. В 2010 году в топ 100 ICFPC русских комманд было сильно много.

== Форматы правил ==
'''ACM''' — для студентов вузов. Длительность 5 часов. Сдача решений проводится интерактивно, то есть отправленное решение сразу компилируется на сервере и сообщается результат прогона на тестах.
Участвовать в финале чемпионата мира студент может только 2 раза (в отборочных региональных — 5 раз), поэтому топовый вуз будет терять до 3 лучших участников раз в 2 года и должен готовить новое мясо.
Правила ACM являются наиболее популярными также и для разных местных, не связанных с ACM, соревнований (как личных, так и командных).

'''ACM плюс''' — то же самое, что и ACM, но за успешно задачу начисляется не одно очко, а 1 минус 0.2*количество неудачных попыток по ней, поэтому задача, сданная с 6-й попытки или после, [[когнитивный диссонанс|ухудшает результат участника]].

'''IOI''' — для школьников. Решений можно слать много, уже несколько лет можно узнать результаты проверки прямо на контесте и в случае фейла засабмитить с еще одним костылём. К сожалению, чтобы не превращать в ACM, были придуманы токены — две шняги с регеном в полчаса, которые сообщают полные резы (без них доступно только на части тестов). Количество баллов за задачу зависит от количества пройденных тестов (максимальное = 100, иногда дотягивают до 110).

'''Topcoder algorithm''' — для всех желающих. Уникально тем, что вполне полноценно можно играть в одном java-клиенте и не имея у себя никаких компиляторов. Проверка же решений неинтерактивная, то есть о фейле можно узнать в самом конце. Есть веселая возможность попытаться сфейлить решение другого участника, скормив ему неудобоваримые входные данные (но соответствующие условию задачи). Алсо, самый благоприятный для [[читер]]ов формат.

'''Google Code Jam''' — участники получают на каждую попытку рандомно сгенерированный тест и прогоняют его у себя. Поэтому можно использовать почти любой язык.

'''ICFPC''' — оптимизационная или исследовательская задача. На трое суток командой. Поэтому оно больше похоже на настоящее программирование, и не нацелено на школоту.

'''Кто соснул?''' — тоже командная игра, но уже нацеленная на школоту. На любимом языке программирования решается некая задача и сравнивается с решениями на ЯП оппонентов. Результат сравнения трактуется в свою пользу. В ход идут подручные предметы. Популярно в [[S|/pr/]] при подготовке к олимпиадам и просто так.

== Работа жюри ==
Поддерживает работу тестирующей системы, зоопарка компиляторов, пишет задачи, тесты и эталонные решения к задачам, а также отвечает на вопросы участников трёхзначной булевой логикой: YES, NO, NO COMMENT (самый частый ответ). Иногда жюри фейлит и вставляет в набор тесты, не соответствующие условию, и обнаружив это, делает повторное тестирование на исправленном наборе тестов — {{Acronym|реджадж|rejudge}}. Или не делает.

== Личности ==
[[Файл:ITMO team 2015 ACM ICPC.jpg|300px|thumb|Короткевич (справа) второй раз выигрывает ICPC]]
* '''Билл Пучер (Паучер)''' — бессменный директор ACM ICPC, большой любитель классической музыки.
* '''Андрей Станкевич''' — вице-директор Северо-Западного полуфинала АСМ (Россия и СНГ), призёр финалов ICPC 2000 и 2001 года, и вообще тот, на ком сейчас держится вся подготовка команд ИТМО.
* '''Геннадий Короткевич aka [http://codeforces.ru/profile/tourist tourist]''' — студент ИТМО из [[Бульбостан]]а, выступающий за Россию. Обычно считается самым сильным олимпиадником, что подтверждают запредельный рейтинг на этих ваших Codeforces и [[Вин|первые места]] на IOI, ICPC, Google Code Jam, VK Cup, Topcoder Open, Яндекс. Алгоритм и т. д. и т. п. [[Сперва добейся|А чем можешь похвастаться ты, юный падаван?]]
* '''Пётр Митричев aka [http://codeforces.ru/profile/Petr Petr]''' — до прихода Гены был однозначно лучшим ([http://sharpc.livejournal.com/21303.html 40+ фактов о Пете Митричеве]), но вопрос о том, кто сильнейший, ещё открыт. Обе попытки в финалах ACM ICPC частично зафейлил: команда МГУ занимала 2-е места.
* '''Снарк''' — имеет бороду, ведёт открытый кубок (OpenCup), являющийся зеркалом разноместных онсайт-контестов по правилам ACM, также любитель придумывать [[ФГМ|новые правила]] для своих собственных контестов.
* '''Владислав Исенбаев''' [[aka]] Winger — студент ИТМО, победивший в финале ACM 2009 года и зафейливший две последующие попытки попасть в финал, проиграв другой команде собственного университета.
* '''Степан Гатилов''' — студент НГУ, получивший у Медведева [http://www.sbras.ru/HBC/article.phtml?nid=453&id=20 отмазку за пропуски инъяза]
* '''[http://www.mimuw.edu.pl/~tczajka/ Томек Чайка]''' — пшек. Выигрывал как Topcoder Open, так и ACM ICPC. Один из участников знаменитой [http://www.om.edu.pl/stara_wersja/zdjecia_zwardon/1997/zwardon1997_2.html сумасшедшей IT вечеринки] (фотография [http://www.wykop.pl/wpis/8400176/wlasnie-mi-ktos-podeslal-zrodlo-klasycznego-zdjeci/ сделана] в 1997 году в польском математическом лагере, собравшем победителей региональных математических олимпиад для подготовки к международным олимпиадам).
* '''Ferlon''' — яркий пример [[ФГМ|фимоза]] на почве [http://ferlon.livejournal.com/35890.html задротства].

== Холиворы ==
* могут ли олимпиадники заниматься настоящим программированием?
* нужна ли популяризация олимпиадного программирования?
* нужно ли использовать макросы?

;Аргументы за:
* Алгоритмы нужны для разработки чего-то большого и нового. Такую систему, как поиск гугла, невозможно спроектировать с помощью обычных приёмов декомпозиции и паттернов программирования.
* Не удивительно потому, так как крупные корпорации уделяют особое внимание этим соревнованиям и самим олимпиадникам. Победители мировых олимпиад 2000 и 2001 годов [http://vkontakte.ru/kotehok Андрей Лопатин] и [http://vkontakte.ru/id6 Николай Дуров] работали на благо этого вашего [[Вконтакте|Вконтактика]].
* Алгоритмы это наше всё!!!!1111расрас

;Против:
* Олимпиадные задачи могут вообще не иметь никакого отношения к [[быдлокодер|практическому программированию]]. Например, решение может сводиться к вычислению аналитического выражения или выводу на печать константы (да-да, и такое бывает), то есть к области чистой математики. Как правило код, написанный олимпиадниками никто, включая самого автора, потом не поймёт. В серьёзном промышленном программировании, понятный и сопровождаемый код с чёткой архитектурой ценится несравненно выше чем замысловатый и в разы более быстрый, так как зачастую стоимость вычислительных ресурсов ничтожна по сравнению со стоимостью разработки и поддержки. Кроме того оптимизировать, например писать ассемблерные вставки или использовать нетривиальные алгоритмы, имеет смысл только отлаженный код и только в узких местах.
* Задачи, имеющие отношение к компьютерной тематике (например формат PCX или скан-коды клавиатуры) часто содержат ошибки, что как бы намекает на плохие познания авторов в компьютерах.
* Ряд задач сводится к тому, чтобы закодить алгоритм, который есть в учебнике, но которого нет в стандартной библиотеке (типа максимального паросочетания или минимального разреза).
* Решения олимпиадных задач очень короткие (обычно менее 200 строк), которые можно отладить с помощью грубой силы, напильника и кувалды.
* Для решения используются самые базовые средства, чтобы сделать соревнования доступными для как можно большего числа участников. Поэтому можно даже не знать язык, на котором пишешь.
* Заюзать какую-нибудь стороннюю библиотеку хер получится. Алсо, с этим связан фап на java BigInteger, пусть и неудобный, но доступный из коробки (в связи с этим авторы изобретают особо хитрожопые задачи, где длинная арифметика есть, а этот класс бесполезен; давать задачи, где очевидно применение BigInteger считается моветоном).
* О звёздах прошлого обычно ничего примечательного неизвестно, разве только они переходят из участников в жюри. Вероятнее всего, у этого есть свои причины. Так [http://vkontakte.ru/id6 Николай Дуров] (брат того самого) сам убрал себя из [http://vk.com/help.php?page=about списка создателей] Контакта (возможно, опасаясь славы и троллей).

== Фабулы условий задач ==
К каждой задаче обычно придумывают сюжет. Иногда сюжет для уже готовых задач ВНЕЗАПНО меняют перед самым контестом, доставляя немало сюрпризов читающему её. Сюжет как правило не имеет с содержанием ничего общего, а также [https://web.archive.org/web/20090517084914/http://www.youngscience.ru/278/113/1405/index.shtml?id=1747 вводит в заблуждение] [[Медведев]]а.

;Примеры:

{{Цитата|Штирлиц и Мюллер играют в занятную игру, стреляя по очереди. После каждого выстрела кто-нибудь в очереди умирает. Если у еврея не осталось соседей, он в ужасе сам накладывает на себя руки. Пусть в очереди изначально было N человек и Штирлиц хочет убить последнего. Сможет ли он это сделать, если оба игрока будут действовать наилучшим образом?}}

{{Цитата|Организация «Кот в танке» хочет захватить мир. Но у них возникла проблема…}}
Внимательный читатель может заметить, что {{Spoiler|«Кот в танке» — анаграмма одного хорошо известного в этой стране сайта {{Spoiler|ВКонтакте}}}}

{{Цитата|pre=1|Вам дано дерево, сплошь усеянное бобрами. … «Боброжуй-0xFF» работает по следующему принципу: находясь в некоторой вершине u, он может перейти к вершине v, если они соединены ребром, и съесть ровно одного бобра из тех, что находятся в вершине v.
Гарантируется, что бобры будут находиться в шоке от происходящего, поэтому не смогут перемещаться по дереву.}}

{{Цитата|width=auto|В Банановой республике очень много холмов, соединенных мостами. На химическом заводе произошла авария, в результате чего испарилось экспериментальное удобрение «зован». На следующий день выпал цветной дождь, причем он прошел только над холмами, в некоторых местах падали красные капли, в некоторых — синие, а в остальных — зеленые, в результате чего холмы стали соответствующего цвета. Президенту Банановой республики это понравилось, но ему захотелось покрасить мосты между вершинами холмов так, чтобы мосты были покрашены в цвет холмов, которые они соединяют.
К сожалению, если холмы разного цвета, то покрасить мост таким образом не удастся.}}

Была на одном соревновании [http://acm.timus.ru/problem.aspx?space=1&num=1120 задача], в которой авторы сумели особенно отличиться: «В этой задаче нет лихо закрученной формулировки, за уши притянутой к деятельности фирмы СКБ Контур. Более того, в этой задаче вообще нет формулировки».

Ну и [[клюква]] иногда [http://acm.timus.ru/problem.aspx?space=1&num=1450 тоже встречается], куда ж без неё.

== Галерея ==
{{Галерея||center|<gallery widths="180px" perrow="4">
Файл:DSCF8383_JPG_600x450_q85.jpg|
Файл:ACM_2010_(1).JPG|
Файл:ACM_2010_(2).JPG|
Файл:ACM_2010_(3).JPG|
Файл:ACM_2010_(5).JPG|
Файл:ACM_2010.JPG|
Файл:Opening_ceremony2_JM_87.jpg|[[Вин]]
Файл:Acm epic win01.jpg|Epic Win!
Файл:William_Poucher_.jpg|Билл Пучер смотрит на [[быдлокодер]]ов и [[хеллоуворлдщик]]ов, как на…
Файл:Acmicpc-poucher.jpg
Файл:0_karlson_1.jpg|
Файл:0_karlson_2.jpg|
</gallery>}}

== Серверы ==
* [http://codeforces.ru codeforces.ru] — спортивное программирование [[Хабрахабр|c УГ и кармадрочерством]]
* [http://www.topcoder.com/tc topcoder.com] — [[Bredor|примерно то же самое]]
* [http://acm.timus.ru acm.timus.ru] — годный архив задач с уральских соревнований
* [http://spoj.pl spoj.pl] — пшековский сервер, задач [[9000|более 9000]], можно сдавать решения на [[Haskell|хаскеле]] и [[BrainFuck|брэйнфаке]]
* [http://informatics.mccme.ru informatics.mccme.ru] — популярный джадж для школьников
* [http://acm.uva.es acm.uva.es]
* [http://acm.sgu.ru acm.sgu.ru]
* [http://acm.ssau.ru acm.ssau.ru]
* [http://opencup.ru opencup.ru]
* [http://www.e-olimp.com e-olimp.com]
* [https://www.codeeval.com codeeval.com]
* [http://acmp.ru acmp.ru]
* [https://www.codingame.com codingame.com]

* [http://e-maxx.ru/algo/ e-maxx.ru] — популярный сайт с описаниями алгоритмов
* [http://neerc.ifmo.ru/wiki/ neerc.ifmo.ru] — вики ИТМОшников
* [https://algorithmica.org/ru algorithmica.org]

== См. также ==
* [[Демосцена]]

{{software}}
{{Спорт}}
{{Языки программирования}}

Спортивное программирование - История изменений

127.0.0.1: /* Форматы правил */