Задача A. Космос для школьников ≡

Условие

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

Учитель астрономии решил поддержать юных исследователей и выдал друзьям список существующих спутников, которые будут пролетать над городом, где живут Игорь с Олегом, в день предполагаемого запуска их спутника. Для каждого из N спутников в списке указан момент его пролёта над городом с точностью до минуты.

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

Формат входного файла

В первой строке входного файла содержится число N. Далее следуют N строк вида HH:MM, где HH — часы, MM — минуты.

Формат выходного файла

Выходной файл должен содержать последовательность строк вида HH:MM - HH:MM или HH:MM — интервалы времени, в течение которых над городом нет спутников. Интервалы должны быть расположены в хронологическом порядке.

Ограничения

1 ≤ N ≤ 1440

0 ≤ H ≤ 23

0 ≤ M ≤ 59

Примеры тестов

2
10:10
10:12

00:00 - 10:09
10:11
10:13 - 23:59

4
10:11
10:12
10:10
10:13

00:00 - 10:09
10:14 - 23:59

Задача B. Любители SMS ≡

Условие

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

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

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

Расположение клавиш и координаты их центров показаны на приведённой схеме:

  1 2 3   (1; 1) (1; 2) (1; 3)
  4 5 6   (2; 1) (2; 2) (2; 3)
  7 8 9   (3; 1) (3; 2) (3; 3)
    0            (4; 2)
  

Одному члену жюри требуется набрать сообщение, состоящее из N символов. Помогите ему оценить минимальное время, которое для этого потребуется. Клавиша, которую нужно нажать, чтобы ввести i-й символ сообщения, задаётся изображённой на ней цифрой a_i. В начальный момент времени палец левой руки находится на клавише 4, а палец правой руки — на клавише 6.

Рекомендуется рассмотреть частичные решения

• Минимизация расстояния на каждом шаге ведёт к минимизации ответа (жадный алгоритм)
• 1 ≤ N ≤ 20

Формат входного файла

Входной файл содержит целое число N, за которым следуют N цифр a_i.

Формат выходного файла

Выходной файл должен содержать единственное вещественное число t — минимальное время набора сообщения. Абсолютная ошибка ответа не должна превышать 10⁻³.

Ограничения

1 ≤ N ≤ 10⁵, 0 ≤ a_i ≤ 9

Примеры тестов

4
1 3 2 7

5

6
5 2 9 0 0 3

6.650281540

Задача C. Плотные и целые ≡

Условие

Последовательность целых чисел b₁, b₂, …, b_K назовём плотной, если после сортировки по возрастанию она превратится в последовательность x, x + 1, …, x + K − 1 для некоторого целого x. Например, последовательности 1, 2 и 7, 6, 8, 5 являются плотными, а последовательности 1, 1, 2 и 1, 5, 2, 3 — нет.

Дана последовательность из N целых чисел a₁, …, a_N. Требуется определить такие два индекса 1 ≤ i ≤ j ≤ N, что:

1. подпоследовательность a_i, a_i + 1, …, a_j является плотной;
2. длина подпоследовательности j − i + 1 является максимально возможной;
3. индекс i — наименьший среди всех подпоследовательностей, удовлетворяющих предыдущим условиям;

Рекомендуется рассмотреть частичные решения

1. 1 ≤ N ≤ 500
2. 1 ≤ a_i ≤ 10⁶

Формат входного файла

Формат выходного файла

Выходной файл должен содержать два целых числа — индексы i и j.

Ограничения

Примеры тестов

2
3 3

1 1

10
1 1 2 2 5 3 4 6 2 4

4 8

Задача D. Макет города ≡

Условие

У Пети на столе стоит макет центральной части города. Макет представляет собой N зданий в форме прямоугольных параллелепипедов, расположенных на плоской поверхности. Здания могут вплотную соприкасаться стенками.

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

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

Рекомендуется рассмотреть частичные решения

1. N = 1.
2. Здания не соприкасаются стенками.
3. Все здания имеют одинаковую высоту.
4. N ≤ 1000.

Формат входного файла

Входной файл содержит целое число N — количество зданий.

Далее следуют N пятёрок целых чисел: x_i y_i u_i v_i h_i, где (x_i, y_i) и (u_i, v_i) — координаты двух противоположных углов основания здания в сантиметрах, h_i — высота здания в сантиметрах.

Основания зданий представляют собой прямоугольники со сторонами, параллельными осям координат.

Формат выходного файла

Выходной файл должен содержать целое число S — искомую площадь в квадратных сантиметрах.

Ограничения

1 ≤ N ≤ 10⁵.

0 ≤ x_i < u_i ≤ 10000, 0 ≤ y_i < v_i ≤ 10000, 0 < h_i ≤ 100.

Сумма площадей верхних и боковых граней всех зданий без учёта соприкасающихся частей не превосходит 10⁹.

Примеры тестов

1
0 5 5 7 3

52

2
0 5 5 7 3
3 2 6 5 4

97