Этот раздел предназначен для пользователей, начинающих осваивать программирование и служит ознакомительным аспектом с областью олимпиадного программирования. Если Вы пока не знаете что из себя представляют олимпиадные задачи, как они представлены и какие критерии оценки для проверки решения существуют, то этот раздел именно для Вас.

В отличии от обычных программ, создаваемых программистами повседневно, класс олимпиадных задач достаточно узок, но практичен с точки критериев выявления способности участников программировать за короткий срок. Как правило, олимпиадная задача представляет собой некоторую проблему, для решения которой требуется использовать свой 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 - номер задачи.

В России олимпиадным программированием занимаются уже достаточно давно. Школьные олимпиады проводятся с конца 80-х, студенческие с середины 90-х годов XX века. Так что это такое олимпиады по программированию нужны ли они или нет и если да то кому?

Давайте разберемся, что такое олимпиада по программированию?

Как устроена олимпиада?

Студенческая олимпиада организованна следующим образом:

Трое участников команды сидят перед одним компьютером. Им дается набор задач, которые они должны решить. Что значит решить задачу? Это значит написать программу, которая пройдет заранее заготовленный жюри набор тестов. Таким образом, задача решена, если она прошла весь набор, то есть полностью правильна с точки зрения жюри. Для любой программы есть ограничения по ресурсам, она не должна требовать слишком много памяти и работать слишком долго. Продолжительность олимпиады обычно 5 часов. Команды соревнуются между собой. Это значит, что в турнирной таблице выше находится та команда, которая решила больше задач. А из тех, которые решили одинаковое количество задач та, которая это сделала быстрее.

Школьные олимпиады обычно имеют свою особенность:

Чаще всего они не командные, а личные, и ребята не должны на 100% решить задачу, а могут решить только часть задачи и получить за это соответствующие баллы.

Какие задачи дают на олимпиадах?

Обычно это задачи из области программирования, информатики (Computer Science), различных разделов математики. Очень популярны задачи по поиску и обработке текста, задачи по криптографии, геолокации, теории игр, методов оптимизации, оптимального хранения и обработки данных, быстрого доступа к данным и другие.

На самом деле, каждый из нас встречается с решениями олимпиадных задач очень часто. Рассмотрим несколько примеров:

Поиск Маршрутов. Многие из нас пользуются различными приложениями по поиску маршрутов: 2GIS, Яндекс Карты, Google Maps и другие. Эти приложения подбирают для нас кратчайший маршрут с учетом разных факторов: транспорт, пробки, направление движения на дорогах, наличие пешеходного перехода и другие. Так вот, построить такой маршрут - это одна из классических олимпиадных задач: найти кратчайший путь в графе. Для этой ззадачи существуют различные подходы и алгоритмы. В частности, в создании сервиса Яндекс. Пробки активно принимали участие олимпиадники.

Другой пример: поиск сроки в тексте, вы часто пользуетесь поиском? Так вот поиск - тоже олимпиадная задача.

Третий пример уже более специализированный: во многих организациях возникает поток заказов, задач или заданий Есть несколько исполнителей, каждый может выполнять какие-то заказы, но стоимость выполнения разная. Как быстро и с минимальными затратами выполнить все заказы?

Какие навыки развиваются у олимпиадника?

Во-первых, ребята учатся решать не тривиальные задачи, часто из разных областей математики и программирования. Это позволяет с одной стороны иметь большой математический кругозор, с другой стороны видеть, что эти абстрактные математические задачи имеют привязку к жизни. Во вторых, оценивать свои решения в зависимости от имеющихся ресурсов (обычно это время и память, которые используют программы). Вряд ли кому-то нужна программа, которая работает сотни лет или требует все имеющиеся жесткие диски в мире. В-третьих, работать качественно и в короткие сроки, в олимпиадах время ограничено и принимается решение только 100% верное. В-четвертых, работать в команде: у участников есть только один компьютер, поэтому они вынуждены обсуждать, распределять роли в команде, писать код по очереди, помогать сокоманднику, если у него что-то пошло не так. В-пятых, ребята учатся искать потенциальные проблемы своих решений, готовить контрольные примеры, тестировать свои решения. В-шестых, это соревнование - ребята учатся какого это обходить других и когда обходят тебя, как взаимодействовать с другими и видят насколько много людей участвуют в этом движении.

Кому это все нужно?

Это нужно науке.

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

Отличие олимпиад от классической науки в том, что олимпиадники обычно решают задачи в короткие сроки, а ученые проводят за исследованиями много дней, и только тогда находят решения. Однако, олимпиадники также проводят много времен, раздумывая над задачами не во время самой олимпиады, а при подготовке. При этом на самой олимпиаде чаще всего применятся уже наработанные знания и навыки, всплывающие из глубин памяти и интеллекта. Те, которые были выработаны в процессе долгих размышлений.

Есть много примеров, когда олимпиадники становятся учеными: многие олимпиадники КФУ защитили свои кандидатские или сейчас в процессе, в Москве и Петербурга вы можете встретить ученых, которые в своем прошлом участвовали в олимпиадах. Известные ученые в области квантовой информатики - победители олимпиад.

