#22

Темы: [Стек] [Динамическое программирование: один параметр] [Жадный алгоритм]

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

Профиль Уральских гор задается ломаной (x₁, y₁), (x₂, y₂), …, (x_N, y_N), для координат вершин которой верны неравенства x₁ < x₂ < … < x_N. Начальные и конечные точки профиля расположены на уровне моря (y₁ = y_N = 0).

На горном профиле заданы две различные точки A и B, между которыми требуется проложить дорогу. Эта дорога будет проходить по склонам гор и проектируемому горизонтальному мосту, длина которого не должна превышать L. Оба конца моста находятся на горном профиле. Дорога заходит на мост с одного конца и выходит с другого. Мост не может содержать точек, расположенных строго под ломаной (строительство тоннелей не предполагается).

Возможные примеры расположения моста

Невозможное расположение моста

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

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

Первая строка входных данных содержит два целых числа N и L — количество вершин ломаной (2 ≤ N ≤ 100 000) и максимальную длину моста (1 ≤ L ≤ 10⁶) соответственно. Вторая строка содержит координаты точки A, третья строка — координаты точки B. Точки A и B различны.

Последующие N строк содержат координаты вершин ломаной (x₁, y₁), (x₂, y₂), …, (x_N, y_N). Координаты вершин ломаной, а также точек A и B, задаются парой целых чисел, не превосходящих по абсолютному значению 10⁶. Гарантируется, что x₁ < x₂ < … < x_N и y₁ = y_N = 0, а также, что точки A и B принадлежат ломаной.

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

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

В примере в первой строке указана длина дороги от точки A до точки B с учётом построенного моста. Её не нужно выводить.

Примечание

Решения, корректно работающие при N ≤ 2000, будут оцениваться, исходя из 80 баллов.

Примеры

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

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

2.000000000
1.00000 1.00000
3.00000 1.00000

#35

Количество треугольников

Темы: [Динамическое программирование: один параметр]

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2005, Задача J ]

Рассмотрим фигуру, аналогичную показанной на рисунке (большой равносторонний треугольник, составленный из маленьких равносторонних треугольников). На рисунке приведена фигура, состоящая из 4-х уровней треугольников.

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

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

Вводится одно число \(N\) — количество уровней в фигуре (\(1\le N \le 100000\)).

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

Выведите количество треугольников в такой фигуре.

Примеры

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

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

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

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

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

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

#203

Мячик на лесенке

Темы: [Динамическое программирование: один параметр] [Рекуррентные последовательности]

На вершине лесенки, содержащей N ступенек, находится мячик, который начинает прыгать по ним вниз, к основанию. Мячик может прыгнуть на следующую ступеньку, на ступеньку через одну или через 2. (То есть, если мячик лежит на 8-ой ступеньке, то он может переместиться на 5-ую, 6-ую или 7-ую.) Определить число всевозможных "маршрутов" мячика с вершины на землю.

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

Вводится одно число 0 < N < 31.

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

Выведите одно число — количество маршрутов.

Примеры

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

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

#207

Последовательность из 0 и 1

Темы: [Динамическое программирование: один параметр] ["Длинная" арифметика]

Требуется подсчитать количество последовательностей длины \(N\), состоящих из 0 и 1, в которых никакие две единицы не стоят рядом.

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

На вход программы поступает целое число \(N\) (\(1\le N\le100\)).

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

Выведите количество искомых последовательностей.

Примеры

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

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

#210

Гвоздики

Темы: [Динамическое программирование: один параметр]

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

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

В первой строке входных данных записано число \(N\) — количество гвоздиков (\(2\le N\le100\)). В следующей строке заданы \(N\) чисел — координаты всех гвоздиков (неотрицательные целые числа, не превосходящие 10000).

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

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

Пример

Входные данные	Выходные данные
5 4 10 0 12 2	6