Формат выходного файла: Необходимо вывести одно целое число – количество фигурок, которые придется распилить при укладке рисунка.

Пример:

Задача В: Словарь

Ограничение по времени: 1 секунда

Ограничение по памяти: 16 Мб

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

Переводчик в своем походном марсианско-русском словаре обозначает первую букву марсианского алфавита за « A », вторую за « B » и так далее (N не превосходит 20). Разумеется, слова в словаре упорядочены по алфавиту. И когда он встречает в какой-нибудь марсианской книге редко используемое слово, ему приходится долго листать словарь в поисках перевода. Помогите переводчику по марсианскому слову определить его порядковый номер в словаре.

Формат входного файла: В первой строке файла записано натуральное число N , не превосходящее 20, - длина слова. Следующая строка содержит марсианское слово для перевода. Слово состоит из заглавных латинских букв.

Формат выходного файла: Необходимо вывести одно целое число – порядковый номер этого слова в марсианско-русском словаре.

Примеры:

Задача C: Школа

Ограничение по времени: 1 секунда

Ограничение по памяти: 64 Мб

В школе некоторые из ребят хотели бы перейти из своего класса в другой, параллельный. Однако сделать это можно только в том случае, если кто-то из учеников этого класса также решит сменить класс – и освободит, таким образом, место. Скажем, ученик «10А» Антон сможет перейти в «10Г», если, например, Вера из «10Г» захочет перейти в «10Б», а Лена из «10Б» – в «10А».

Вам известны предпочтения ребят (ровно одно для каждого ученика). Необходимо определить длину максимальной цепи переходов учеников из класса в класс. Например, в разобранном выше случае длина цепи переходов составляет 3.

Формат входного файла: В первой строке входного файла задано количество N учеников, желающих перейти в другой класс. Каждая из следующих N строк состоит из имени ученика, буквы класса (отделенной от имени одним пробелом), в котором он учится, и отличной от нее буквы класса (также отделенной одним пробелом), куда хочет перейти. Используются только латинские буквы. Буквы класса – прописные. Длина имени ученика не превосходит 20.

Формат выходного файла: Одно целое число – длина максимальной цепи переходов.

Пример:

Демонстрации:

• 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

Требуется сложить два целых числа А и В.

Входные данные

В единственной строке входного файла INPUT.TXT записано два натуральных числа через пробел, не превышающих 10 9 .

Выходные данные

В единственную строку выходного файла OUTPUT.TXT нужно вывести одно целое число - сумму чисел А и В.

Пример

Эта классическая простая задача используется для ознакомления участников с системой автоматической проверки и соответствует всем критериям правильной постановки олимпиадной задачи. При решении этой задачи необходимо из входного файла input.txt (либо с клавиатуры), расположенного в текущей папке (где и Ваша программа) считать 2 целых числа и вывести их сумму в выходной файл output.txt (либо на экран). Ограничения по памяти в 16Мб и времени 1 сек. весьма условны, так как такая простая задача потребует минимальную память и выполнится за минимальный промежуток времени (операция сложения выполнится мгновенно, современные ЭВМ способны выполнять 10 8 таких операций в секунду). Каждая задача имеет пример входных и выходных данных (часто даже несколько примеров), это позволяет участникам более однозначно понять содержание задачи. В данном примере в разделе "Пример" отражен пример входных данных "2 3" и выходных "5", это означает, что 2+3=5.

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

В мире предпочтение отдается языку С++, но в России по-прежнему классическим языком программирования остается Pascal, а именно, большинство олимпиадных задач в России решается на Delphi. Мы же рекомендуем осваивать язык С++, который со временем станет наиболее популярным и в нашей стране. Далее мы в основном будем использовать язык С++ для рассмотрения примеров решения задач. можно ознакомиться с различными средами разработки программ на С++ на примере решения задачи "А+В".

Теперь Вы можете ознакомившись с работой системы , сдать задачу "A+B" на этом сайте . Другие задачи можно найти в "Архиве задач" и в "Курсах" . Быстрый переход по номеру задачи возможен с главной страницы с помощью раздела "Поиск по сайту", если в поисковой строке ввести "#N" или "№N" (без кавычек), где N - номер задачи.

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

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

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

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

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

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

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

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

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

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

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

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

Об обучении

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

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

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

Меня всегда привлекало программирование (что это такое я понял аж в 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 и информатику, мечта моя - выучиться на физика-теоретика и заниматься исследованиями. А так как в РФ с этим проблемы я планирую уехать в Канаду или США.

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