Олимпиадные задачи по программированию

Подготовка к олимпиаде

Решением олимпиадной задачи является программа, написанная на одном из языков программирования. Самыми популярными языками являются: C++, C#, Java, Pascal. Возможно,вы скажете, что Pascal уже давно устарел. Однако не стоит его недооценивать! Опытные спортивные программисты способны писать на Pascal’е стандартные алгоритмы, которые уже есть в C++, быстрее, чем обычный человек прочтет условие задачи :) Кстати, из-за того, что участники выбирают язык программирования самостоятельно, есть риск, что они делают неоптимальный выбор. Во-первых, решения существуют не на всех языках, а во-вторых, решения, написанные на некоторых языках, могут работать менее эффективно,чем на других.Вернемся к обсуждению условия. Олимпиадные задачи очень формализованы: строгий формат ввода\вывода, иногда даже с точностью до пробелов и переводов строк; условия, как правило, имеют строгую однозначную трактовку. Вот уж где можно поучиться заказчикам в написании ТЗ! строгие ограничения по времени выполнения и используемой памяти. В реальной разработке вам скорее скажут что-то в стиле «хотим, чтобы работало на таком-то железе и на такой-то ОС» или «слушай, твоя программа ест слишком много памяти». Куда реже можно услышать фразы типа «твоя программа должна работать не более 1,5 секунд» или «не смей использовать более 64 мегабайт памяти»; все исходные величины строго ограничены.Не забыть дописать смешной заголовок. Такая строгая формализация является оправданной. Все решения участников соревнований проверяются на некотором наборе тестов, который готовится жюри олимпиады и обычно заранее не известен участникам.Следующая особенность заключается в анализе задач. Автор олимпиадной задачи думает о том, сколько процентов участников решит такую задачу, за какое время (с точностью до минут), к какой тематике относится данная задача (например, задача на графы или задача на жадный алгоритм).

Вообще существует два типа олимпиадных задач: «классические» и «эвристические». Классические задачи предполагают наличие точного строго доказанного решения. При решении эвристических задач участники соревнуются между собой, кто сможет получить лучшие ответы. Например, чье решение правильно распознает большее количество символов. Эвристические задачи обычно не имеют точных решений. Здесь они более всего близки к реальной разработке. Например, распознавание символов – вполне себе «эвристическая» задача.
Существует немало способов оценки решений для «классических» задач: задача считается решенной, если решение участника правильно сработало на всех тестах. Такая система оценки используется на ACM-соревнованиях. За решение начисляются баллы, которые зависят от количества тестов, успешно пройденных программой. Такой подход часто используется на школьных олимпиадах: никто не уйдет обиженным с соревнования и получит хотя бы свои 0,5 балла. Тесты объединены в группы, за каждую из которых начисляется определенное количество баллов. Нужно заметить, что баллы за группу начисляются, только если решение правильно сработало на всех тестах из группы. Это разумный компромисс между справедливостью и удовлетворением участников. Иногда число баллов, полученных участником, зависит от времени, которое было затрачено на решение задачи.
Оценки решений «эвристических» задач в каждом случае разрабатывается индивидуально. К примеру: в эвристической задаче, которую предлагалось решить финалистам, нужно было разработать программу для классификации документов по тематикам. Решение проверялось на группе тестов, каждая из которых содержала некоторый набор текстов на разные темы. Всего было три тематики, и каждая из них была представлена в каждой группе в разном количестве. Выигрывал тот, чье решение прошло наибольшее количество групп тестов. При установке «эвристической» задачи на тестирующую платформу иногда приходиться ее дорабатывать, поскольку большинство тестирующих платформ «заточено» на оценку классических задач.

Примеры задач:

Задача 1. Спички (Школьная олимпиада по программированию младшая лига.)

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

Формат входных данных

На вход программа получает количество квадратов N, не превосходящее 109.

Формат выходных данных

Программа должна вывести единственное число – необходимое количество спичек.

Пример

Вход 4

Выход 12

Задача 2. Муха.

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

Формат входных данных.

Первые три строки входных данных содержат положительные числа K, L, M, являющиеся размерами параллелепипеда вдоль осей OX, OY, OZ. Один угол параллелепипеда находится в начале координат, противоположный – в точке (K;L;M), ребра параллелепипеда параллельны осям координат.

Следующие три строки входных данных содержат координаты мухи X1, Y1, Z1, затем идут три строки с координатами варенья X2, Y2, Z2. Задаваемые этими координатами точки находятся на поверхности параллелепипеда. Все числа во входных данных целые, не превосходящие 1000.

Формат выходных данных

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