Здравствуй!
Пишет тебе девятиклассник, призер регионального этапа всероссийской олимпиады по информатике. В последнее время я стал замечать, что у читателей повысился интерес к олимпиадам по программированию. Как их активный участник я постараюсь ответить на все вопросы, рассказать о своем пути, привести примеры реальных, запомнившихся мне задач.
Об обучении
Учусь я в школе с углубленным изучением физики, математики и информатики.
Что же это за школа, как в ней учиться и как в нее поступить?
Отбор проходит в два этапа. Первый - экзамен по физике и математике. После него некоторые счастливчики попадают на собеседование, где от них требуется решить несколько олимпиадных задач по математике. И только после этого самые умные и удачливые становятся учениками.
Учиться очень тяжело и сложно. Учителя требуют идеального знания чуть ли не всех предметов. На родительском собрании сказали: «В начале обучения абсолютно все ученики скатываются до двоек, даже отличники. Те, кто начинают реально учиться - получают хорошие оценки. Остальные отсеиваются». У меня больше всего было проблем с русским языком и литературой, как бы это ни было странно.
Меня всегда привлекало программирование (что это такое я понял аж в 4 классе). Я был очень рад, когда в седьмом классе начали преподавать Pascal и различные вычислительные алгоритмы. Именно тогда я написал первый «Hello World!», алгоритм Евклида; изучил условные операторы, циклы, массивы.
С восьмого класса учителя приглашали на факультативы по информатике, где мы изучали графы, алгоритмы сортировки массивов и многое другое.
Задачи
Посмотрим на совершенно типичную задачу для начинающих программистов-олимпиадников
Пятью пять - двадцать пять!
(Время: 1 сек. Память: 16 Мб Сложность: 8%)
Вася и Петя учатся в школе в одном классе. Недавно Петя поведал Васе о хитром способе возведения в квадрат натуральных чисел, оканчивающихся на цифру 5. Теперь Вася может с легкостью возводить в квадрат двузначные (и даже некоторые трехзначные) числа, оканчивающиеся на 5. Способ заключается в следующем: для возведения в квадрат числа, оканчивающегося на 5 достаточно умножить число, полученное из исходного вычеркиванием последней пятерки на следующее по порядку число, затем остается лишь приписать «25» к получившемуся результату справа. Например, для того, чтобы возвести число 125 в квадрат достаточно 12 умножить на 13 и приписать 25, т.е. приписывая к числу 12*13=156 число 25, получаем результат 15625, т.е. 1252=15625. Напишите программу, возводящую число, оканчивающееся на 5, в квадрат для того, чтобы Вася смог проверить свои навыки.
Входные данные
В единственной строке входного файла INPUT.TXT записано одно натуральное число А, оканчивающееся на цифру 5, не превышающее 4*105.
Выходные данные
В выходной файл OUTPUT.TXT выведите одно натуральное число - A2 без лидирующих нулей.
Примеры:
INPUT.TXT
5
75
4255
OUTPUT.TXT
25
5625
18105025
Требования
От олимпиадника требуется написать программу на одном из принимаемых языков (обычно этот набор состоит из Pascal (сам пишу, никогда проблем не было), Delphi, C++, Java, Visual Basic, в последнее время добавляют C#). После этого исходный файл отправляется в систему-песочницу, где он компилируется и выполняется на группе тестов. За каждый тест участник олимпиады получает некоторый балл, которые потом складываются. После олимпиады результаты становятся видны всем. Чем больше суммарный балл - тем выше место.
Стоит отметить, что обычно проверяющими системами плохо обрабатывается управляемый код (Java, C#). Мой друг лично на региональном этапе получил на трех из четырех задач 0 баллов из-за ошибки во время выполнения (писал на C#), хотя проверялось все нормально. Что делать в таком случае не понял ни я, ни он; на апелляции жюри просто пожали плечами.
Риски
На чем можно проиграть? Существуют 7 типов ошибок:
Скрытый текст
Wrong answer
Неверный ответ. Результат работы программы не совпадает с ответом жюри
Неверный формат вывода или алгоритмическая ошибка в программе
Time limit exceeded
Превышен указанный в задаче лимит времени. Программа выполняется дольше установленного времени
Неэффективное решение или алгоритмическая ошибка в программе
Presentation Error
Отсутствие выходного файла OUTPUT.TXT
Файл не создан, неверное имя файла или сбой программы до открытия выходного файла
Compilation error
Ошибка компиляции. В результате компиляции не создан исполняемый файл
Синтаксическая ошибка в программе или неверно указано расширение файла. Возможно, что при реализации на языке Java был использован класс, отличный от Main
Memory limit exceeded
Превышен указанный в задаче лимит памяти. Программа использует больше установленного размера памяти.
Неэффективный алгоритм, либо нерациональное использование памяти
Runtime error
Ошибка исполнения. Программа завершила работу с ненулевым кодом возврата. В этом случае результат работы не проверяется
Возможно, в программе произошло обращение к несуществующему элементу массива, деление на ноль и т.д. Возможно, программа на C++ не завершается оператором «return 0» или по иной причине вернула ненулевой код возврата
Олимпиады
Как проходит всероссийская олимпиада по информатике?
Я прошел всего 5 этапов: 8-9 классы в школе, 8-11 классы в школе, муниципальный этап, дистанционный тур региональной олимпиады, региональная олимпиада. Далее идет всероссийский тур, но я на него, к сожалению, не попал. Сейчас я расскажу про те задачи, которые мне очень понравились.
Этап среди старшеклассников
Во время тура среди 8-11 классов была задача «Полиномиальные хэш функции» условие которой было записано на двух страницах формата A5. В этом условии была приведена краткая информация о хэш функциях, их истории, была предложена одна такая функция. Задача заключалась в её вычислении для массива входных данных. Нас испугало очень страшное название, сложная терминология, запись суммы её значком (тот который выглядит как буква E) и в результате её мало кто вообще начал решать. Условие сейчас найти, к сожалению, не смогу.
Муниципальный этап
Муниципальный этап получился просто убийственным по сложности.
Вот задача оттуда
Б. Бобр
Ограничения по памяти: 64 Мб
Бобр собирается построить каскад плотин и уютную хатку в русле неширокой реки. Так получилось, что река протекает по идеально прямой траектории, и ширина реки настолько мала, что в рамках данной задачи мы можем ею пренебречь. На берегах реки стоят деревья, которые бобр может использовать для строительства. Ученые решили выяснить, насколько оптимально бобр выбирает места для строительства плотин и хатки с точки зрения минимального суммарного расстояния, на которое необходимо переносить деревья.
Напишите программу, которая по заданным координатам деревьев относительно начала прямого участка реки, если считать ось сонаправленной течению определяет координаты объектов, соответствующие минимальному суммарному расстоянию, на которое необходимо переносить деревья.
Формат входных данных:
<=T<=10 – количество тестовых блоков, идущих друг за другом. В первой строке каждого тестового блока содержится два целых положительных числа 1<=N<=1000, 0<=М<=10, 0<=L<=100 – соответственно количество деревьев, растущих на берегах реки, количество деревьев, необходимое для возведения одного объекта и количество объектов, которые необходимо возвести. В каждой из следующих N строчек записано единственное положительное вещественное число – расстояние в метрах от начала прямого участка реки (самого высокого по течению) до места, где растет соответствующее дерево. Известно, что деревьев гарантированно хватает, чтобы построить все объекты (N>=M*L)
Формат выходных данных:
Для каждого тестового блока в отдельной строке необходимо вывести единственное число - сумму координат мест, в которых необходимо возвести объекты, чтобы суммарное расстояние, на которое потребуется перенести деревья для строительства, было минимальным, указав три точных знака после десятичного разделителя.
Входные данные
2
5 3 1
0.1
1.2
5.6
7.3
9.4
2 2 1
1
2
Выходные данные
7.300
1.000
Решить задачу, если объект один достаточно просто. Но когда объектов больше - приходится применять достаточно сложный раздел программирования, «Динамическое программирование». Учитель, который вел у нас факультатив признался в том, что он плохо представляет как решить эту задачу (совместными усилиями мы вывели значение, которое нужно минимализировать, просто построив несколько графиков, даже не спрашивайте что это за значение - я его благополучно забыл).
В результате задачу на полный балл решил лишь один участник олимпиады.
А вот еще одна задача, решение жюри на которой было пересмотрено (из того же муниципального этапа):
А. Альбатрос
Ограничения по времени: 1 секунда на тест
Ограничения по памяти: 64 Мб
Альбатрос может совершать длительные перелеты, преодолевая длинные расстояния над просторами океана. Орнитологи решили определить, сколько километров может пролететь альбатрос, не посещая сушу. Для этого флотилия плавучих исследовательских лабораторий рассредоточилась по океану и записала данные об изучаемой особи, к которой прикреплена радиометка. Ученые фиксируют момент времени и текущие координаты того места, где они обнаружили альбатроса.
Напишите программу, определяющую расстояние, которое преодолел альбатрос в течение эксперимента, если считать, что в зоне наблюдений наша планета представляет собой идеальный шар радиусом 6366,197 километров.
Формат входных данных:
В первой строке входных данных содержится единственное целое положительное число 1<=T<=10 – количество тестовых блоков, идущих друг за другом. В первой строке каждого тестового блока содержится единственное целое положительное число 2<=N<=1000, количество записей о появлении альбатроса. В каждой из следующих N строчек записаны по двенадцать целых неотрицательных чисел (0<=d1<=90, 0<=m1<=90, 0<=s1<=90, 0<=d2<=90, 0<=m2<=90, 0<=s2<=90, 0<=h<=23, 0<=mt<=59, 0<=sec<=59, 1<=dd<=31, 1<=mm<=12, 2000<=yy<=2012) – соответственно градусы минуты и секунды северной широты, градусы, минуты и секунды западной долготы того места, где плавучая исследовательская лаборатория заметила альбатроса; время в формате часы, минуты, секунды и дата наблюдения в формате день, месяц, год.
Формат выходных данных:
Для каждого из тестовых блоков в отдельной строке необходимо вывести единственное целое число – расстояние, которое преодолел альбатрос, округленное до ближайшего четного целого числа.
Пример входных и выходных данных:
Входные данные
2
3
0 0 0 0 0 0 0 0 0 1 1 2012
0 0 0 0 2 0 0 0 0 3 1 2012
0 0 0 0 1 0 0 0 0 2 1 2012
2
0 0 0 0 0 0 0 0 0 1 1 2012
0 0 0 0 1 0 0 0 0 2 1 2012
Выходные данные
4
2
Достаточно простая задача: необходимо отсортировать значения по дате появления Альбатроса, вычислить длину каждой дуги между двумя точками, а потом их все сложить. В решении принимается допущение, которое позволяет использовать теорему Пифагора.
Но почему же решение было пересмотрено? Взглянем на диапазон минут и секунд.
0<=m1<=90, 0<=s1<=90
Вы, наверное, наивно предположили, что в одном градусе 60 минут? Или что в одной минуте 60 секунд? Ха-ха! Тут же явно написано «90».
Тесты были составлены именно с учетом перевода: в одном градусе 60 минут, в одной минуте 60 секунд. Это безобразие было успешно оспорено нашими учителями.
Самое обидное, что даже пример получился неправильный
В результате задачу не решил, по-моему, вообще никто.
Полный текст муниципального этапа можно найти .
Дистанционный тур
Задачи дистанционного тура были гораздо интереснее. Мне запомнились две задачи.
Вот первая
Г. Герой дня
Ввод/вывод: стандартный
Медиахолдинг «Пермь Великая» отслеживает сообщения блоггеров Пермского края и каждый день пытается выяснить, кто является наиболее популярным в записях для того чтобы включить этого человека в традиционную рубрику «Герой дня».
Для каждой записи, попавшей в список отслеживания, известно количество просмотров и те персоналии, которые в ней упоминаются. Напишите программу, определяющую человека, для которого суммарное количество просмотров для записей, где он упоминается, максимально.
Формат входных данных:
В первой строке входных данных приводится единственное целое число 1<=L<=10000 – количество записей, попавших в обзор за текущий день. В каждой из следующих строк вначале указывается число – количество просмотров соответствующей записи и затем имена и фамилии людей, упоминающихся в записи. Имена и фамилии состоят из букв английского алфавита, число, а также все соседние слова отделяются друг от друга ровно одним пробелом. Суммарная длина строки составляет не более 200 символов.
Формат выходных данных:
В единственной строке выходных данных необходимо вывести имя и фамилию человека, записи с упоминанием которого набрали больше всего просмотров. Если таких людей несколько нужно вывести того, кто идет раньше других по алфавиту.
Входные данные
1
100500 John Travolta John Lennon
5
5 Vasya Pupkin Sergey Syroezhkin
10 Harry Potter
5 Garry Potter Vasya Pupkin
5 Sergey Syroezhkin
12341234463456234123466543342 Arnold Schwarzenegger
Выходные данные
John Lennon
Arnold Schwarzenegger
Именно после этой задачи мне пришла идея «словаря», тип данных с удобным поиском по людям. Если кому интересно - напишу в комментариях, можете спросить в ЛС, но чувствую что это тот еще велосипед.
Необходимо составить список из людей с общим количеством просмотров (посмотрите на человека с идентификатором Arnold Schwarzenegger, требуется длинная арифметика), а затем просто выбрать нужного человека из нашего списка. Чтобы упростить алгоритм наши одиннадцатиклассники использовали хэш-функцию для имени (сумма всех ASCII номеров символов в имени), что существенно ускорило работу программы, коллизии получились небольшими.
Вторая задача или задача архивации
В. Великий архиватор
Ввод/вывод: стандартный
Ограничения по времени: 1 секунда
На планете роботов очень любят автоматическую обработку текстов. Для этого роботы ввели специальную должность Великого Архиватора. В обязанности Великого Архиватора входит составление списка всех слов текста и замена слов на число, обозначающее номер этого слова в списке.
Напишите программу, выполняющую функции Великого Архиватора.
Формат входных данных:
В единственной строке входных данных приводится строка длиной не более миллиона символов, состоящая из строчных и заглавных букв английского алфавита и пробелов. Любые два соседних слова в тексте разделены ровно одним пробелом. Слова считаются одинаковыми, если они равны с точки зрения сравнения строк, причем строчные и заглавные буквы считаются различными.
Формат выходных данных:
В единственной строке выходных данных необходимо вывести последовательность номеров слов текста, причем слова в списке должны быть упорядочены в порядке их появления в тексте. Нумерация слов должна начинаться с единицы.
Примеры входных и выходных данных:
Входные данные
To be or not to be
Why do you cry Willie Why do you cry Why Willie Why Willie Why Willie Why
Выходные данные
1 2 3 4 5 2
1 2 3 4 5 1 2 3 4 1 5 1 5 1 5 1
Пояснение к примерам входных и выходных данных: текст во втором примере не содержит символов перевода строки и возврата каретки.
Достаточно простой алгоритм сжатия (не помню как называется). Мне было интересно реализовать. Я решил эту задачу созданием массива из слов, добавлял туда первое слово. Затем считывал каждое следующее слово, проверял, нет ли его в массиве. Если оно было - записывал в выходной поток номер слова, иначе - добавлял в массив, записывал номер.
В принципе, мое решение не получило полный балл.
Полный текст заданий можно найти .
На дистанционном туре я занял 1 место среди девятиклассников.
Региональный этап
На этапе региональном было не так весело, тура было два. Я боялся подвести школу и не пройти на следующий этап, плохо показать нашу школу. Поэтому и задания воспринимались не так весело и приятно. В общем: ничего не запомнил оттуда, но получил заветный диплом. Да и условия мне не удалось найти.
На второй день к нам приехали представители местной компании «Прогноз», поиграли с нами в «Что? Где? Когда?», провели викторину. Победителям раздали призы.
Подготовка
Как же я готовился?
Ответ достаточно прост: у меня хорошие учителя. Мне это было интересно и я получал от всего происходящего удовольствие. Я усердно готовился и добился того, чего хотел.
Что делать, если Вам это тоже интересно и Вы хотите принять во всем этом участие?
- Существуют системы подготовки школьников к олимпиадам по программированию, на них есть тестовая система и куча условий с решениями. Насколько я понимаю, на всех таких системах нужна регистрация. Я готовился при помощи двух:
- acmp.ru/ Есть достаточно много задач разной сложности, так же интересен раздел «Курс олимпиадника»
- http://acm.timus.ru/ Куча задач с самых разных олимпиад, некоторые на английском. В разделе http://acm.timus.ru/offline у нас проводился дистанционный и региональный этапы.
- Существуют онлайн олимпиады, я участвовал лишь в одной: NetOI от украинцев. Отзыв такой: ХАРДКОР!!! Дальше второго тура не прошел. Код нужно писать ужасно оптимально (я так не умею), для каждого теста индивидуальные условия (удвоенное время программы жюри).
Что же дальше?
Говоря это, я подразумеваю вопрос о том, насколько олимпиадники приспособлены к работе в реальных условиях.
Хоть я и не работал еще в IT индустрии, но я считаю: олимпиадники никак не приспособлены к реальной работе. На таких олимпиадах требуется уметь быстро изобрести «велосипед», знать хорошо алгоритмы. Я с другом занимаюсь написанием небольших игр и понимаю, что гораздо важнее уметь выбрать правильную технологию для твоих целей, уметь найти готовое решение чтобы ускорить разработку, «Велосипеды не нужны». Поправьте меня, если это не так.
Если кого интересует то, чего я в жизни хочу: на самом деле я не очень-то люблю IT и информатику, мечта моя - выучиться на физика-теоретика и заниматься исследованиями. А так как в РФ с этим проблемы я планирую уехать в Канаду или США.
Приму любые пожелания в ЛС или в комментариях. Надеюсь, данная статья не получилась длинной. Надеюсь она была для Вас интересна. Надеюсь Вас не раздражала моя неграмотность, уж очень я плохо знаю пунктуацию.
Демонстрации:
- indy256"s CodeLibrary (GitHub)
- R. Sedgewick and K. Wayne"s Java Algorithms and Clients (GitHub)
Книги
Алгоритмы (классические учебники)
- Introduction to Algorithms / Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. — 3rd ed. — Cambridge, MA: MIT Press, 2009. — 1292 p. (сайт книги)
- Sedgewick R., Wayne K. Algorithms / Robert Sedgewick, Kevin Wayne. — 4th ed. — Boston, MA: Addison-Wesley, 2011. — 976 p. (сайт книги)
- Skiena S. The Algorithm Design Manual / Steven S. Skiena. — 2nd ed. — London: Springer-Verlag, 2008. — 746 p. (сайт книги)
Олимпиадное программирование
- Art of Programming Contest / Ed. by A. S. Arefin. — 2nd ed. — Dhaka: Gyankosh Prokashoni, 2006. — 247 p.
- Halim S. Competitive Programming / Steven Halim, Felix Halim. — Raleigh, NC: Lulu, 2010. — 152 p.
- Долинский М. С. Решение сложных и олимпиадных задач по программированию / М. С. Долинский. — СПб.: Питер, 2006. — 366 с.
- Окулов С. М. Основы программирования / С. М. Окулов. — 4-е изд. — М.: БИНОМ, 2008. — 440 с.
- Окулов С. М. Программирование в алгоритмах / С. М. Окулов. — 3-е изд. — М.: БИНОМ, 2007. — 383 с.
- Порублев И. Н., Ставровский А. Б. Алгоритмы и программы. Решение олимпиадных задач. — М.: Вильямс, 2007. — 480 с.
- Скиена С. С., Ревилла М. А. Олимпиадные задачи по программированию. Руководство по подготовке к соревнованиям / С. С. Скиена, М. А. Ревилла. — М.: КУДИЦ-ОБРАЗ, 2005. — 416 с.
Сборники задач
- Алексеев А. В., Беляев С. Н. Подготовка школьников к олимпиадам по информатике с использованием веб-сайта / А. В. Алексеев, С. Н. Беляев. — Ханты-Мансийск: РИО ИРО, 2008. — 284 с.
- Брудно А. Л., Каплан Л. И. Московские олимпиады по программированию / Под ред. Б. Н. Наумова. — 2-е изд. — М.: Наука, 1990. — 208 с.
- Кирюхин В. М., Окулов С. М. Методика решения задач по информатике. Международные олимпиады / В. М. Кирюхин, С. М. Окулов. — М.: БИНОМ, 2007. — 600 с.
- Московские олимпиады по информатике / Под ред. Е. В. Андреевой, В. М. Гуровица и В. А. Матюхина. — М.: МЦНМО, 2006 — 256 с.
- Московские учебно тренировочные сборы по информатике. Весна–2006 / Под ред. В. М. Гуровица. — М.: МЦНМО, 2007 — 194 с.
- Меньшиков Ф. В. Олимпиадные задачи по программированию / Ф. В. Меньшиков. — СПб: Питер, 2006. — 315 с.
- Особенности национальных задач по информатике / В. И. Беров, А. В. Лапунов, В. А. Матюхин, А. Е. Пономарёв. — Киров: Триада-С, 2000. — 160 с.
- Шень А. Программирование: теоремы и задачи / А. Шень. — 2-е изд. — М.: МЦНМО, 2004 — 296 с.
Литература по темам
Алгоритмы и структуры данных
- Erickson J. Algorithms / Jeff Erickson. — Urbana, IL: University of Illinois at Urbana-Champaign, 2015. — 514 p.
- Sedgewick R., Flajolet P. An Introduction to the Analysis of Algorithms / Robert Sedgewick, Philippe Flajolet. — 2th ed. — Boston, MA: Addison-Wesley, 2013. — 592 p.
- Ахо А., Хопкрофт Д., Ульман Д. Построение и анализ вычислительных алгоритмов / А. Ахо, Дж. Хопкрофт, Дж. Ульман. — М.: Мир, 1979. — 536 с.
- Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы / Альфред В. Ахо, Джон Хопкрофт, Джеффри Д. Ульман. — М.: Вильямс, 2000. — 384 с.
- Бабенко М. А., Левин М. В. Введение в теорию алгоритмов и структур данных / М. А. Бабенко, М. В. Левин. — М.: МЦНМО, 2016. — 144 с.
- Вирт Н. Алгоритмы и структуры данных / Н. Вирт. — М.: Мир, 1989. — 360 с.
- Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы / С. Дасгупта, Х. Пападимитриу, У. Вазирани. — М.: МЦНМО, 2014. — 320 с.
- Клейнберг Дж., Тардос Е. Алгоритмы: разработка и применение / Джон Клейнберг, Ева Тардос. — СПб: Питер, 2016. — 800 с. (слайды лекций)
- Левитин А. В. Алгоритмы: введение в разработку и анализ / Ананий В. Левитин. — М.: Вильямс, 2006. — 576 с.
- Макконнелл Дж. Анализ алгоритмов. Вводный курс / Дж. Макконнелл. — М.: Техносфера, 2002. — 304 с.
- Стивенс Р. Алгоритмы. Теория и практическое применение / Род Стивенс. — М.: Э, 2016. — 544 с.
Дискретная математика
- Асанов М. О. Барановский В. А., Расин В. В. Дискретная математика: графы, матроиды, алгоритмы / М. О. Асанов, В. А. Барановский, В. В. Расин. — СПб.: Лань, 2010. — 368 с.
- Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики / Р. Грэхем, Д. Кнут, О. Паташник. — М.: Мир, 1998. — 703 с.
- Кук Д., Бейз Г. Компьютерная математика / Д. Кук, Г. Бейз. — М.: Наука, 1990. — 384 с.
- Новиков Ф. А. Дискретная математика для программистов / Ф. А. Новиков. — 2-е изд. — СПб.: Питер. 2007. — 364 с.
- Окулов С. М. Дискретная математика. Теория и практика решения задач по информатике / С. М. Окулов. — 2-е изд. — М.: БИНОМ, 2012. — 422 с.
- Хаггарти Р. Дискретная математика для программистов / Р. Хаггарти — М.: Техносфера, 2004. — 320 с.
Вычислительная геометрия
- Computational Geometry: Algorithms and Applications / Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars. — 3rd ed. — Berlin: Springer-Verlag, 2008. — 386 p.
- Андреева Е. В., Егоров Ю. Е. Вычислительная геометрия на плоскости / Е. В. Андреева, Ю. Е. Егоров. // Информатика. — 2002. — №39, 40, 43, 44
- Препарата Ф., Шеймос М. Вычислительная геометрия / Ф. Препарата, М. Шеймос. — М.: Мир, 1989. — 478 с.
Этот раздел предназначен для пользователей, начинающих осваивать программирование и служит ознакомительным аспектом с областью олимпиадного программирования. Если Вы пока не знаете что из себя представляют олимпиадные задачи, как они представлены и какие критерии оценки для проверки решения существуют, то этот раздел именно для Вас.
В отличии от обычных программ, создаваемых программистами повседневно, класс олимпиадных задач достаточно узок, но практичен с точки критериев выявления способности участников программировать за короткий срок. Как правило, олимпиадная задача представляет собой некоторую проблему, для решения которой требуется использовать свой IQ почти напределе, однако, сам текст программы может быть совсем незначительным и помещаться на одной странице.
Если человек не занимался программированием, то предположительно можно оценить его способности к этой области в случае ее изучения. Многие полагают, что способности программировать связаны с умением решать математические и комбинаторные задачи. Другими словами, если у Вас в школе твердая пятерка по алгебре, геометрии и иным математическим дисциплинам, а так же умеете хорошо играть в шашки и шахматы, то вполне вероятно, что будете неплохо программировать, если начнете этим заниматься. И наоборот, если в школе у Вас тройка по алгебре, как бы вы не старались, то вряд ли программирование - это то, чем Вам стоит заниматься. Так же следует отметить, что Ваши заслуги в области освоения гуманитарных предметов мало Вам помогут в освоении программирования, которое, как Вы уже поняли, относится к точным наукам.
Приведем условную классификацию олимпиадных задач:
- Арифметика - математические задачи, работа с большими числами (длинная арифметика), такие задачи, как правило, требуют знания формул, умение их применять, а код программ может быть небольшим
- Геометрия - геометрические задачи, здесь может быть описана какая либо ситуация взаимодействия тел на плоскости и в пространстве
- Динамическое программирование - задачи, направленные на выявление рекуррентных соотношений
- Сортировка и последовательности - работа с данными, представленными в виде массива
- Графы - задачи с графами (структурами данных, основаных на вершинах и ребрах)
- Рекурсия - задачи на поиск с рекурсивным перебором вариантов
Конечно же задачи могут сочетать в себе сразу несколько направлений и часто бывает сложно конкретную задачу отнести к тому или иному разделу.
Любая олимпиадная задача подразумевает входные и выходные данные. Т.е. в формулировке задания обязательным образом описан формат входных и выходных данных, а Ваша программа должна считать эти данные, обработать и вывести результат в установленном формате. Чаще всего чтение происходит из некоторого файла INPUT.TXT, а вывод в некоторый файл OUTPUT.TXT . Т.е. для решения олимпиадных задач нужно уметь работать с файлами: читать, создавать и писать в них, а вот знания графических функций вряд ли Вам пригодятся. Стоит заметить, что многие системы, например http://acm.timus.ru , используют консольный режим ввода-вывода и работа с файлами в них не приветствуется. Данный сайт позволяет сдавать задачи как с использованием вышеупомянутых файлов, так и без них. Вариант ввода-вывода Вы выбираете сами. Помимо условия задачи, правил ввода и вывода информации на каждую задачу накладываются ограничения на время выполнения и используемую Вашей программой оперативную память.
Приведем пример формулировки олимпиадной задачи по программированию (Задача №1 в текущей системе из раздела Архив задач):
A+B
(Время: 1 сек. Память: 16 Мб Сложность: 2%)Требуется сложить два целых числа А и В.
Входные данные
В единственной строке входного файла INPUT.TXT записано два натуральных числа через пробел, не превышающих 10 9 .
Выходные данные
В единственную строку выходного файла OUTPUT.TXT нужно вывести одно целое число - сумму чисел А и В.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 | 2 3 | 5 |
Эта классическая простая задача используется для ознакомления участников с системой автоматической проверки и соответствует всем критериям правильной постановки олимпиадной задачи. При решении этой задачи необходимо из входного файла input.txt (либо с клавиатуры), расположенного в текущей папке (где и Ваша программа) считать 2 целых числа и вывести их сумму в выходной файл output.txt (либо на экран). Ограничения по памяти в 16Мб и времени 1 сек. весьма условны, так как такая простая задача потребует минимальную память и выполнится за минимальный промежуток времени (операция сложения выполнится мгновенно, современные ЭВМ способны выполнять 10 8 таких операций в секунду). Каждая задача имеет пример входных и выходных данных (часто даже несколько примеров), это позволяет участникам более однозначно понять содержание задачи. В данном примере в разделе "Пример" отражен пример входных данных "2 3" и выходных "5", это означает, что 2+3=5.
В зависимости от правил соревнований или тестирующей системы могут использоваться те или иные языки программирования. Приведем наиболее часто используемые средства создания программ приведены в разделе "Дистрибутивы" , откуда их возможно скачать и установить на свой компьютер.
В мире предпочтение отдается языку С++, но в России по-прежнему классическим языком программирования остается Pascal, а именно, большинство олимпиадных задач в России решается на Delphi. Мы же рекомендуем осваивать язык С++, который со временем станет наиболее популярным и в нашей стране. Далее мы в основном будем использовать язык С++ для рассмотрения примеров решения задач. можно ознакомиться с различными средами разработки программ на С++ на примере решения задачи "А+В".
Теперь Вы можете ознакомившись с работой системы , сдать задачу "A+B" на этом сайте . Другие задачи можно найти в "Архиве задач" и в "Курсах" . Быстрый переход по номеру задачи возможен с главной страницы с помощью раздела "Поиск по сайту", если в поисковой строке ввести "#N" или "№N" (без кавычек), где N - номер задачи.
На четвёртом курсе наша провинциальная команда (Orel STU) пробилась на финал ACM ICPC. Это был, мягко говоря, феерический успех – ведь мы никогда не срывали звёзд с неба, да и отбор был посерьёзнее, чем нынче. К нашей неугомонной радости случилась революция в Египте, которая стала причиной переноса финала из Шарм-Эль-Шейха в город Орландо солнечных штатов Америки.
А там-то и случился тот короткий разговор. Как-то вечером в chill zone мы болтали с Мишей Левиным о танцевальном агрегате, как вдруг подошёл на тот момент мне неизвестный Серёжа Чернышёв и, опознав по футболке участника финала, спросил: «В Яндекс к нам хочешь?» А чего отказываться? =)
Всё получилось как-то удивительно просто. Перекинулись парой писем. Уладили какую-то бюрократию - анкетку заполнить, даты согласовать. У меня оказался один формальный начальник и сразу несколько реальных.
Схема летней стажировки меня устраивала абсолютно: я приезжаю в середине лета, меня обеспечивают едой и жильём, два с половиной месяца стажируюсь и в конце сентября еду обратно в город-птицу, дабы доучиться последний курс и защитить диплом.
Забавно, но первый «рабочий» день совпал с закрытием ШАДа и подведением итогов Яндекс.Алгоритма. Так что я бы приехал в Москву всё равно. =) Рабочий день мне понравился. До четырёх часов вечера я тусил с друзьями-олимпиадниками в Экстрополисе и поедал куриные шашлычки. Не выходя из здания получил бейджик с серьёзной надписью: «Департамент разработки».
Вообще надо отметить, что я серьёзно переживал. Когда, когда мне дадут первое задание? Хватит ли моих скудных олимпиадных знаний, чтобы с ним справиться? Два с половиной месяца – это совсем немного, поэтому я ожидал уж если не галопам-по-европам, то хотя бы в-темпе-вальса mode on.
Однако никто даже не чесался. Ну, наверное, мне так казалось. Лёша Мирзоян с переменным успехом успокаивал меня: «тю, ну ты чего? Первую неделю знакомься с начальством, ребятами, офисом. Не заморачивайся!» В общем, конец дня прошёл попеременно то в бильярде, то в музыкальной комнате. ;)
Самым большим удивлением оказался мой сосед по жилищу. Саша Прудаев, с которым мы пару лет обсуждали по аське олимпиадные задачи, перебрался из далёкой Тюмени в столицу. И вышел на работу на два дня раньше меня. Вот так новость, вот так встреча! Другим моим соседом оказался Даниил Бурдаков, весьма толковый парнишка, с которым мы сейчас часто пересекаемся в ШАДе. Поэтому компашка подобралась что надо. Мы жили в двух минутах ходьбы от Нагорной и, с учётом того, что кольцевая Парка Культуры была закрыта на ремонт, тратили на дорогу порядка сорока минут в одну сторону.
На следующий день в моих руках оказался ноутбук. С виндой. Уже здорово, ибо линуксами я не пользовался в жизни. Задание начальство подобрало с душой. Нужно было каким-то образом научиться сравнивать документы на похожесть, ввести определение похожести и делать это всё достаточно быстро – ну, в предположении, что у нас овер 10^9 документов.
Но давайте обо всём по порядку. Меня записали в практикантский проект Ябракадабра, где занимались новым поисковиком с нуля. На его основе можно уверенно изучать и демонстрировать архитектуру любого поисковика, объяснять принципы информационного поиска и прочая, и прочая.
В теории всё было не очень страшно. Страшно было на практике. На меня обвалилось столько ужасно незнакомых вещей, что даже гитом пользоваться не приходилось – вместе с ребятами я один-единственный раз выкачал репозиторий, а потом всё делал локально. Забегая вперёд, скажу, что в последний день летней стажировки отправил свой код на почту начальнику, а не что-то куда-то внедрил. Наверное, люди с опытом, читающие эти строки, катаются по полу от смеха, держась за животы.
Практически сразу я понял, что в промышленном программировании две беды: ООП и названия переменных. С горем пополам и божьей помощью декомпозировав задачу, я приступил к поиску решения. Ребята советовали разные статьи на практически неизвестном мне тогда английском про simhash и minhash. Но как должен поступить настоящий олимпиадник? Конечно же придумать что-то своё! (Не хватает только комикса со шваброй).
Читал статьи и думал я где-то неделю. Конечно же, не переставая знакомиться с окружением. Трудовые будни скрашивались няшным офисом, посиделками на кофепоинтах с Сашей Прудаевым и другими спортивными программистами. Дальше произошёл переломный момент, которым я горжусь до сих пор: я придумал решение. Это было в поезде метро, как сейчас помню. =) В дальнейшем практика показала, что оно оказалось уж точно не хуже аналогов, которые всё равно пришлось реализовывать для построения графиков и убеждения начальства.
В итоге, на своё первое ревью я «отправил» нечто, состоящее из 300+ строк кода. В свою защиту могу сказать, что эти 300+ строк полностью решали поставленную задачу. =)
Ребята бились в истерике. Артём Бабенко плакал кровавыми слезами и говорил, что больше пяти раз он не станет принимать мой код. Ещё один дико забавный момент был в том, что на распечатке (а ревью было именно таким – я распечатывал код, и мы шли его толпой читать) сверху указан путь вроде “…/cadabra/kpr/hash.cpp”. На соответствующий вопрос я соответствующе ответил, и Артём долго и регулярно мне потом со слезами на глазах вспоминал «Купринхэш». .
В дальнейшем мой код рос и ширился. Это было как-то глупо и странно, учитывая, что функциональность не менялась. Пять раз быстро исчерпались, и со мной существенную часть времени проводил другой начальник Егор Самосват. Несмотря на то, что я чувствовал себя идиотом и выглядел ничуть не умнее, происходящее мне нравилось. Фактически, я учился в одновременно комфортных и боевых условиях.
Приходило время летних петрозаводских сборов, куда я напросился поехать от Яндекса, дабы нести свет и добро (зачёркнуто) дабы рассказать о прелестях летней стажировки. Народ отреагировал не очень охотно, и тогда я вспомнил себя на младших курсах: настоящий олимпиадник будет заниматься олимпиадными задачами бесконечно. Что ж, господа, придёт и ваше время. ;)
Тем временем, мы переехали в другую квартиру, на Белорусской. Станция Парк Культуры всё ещё была закрыта, а к концу второго месяца стажировок у меня окончательно поехал режим. Полтора часа в день на дорогу тратить было просто лень, поэтому я проводил в офисе практически круглые сутки, ночуя в мягких переговорках, гамаках и на пуфах. Это было действительно здорово. Удавалось много времени проводить в музыкальной комнате – ночами напролёт я терзал синтезатор и гитары. Ночные прогулки по офису приводили в недоумение охранников, зато какая атмосфера!
А тем временем работа медленно подходила к концу. «Купринхэш» обрёл новое имя – FirstLetterHash, перерос из одного файла в десяток, у него появились новые возможности и братья, имеющие тот же интерфейс, собралась статистика по запросу “проблемы бытия”, и многое, многое другое.
Как мне кажется, по большому счёту я справился. Пусть и не так здорово, как могло бы быть, но справился. Дабы не терять контакты, меня пообещали взять где-то зимой на удалёнку.
А в родном университете вовсю шли дискуссии и баталии о темах дипломных работ. Договорившись заранее с ребятами из Яндекса, мне удалось убедить дипломного руководителя в бесконечном пафосе и практической применимости FirstLetterHash. Так что в некотором роде диплом у меня был в кармане – осталось налить воды в пояснительую записку, что оказалось вопросом пары недель.
1 февраля я снова «вышел» на работу. Вот тут-то мне понадобился и git, и putty, и многие другие ранее неведомые радости жизни. Задание снова оказалось классным. На этот раз по ключевым словам нужно было построить сниппет – небольшую склейку из кусочков исходного текста, которая бы одновременно содержала много ключевых слов и воспринималась человеком как выдержки из документа, а не нарезка фраз.
Динамическое программирование в помощь! Решение в этот раз оказалось практически на поверхности, вопрос был в ограничениях на время и память. Двухчасовой рабочий день оказался отвратительным форматом, поэтому обычно я выбирал в месяце одну неделю, во время которой плодотворно трудился, а в остальное время занимался своими делами.
По ощущениям я был предоставлен сам себе, и это сильно расслабляло. И, хотя я честно выполнил задачу, оттестировал и закоммитил, мне кажется, что я халявил. Где-то с апреля-мая, когда 90% работы оказалось выполнено, перестали поступать разумные задания, и здесь скорее логика была простая: с новой большой задачей я справиться не успею, а время ещё есть.
После успешной защиты диплома я поступил в магистратуру ВШЭ на программу, совмещённую с ШАДом Яндекса, то есть по сути пошёл учиться сразу в два места. Заботливая ВШЭ поселила будущих магистров в тихом уютном лесном посёлке под названием Дубки, за что спасибо ей большое. Практически сразу я пришёл к выводу, что пять часов на дорогу в сутки можно разменять на рабочий день на полставки и житьё недалеко от офиса.
Очень скоро подвернулась отличная возможность: на выезде ШАДа мой знакомый Паша Шишкин, золотой медалист ACM ICPC, объявил о том, что Яндекс.Картинки ищут разработчика. Ура, вот он, мой шанс!
Скоро состоялось собеседование, на котором я с превеликим трудом отвечал на вопросы теста под названием «pure evil c++ test 2», почему-то лишь со второй попытки верно решил несложную задачку по теорверу, но зато убил наповал скоростью написания алгоритмической задачки в промышленном стиле.
Правда позиции на полставки не было - лишь на полный рабочий день. Но, пожалуй, так даже лучше. В картинках я с 1 октября – как раз прошло ровно пять месяцев. И по внутренним ощущениям всё по-настоящему здорово.
Вот так вот, с одного короткого разговора начался путь олимпиадника в промышленное программирование. И я уверен, что это только начало. Так что, ребят, дерзайте, учитесь, тренируйтесь, - и всё непременно получится!
