Задача A. Отрезки с наложением ≡

Условие

Дано N отрезков с длинами w₁, …, w_N. Требуется расположить их на интервале числовой оси [0, L] так, чтобы они покрыли этот интервал без пропусков и не выходили за его границы.

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

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

Первая строка входного файла содержит целые числа N и L.

Вторая строка содержит N целых чисел w₁ w₂… w_N.

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

Выходной файл должен содержать N целых чисел x₁ x₂… x_N — координаты левых концов отрезков.

Если решения не существует, то выходной файл должен содержать единственное число −1. Если существует несколько решений, вывести любое из них.

Ограничения

1 ≤ N ≤ 1000, 1 ≤ L ≤ 10000, 1 ≤ w_i ≤ 10000.

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

2 3
2 2

0 1

Задача B. Стиральный вопрос ≡

Условие

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

Рабочие могут передвигать стиральную машину на свободное место, соседнее с ней по горизонтали или вертикали.

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

В начальный момент времени координаты помятой машины — (1, 1), координаты выхода — (N, M), свободное место расположено в тех же координатах, что и выход.

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

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

Ограничения

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

2 2

5

5 3

23

3 7

35

Задача C. Шагающий циркуль ≡

Условие

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

Найти наименьшее количество шагов циркуля, которое нужно сделать, чтобы одна из его ножек оказалась в точке B. Раствор циркуля (т. е. длина шага) s может изменяться от s₁ до s₂ включительно (s₁ ≤ s ≤ s₂).

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

Первая строка содержит вещественные числа x_A y_A x_B y_B — координаты точек A и B.

Вторая строка содержит вещественные числа s₁ s₂.

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

Выходной файл должен содержать единственное целое число — минимальное количество шагов циркуля.

Ограничения

−70 < x_A, y_A, x_B, y_B < 70,

1 ≤ s₁ ≤ s₂ < 100.

Все входные данные имеют не более двух знаков после запятой и заданы точно (не содержат ошибки округления).

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

1 1.5 3 0.5
1.0 1.2

2

Задача D. Хоттаб-share ≡

Условие

Прожив 1000 лет, Гассан Абдуррахман ибн Хоттаб узнал, что из интернета можно скачивать файлы. Решив помочь другим пользователям, он сотворил собственный сервер с файлами. Поскольку сервер Хоттаба волшебный, любой файл скачивается с него мгновенно. Однако, после скачивания файла размером S мегабайт скачавший его компьютер отключается от сервера на S секунд.

В распоряжении шушанчиков имеется два компьютера, подключённых к интернету. Им требуется скачать N файлов, i-й файл размером s_i мегабайт. Шушанчики просят Вас рассчитать минимальное время, за которое можно скачать эти файлы с сервера Хоттабыча.

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

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

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

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

Ограничения

1 ≤ N ≤ 500

1 ≤ s_i ≤ 500

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

3
13 17 4

4

7
1 2 23 24 43 44 45

47

Задача E. Флэш-моб ≡

Условие

Жители одного N-этажного дома решили устроить флэш-моб — изобразить ночью на стене дома ползущую "змейку" из L светящихся окон, включая и выключая свет в определённом порядке.

Они придумали схему движения змейки, которая представляет собой последовательность шагов R, L, U, D для движения вправо, влево, вверх и вниз соответственно. Если змейка достигает одного из краев стены, она выползает с другого края (если была наверху и ползла вверх — выползает снизу, и т.д.). Змейка должна выполнять один шаг в секунду.

Теперь нужно для каждого окна определить моменты включения и выключения света.

Окна пронумерованы слева направо снизу вверх, начиная с 1. На каждом этаже имеется по M окон. В начальный момент времени видна только "голова" змейки, которая находится в первом окне. В течении первых L шагов в первом окне появляются последующие части змейки. Перед началом движения свет во всех окнах выключен, по окончании движения он также выключается.

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

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

В первой строке входного файла содержатся числа N M L. Во второй строке — описания шагов для змейки, записанные подряд без пробелов.

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

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

Ограничения

1 ≤ N ≤ 50, 1 ≤ M ≤ 50, 1 ≤ L ≤ 1000

Количество шагов находится в диапазоне от 1 до 10000

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

5 4 4
RRULDDL

1 1  1 4
2 1  2 8
3 1  3 6
6 1  5 8
7 1  4 7
17 1  8 8
18 1  7 8

Задача F. Бег по коридору ≡

Условие

Школьник Петя собрал собственный цветной дисплей с разрешением 2 пикселя по вертикали и N пикселей по горизонтали. Каждый пиксель определяется координатами (a, b), где a — номер строки от 1 до 2, а b — номер столбца от 1 до N.

На дисплее с таким разрешением уже можно играть и Петя разрабатывает одну из игр — "Бег по коридору". По правилам игры, каждый пиксель может быть либо свободен, либо занят препятствием, либо занят игроком, либо занят эликсиром. Игрок может перемещаться в один из смежных пикселей, не занятых препятствием (смежными называются пиксели, соседствующие либо в строке, либо в столбце).

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

Изначально игрок находится в пикселе с координатами (1, 1). Цель игры — добраться до N-ого столбца, минимизировав конечный уровень усталости.

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

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

В первой строке входного файла содержится число N — горизонтальное разрешение дисплея. Далее следует описание игрового поля — пара строк длиной N каждая. Символ "." (точка) соответствует свободному пикселю, символ "#" (решетка) — занятому препятствием, символ "X" (прописная латинская X) — пикселю с эликсиром.

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

Гарантируется, что можно добраться до N-ого столбца.

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

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

Ограничения

2 ≤ N ≤ 100

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

2
..
.#

1

6
....X.
#XXX..

3

Задача G. Шахматный король ≡

Условие

Дана шахматная доска размером N × M клеток. Клетки на ней обозначаются парами координат — номерами вертикали и горизонтали.

В клетке (1, 1) расположен шахматный король. Требуется обойти королём доску, побывав в каждой клетке ровно один раз, и вернувшись в исходную позицию.

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

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

Входной файл содержит числа N M.

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

Выходной файл должен содержать N × M пар чисел v h — координаты клеток, через которые проходит путь короля (1 ≤ v ≤ N, 1 ≤ h ≤ M). Первая клетка в пути должна иметь координаты (1, 1), а последняя — (1, 2), (2, 1) или (2, 2). Если имеется несколько решений, вывести любое из них.

Ограничения

2 ≤ N, M ≤ 100.

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

4 2

1 1  2 1  3 1  4 1  4 2  3 2  2 2  1 2

Задача H. Лэнгфорд плюс один ≡

Условие

Назовем расширенной последовательностью Лэнгфорда такую последовательность из 2 N целых чисел, что:

1. Все числа находятся в диапазоне то 1 до N + 1.
2. Каждое число, входящее в последовательность, встречается в ней ровно два раза.
3. Между двумя вхождениями числа k в последовательность находятся ровно k других чисел.

Требуется по данному N найти соответствующую расширенную последовательность Лэнгфорда.

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

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

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

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

Ограничения

4 ≤ N ≤ 40

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

4

2 3 4 2 1 3 1 4

5

4 5 6 2 3 4 2 5 3 6