#601

Забор

Темы: [Формула]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Окружная олимпиада, 2007, 2 тур, Задача A ]

Том Сойер получил важное задание по покраске забора. Забор состоит из n досок. Он когда-то был покрашен, однако с некоторых участков забора краска облупилась. Эти доски Тому и необходимо покрасить. Так как забор большой, пришлось подвезти к забору целую цистерну с краской. Цистерна была помещена у края забора и не может перемещаться. У Тома есть ведерко, набрав краски в которое, Том может покрасить \(k\) досок забора. При этом Том может в любой момент вернуться за краской к цистерне.

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

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

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

Первая строка входного файла содержит количество досок в заборе \(n\) (1 ≤ \(n\) ≤ \(10^9\)) и вместимость ведерка \(k\) (1 ≤ \(k\) ≤ 100). Во второй строке содержится количество неокрашенных отрезков забора \(m\) (1 ≤ \(m\) ≤ 50). Далее следуют \(m\) строк, в каждой из которых описан один неокрашенный отрезок. Отрезок описывается своей левой границей \(l_i\) и правой границей \(r_i\) (1 ≤ \(l_i\) ≤ \(r_i\) ≤ \(n\)). Такое описание означает, что не покрашены \(l_i\)-я, (\(l_i\)+1)-я, …, (\(r_i\)–1)-я, \(r_i\)-я доски забора (доски нумеруются от 1 до \(n\)). Гарантируется, что неокрашенные отрезки, заданные во входном файле, не пересекаются.

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

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

Примеры

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

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

#602

Окопы и траншеи

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Окружная олимпиада, 2007, 2 тур, Задача B ]

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

Очередные учения должны продемонстрировать способность солдат быстро и незаметно перемещаться из точки A в точку B.

Во время учений солдаты могут перемещаться либо по окопам, либо по траншеям, которые они могут прокапывать между окопами. При этом по окопам и выкопанным траншеям солдат может бегать настолько быстро, что временем перемещения от одной точки до другой можно пренебречь (будем считать его равным нулю). Траншеи же солдат копает со скоростью 1 метр в час.

Заданы точки A и B. Требуется определить, за какое минимальное время солдат во время учений сможет переместиться из А в B. Шириной траншей и окопов можно пренебречь.

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

Первая строка входного файла содержит число n — количество окопов на полигоне (1 ≤ n ≤ 500). Введем систему координат на полигоне таким образом, чтобы ось OX была ориентирована с запада на восток, а ось OY — с юга на север. Следующие n строк описывают окопы, каждый окоп описывается четырьмя целыми числами x₁, y₁, x₂, y₂ — координатами юго-западного и северо-восточного углов, соответственно (–10⁴ ≤ x₁ < x₂ ≤ 10⁴, –10⁴ ≤ y₁ < y₂ ≤ 10⁴).

Последние две строки содержат по два целых числа: x_A, y_A — координаты точки A и x_B, y_B — координаты точки B, соответственно (–10⁴ ≤ x_A, y_A, x_B, y_B ≤ 10⁴). Гарантируется, что точки A и B находятся в окопах. Все координаты заданы в метрах.

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

Выведите в выходной файл одно вещественное число — количество часов, которое потребуется солдату, чтобы добраться из точки A до точки B. Ответ должен отличаться от правильного не более чем на 10^–6.

Примеры

Входные данные	Выходные данные	рисунок
3 0 4 10 11 3 7 7 9 3 0 7 2 4 9 5 0	4
2 0 0 3 3 6 6 9 9 1 3 7 9	4.24264068711928515
2 0 0 6 6 3 3 9 9 1 6 7 9	0

#603

Планировка кухни

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Окружная олимпиада, 2007, 2 тур, Задача C ]

Крупная межгалактическая сеть мебельных магазинов Galactic-Мебель недавно вышла на рынок мебели для кухонь в звездной системе LoST-2007. В этой звездной системе во всех квартирах кухни имеют форму прямоугольника размером a на b метров. При этом вдоль одной из стен принято ставить стол, в смежной с ней стене находится окно. Таким образом, для размещения различных кухонных шкафчиков остается угол со сторонами a и b метров.

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

В звездной системе LoST-2007 используется n типов кухонных шкафчиков. Каждый тип шкафчиков характеризуется своей шириной wi, при этом на кухне должен присутствовать ровно один экземпляр каждого типа шкафчиков.

Недавно директор маркетингового отдела Galactic-Мебель заметил, что он может предложить клиентам несколько вариантов расположения шкафчиков на кухне. Различными считаются варианты, которые отличаются расположением хотя бы одного шкафчика. При этом шкафчики различных типов могут иметь одинаковую ширину, однако отличаются внешней отделкой. Так что даже размещения, которые отличаются лишь позициями шкафчиков с равной шириной, считаются различными. Например, пусть a = 3, b = 4 и есть два типа шкафчиков, шириной 1 и 2, соответственно.

Тогда возможно шесть планировок кухни. Возможные планировки показаны на рисунке.

Требуется по заданным размерам кухни и шкафчиков найти число различных планировок.

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

Первая строка входного файла содержит три целых числа: \(a\), \(b\) и \(n\) (1 ≤ \(a\) ≤ 300, 1 ≤ \(b\) ≤ 300, 1 ≤ \(n\) ≤ 100). Каждая из следующих \(n\) строк содержит целое число \(w_i\) (1 ≤ \(w_i\) ≤ 300) — ширину соответствующего шкафчика.

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

Выведите в выходной файл количество различных планировок кухни.

Примеры

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

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

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

1 6 2
3
2

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

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

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

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

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