Решение Олимпиадных Задач по Программированию

Недавно мы анонсировали конкурс задач по спортивному программированию. Организаторы конкурса попросили написать короткое объявление о конкурсе в блог ABBYY, но строгий редактор отказался печатать анонс без объяснения того, что же такое олимпиадная задача. Из этого родилась целая статья. Начнем, пожалуй, с примера олимпиадной задачи.
Этот же пример, чтобы по ссылке не ходить

ИТ-рестораны

ограничение по времени на тест: 4 секунды
ограничение по памяти на тест: 256 мегабайт
ввод: standard input
вывод: standard output

В городе N. очень плохо с дорогами, общепитом и IT-инфраструктурой. Всего в городе n перекрестков, некоторые пары которых соединены двусторонними дорогами. Дорожная сеть состоит из n - 1 дороги, по дорогам можно добраться с любого перекрестка на любой другой. Да, вы правы — дорожная сеть образует неориентированное дерево.

Недавно мэр города придумал способ, устраняющий проблемы с общепитом и IT-инфраструктурой, причем одновременно! Решено поставить на перекрестках города ресторанчики двух известных сетей кафе для IT-шников: «iMac D0naldz» и «Burger Bing». Так как владельцы сетей не дружат, категорически запрещается размещать рестораны двух разных сетей на соседних перекрестках. Есть и другие требования. Вот полный список:

• в каждом перекрестке должен находится не более чем один ресторан;
• каждый ресторан принадлежит либо «iMac D0naldz», либо «Burger Bing»;
• каждая сеть должна построить не менее одного ресторана;
• не существует пары перекрестков, которые соединены дорогой и на которых стоят рестораны разных сетей.

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

Помогите мэру проанализировать ситуацию. Найдите все такие пары (a,  b), что a ресторанов может принадлежать «iMac D0naldz», b — «Burger Bing», а сумма a + b максимальна.

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

В первой строке входных данных содержится целое число n (3 ≤ n ≤ 5000) — количество перекрестков в городе. Далее в n - 1 строке перечислены все дороги, по одной дороге в строке. Каждая дорога задана парой чисел xi,  yi (1 ≤ xi,  yi ≤ n) — номерами соединяемых перекрестков. Считайте, что перекрестки пронумерованы от 1 до n.

Гарантируется, что заданная дорожная сеть представляет собой неориентированное дерево с n вершинами.

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

В первую строку выведите целое число z — количество искомых пар. Далее выведите все искомые пары (a,  b) в порядке увеличения первой компоненты a.
Примеры тестовВходные данные

5 4 5

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

3 3 1

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

6 8 1

Первое, что бросается в глаза, это необычное условие. Такой подход сложился исторически: писать краткую математическую формулировку не принято. Обычно ее пытаются связать с реальной жизнью, ну или с не очень реальной. Например, в USACO героями всех задач являются фермер Джон и коровы. Прежде чем приступить к решению после прочтения условия, участнику требуется выделить математическую формулировку задачи.
Решением олимпиадной задачи является программа, написанная на одном из языков программирования. Самыми популярными языками являются: C++, C#, Java, Pascal. Возможно, вы скажете, что Pascal уже давно устарел. Однако не стоит его недооценивать! Опытные спортивные программисты способны писать на Pascal’е стандартные алгоритмы, которые уже есть в C++, быстрее, чем обычный человек прочтет условие задачи :) Кстати, из-за того, что участники выбирают язык программирования самостоятельно, есть риск, что они делают неоптимальный выбор. Во-первых, решения существуют не на всех языках, а во-вторых, решения, написанные на некоторых языках, могут работать менее эффективно, чем на других.

Вернемся к обсуждению условия. Олимпиадные задачи очень формализованы:

• строгий формат ввода\вывода, иногда даже с точностью до пробелов и переводов строк;
• условия, как правило, имеют строгую однозначную трактовку. Вот уж где можно поучиться заказчикам в написании ТЗ!
• строгие ограничения по времени выполнения и используемой памяти. В реальной разработке вам скорее скажут что-то в стиле «хотим, чтобы работало на таком-то железе и на такой-то ОС» или «слушай, твоя программа ест слишком много памяти». Куда реже можно услышать фразы типа «твоя программа должна работать не более 1, 5 секунд» или «не смей использовать более 64 мегабайт памяти»;
• все исходные величины строго ограничены.

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

Следующая особенность заключается в анализе задач. Автор олимпиадной задачи думает о том, сколько процентов участников решит такую задачу, за какое время (с точностью до минут), к какой тематике относится данная задача (например, задача на графы или задача на жадный алгоритм).

• Решение Задач по Программированию
• Олимпиадные Задачи по Программированию
• Решение Задачи Линейного Программирования