Олимпиадные задачи по программированию: что за зверь?
Недавно мы анонсировали конкурс задач по спортивному программированию. Организаторы конкурса попросили написать короткое объявление о конкурсе в блог, но строгий редактор отказался печатать анонс без объяснения того, что же такое олимпиадная задача. Из этого родилась целая статья. Начнем, пожалуй, с примера олимпиадной задачи. Этот же пример, чтобы по ссылке не ходитьИТ-рестораныограничение по времени на тест: 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
1 2
2 3
3 4
4 5Выходные данные
3
1 3
2 2
3 1Входные данные
10
1 2
2 3
3 4
5 6
6 7
7 4
8 9
9 10
10 4Выходные данные
6
1 8
2 7
3 6
6 3
7 2
8 1
Первое, что бросается в глаза, это необычное условие. Такой подход сложился исторически: писать краткую математическую формулировку не принято. Обычно ее пытаются связать с реальной жизнью, ну или с не очень реальной. Например, в USACO героями всех задач являются фермер Джон и коровы. Прежде чем приступить к решению после прочтения условия, участнику требуется выделить математическую формулировку задачи. Читать дальше →