Это нужно промышленности.

Навыки создания оптимальных, надежных программ в короткие сроки, работы в команде, умение решать нетривиальные задачи - это то, что требуется любой IT-компании.

Многие компании, такие как Facebook, Google, Яндекс, Mail.ru, VK, Huaweii и друге организовывают собственные олимпиады и приглашают к себе сотрудников по их результатам. Многие компании принимают олимпиадников без собеседования или на льготных условиях. Третьи компании, к примеру Google, и другие проводят собеседование на олимпиадных задачах.

Потому что они понимают, что люди, которые могу решить сложную задачу, написать эффективный код и работать в команде - это те кто смогут обеспечить им обработку не 100 тысяч пользователей, а миллиона или 100 миллионов с той же скоростью, это те кто потом помогут написать распознавание лиц в их программах или построение оптимального маршрута. Это те, кто для компаний помогут заработать новые деньги, а пользователи из-за них будут считать, что внутри программ скрыта “магия”.

Да и просто люди, которые в студенческие годы написали сотни тысяч программ на много лучше будут работать, чем те, которые писали 100-200 программ в рамках своих домашних заданий в университете.

Небольшая социально-культурная составляющая.
Олимпиады позволяют познакомиться ребятам с будущей элитой IT-сообщества, попутешествовать по разным городам, Принять участие в соревнованиях, померяться силами с лучшими программистами мира.

В заключении.

Некоторые люди ругают олимпиады, другие их восхваляют. Нельзя сказать что олимпиады - полная замена каким-то предметам в университете, как некоторые пытаются это представить, но олимпиады это очень хорошее подспорье для будущих ученых, программистов, аналитиков.

Это интеллектуальный спорт, в котором спортсмены после окончания своей карьеры могут приносить реальную пользу обществу. Скажите, много ли видов спорта могут похвастаться этим? Это тот спорт, в котором участвуют большинство ведущих университетов мира. Победители в котором, известны IT и научному сообществу.

P.S. Кстати, это вид спорта в котором Россияне уже 5 лет подряд становятся чемпионами мира! А этим сколько видов спорта могут похвастаться?

Яндекс достаточно давно интересуется олимпиадными программистами. Будучи второкурсником, я слушал рассказы про ШАД Григория Кондакова, выступления Миши Левина. Получал футболки и брошюры на четвертьфиналах и полуфиналах чемпионата мира. Но, знаете, в то далёкое исключительно олимпиадное время совсем не волновали вопросы работы, а уж тем более дополнительного обучения. Ну, до поры, до времени.

На четвёртом курсе наша провинциальная команда (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 октября – как раз прошло ровно пять месяцев. И по внутренним ощущениям всё по-настоящему здорово.

Вот так вот, с одного короткого разговора начался путь олимпиадника в промышленное программирование. И я уверен, что это только начало. Так что, ребят, дерзайте, учитесь, тренируйтесь, - и всё непременно получится!

Здравствуй!
Пишет тебе девятиклассник, призер регионального этапа всероссийской олимпиады по информатике. В последнее время я стал замечать, что у читателей повысился интерес к олимпиадам по программированию. Как их активный участник я постараюсь ответить на все вопросы, рассказать о своем пути, привести примеры реальных, запомнившихся мне задач.

Об обучении

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

Что же это за школа, как в ней учиться и как в нее поступить?

Отбор проходит в два этапа. Первый - экзамен по физике и математике. После него некоторые счастливчики попадают на собеседование, где от них требуется решить несколько олимпиадных задач по математике. И только после этого самые умные и удачливые становятся учениками.
Учиться очень тяжело и сложно. Учителя требуют идеального знания чуть ли не всех предметов. На родительском собрании сказали: «В начале обучения абсолютно все ученики скатываются до двоек, даже отличники. Те, кто начинают реально учиться - получают хорошие оценки. Остальные отсеиваются». У меня больше всего было проблем с русским языком и литературой, как бы это ни было странно.

Меня всегда привлекало программирование (что это такое я понял аж в 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 место среди девятиклассников.

Региональный этап

На этапе региональном было не так весело, тура было два. Я боялся подвести школу и не пройти на следующий этап, плохо показать нашу школу. Поэтому и задания воспринимались не так весело и приятно. В общем: ничего не запомнил оттуда, но получил заветный диплом. Да и условия мне не удалось найти.
На второй день к нам приехали представители местной компании «Прогноз», поиграли с нами в «Что? Где? Когда?», провели викторину. Победителям раздали призы.

Подготовка

Как же я готовился?
Ответ достаточно прост: у меня хорошие учителя. Мне это было интересно и я получал от всего происходящего удовольствие. Я усердно готовился и добился того, чего хотел.

Что делать, если Вам это тоже интересно и Вы хотите принять во всем этом участие?

1. Существуют системы подготовки школьников к олимпиадам по программированию, на них есть тестовая система и куча условий с решениями. Насколько я понимаю, на всех таких системах нужна регистрация. Я готовился при помощи двух:
   • acmp.ru/ Есть достаточно много задач разной сложности, так же интересен раздел «Курс олимпиадника»
   • http://acm.timus.ru/ Куча задач с самых разных олимпиад, некоторые на английском. В разделе http://acm.timus.ru/offline у нас проводился дистанционный и региональный этапы.
2. Существуют онлайн олимпиады, я участвовал лишь в одной: NetOI от украинцев. Отзыв такой: ХАРДКОР!!! Дальше второго тура не прошел. Код нужно писать ужасно оптимально (я так не умею), для каждого теста индивидуальные условия (удвоенное время программы жюри).

Что же дальше?

Говоря это, я подразумеваю вопрос о том, насколько олимпиадники приспособлены к работе в реальных условиях.
Хоть я и не работал еще в IT индустрии, но я считаю: олимпиадники никак не приспособлены к реальной работе. На таких олимпиадах требуется уметь быстро изобрести «велосипед», знать хорошо алгоритмы. Я с другом занимаюсь написанием небольших игр и понимаю, что гораздо важнее уметь выбрать правильную технологию для твоих целей, уметь найти готовое решение чтобы ускорить разработку, «Велосипеды не нужны». Поправьте меня, если это не так.
Если кого интересует то, чего я в жизни хочу: на самом деле я не очень-то люблю IT и информатику, мечта моя - выучиться на физика-теоретика и заниматься исследованиями. А так как в РФ с этим проблемы я планирую уехать в Канаду или США.

Приму любые пожелания в ЛС или в комментариях. Надеюсь, данная статья не получилась длинной. Надеюсь она была для Вас интересна. Надеюсь Вас не раздражала моя неграмотность, уж очень я плохо знаю пунктуацию.

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

А. и Б. Стругацкие.

«В наше время считается общепризнанным,
что из всего, так или иначе касающегося искусства,
ничто более не может считаться общепризнаным»
Теодор Адорно

Все началось с того, как один человек пытался выяснить решение задачи контеста, который проходил в данный момент. Задача была очень простая, всем было очевидно, что этот человек не займет хорошего места, не получит футболку и т.п. Но тем не менее ни один из 5000+ членов сообщества не дал ни одной подсказки (ну или хотя бы из 30+ человек, которые это видели и знали ответ). Мне такой результат уже давно кажется закономерным и я попробовал объяснить его в двух словах. Теперь попробую чуть более подробно. Заранее прошу прощения у людей, которые в это понятие вкладывают не то, что я. Я лишь хотел изложить свой взгляд.

Сначала немного теории из википедии: Программирование , Олимпиады по программированию , Искусство . Обратите внимание, в последней статье указано "Понятие искусства крайне широко - оно может проявляться как чрезвычайно развитое мастерство в какой-то определённой области".

Мне всегда казалось, что программирование, это своего рода искусство. Вот есть узкая область - класс олимпиадных задач по программированию. Умение быстро и точно решать задачи схоже со спортом, и часто олимпиадное программирование называют спортивным, ведь здесь, как и в спорте, сначала несколько лет тренируешься, потом один раз выступаешь, сливаешь все нафиг и забиваешь на программирование достигаешь некоторых результатов и радуешься им. Но с другой стороны спорт - не сильно творческое занятие. Обычно стратегии составляются не главными участниками и они не блещут оригинальностью и красотой. А в программировании все не так.

Никто не будет спорить, что стихи - искусство. А ведь, что такое стихи? Стихи - это умение вкладывать свои мысли в четкие рамки ритма и рифмы, стиля и словарного набора. Есть множество ограничений, которые не дают просто излагать то, что ты хочешь. Зачем же они? Это добавляет стиху красоты и изящества, это показывает, что автор вложил усилия, чтобы выразить свои мысли таким образом, соответственно, эти мысли были тщательно обдуманы автором, обточены и получили материальную форму в виде стиха. Кроме того, язык мыслей сильно отличается практически от всех языков мира, будь это язык слов, язык изображений, язык звуков или язык архитектуры.

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

Вот вы видите доску в городском доме творчества. На доске сверху ровными буквами написано "Выставка детских рисунков", а под надписью уже не столь ровно изображены различные эпизоды из детского быта. Попробуйте ответить - это искусство? Мой ответ - да, безусловно. Эти дети нашли свой способ общаться с миром, показывать ему свои мысли. Пусть они весьма примитивны и грубо изображены (хотя, бывает по-разному, некоторые дети способны на шедевры, которые и не снились взрослым художникам), но это искусство. Возможно, когда нибудь, один из этих детей будет писать легендарные картины, и люди со всего света будут приезжать, чтобы посмотреть на них. Все начинается с малого.

Я бы хотел, чтобы подобные общества были своего рода клубами искусства программирования(как, например, будетляне), в которых люди общаются, делятся секретами, творят вместе, помогают новичкам, но никогда не будут выдавать чужие мысли за свои.

Буду поддерживать список неплохих комментариев и дополнений.