Темы --> Информатика --> Алгоритмы --> Динамическое программирование --> Динамическое программирование: один параметр
---> 43 задач <---
Источники
    Личные олимпиады(925 задач)
    Командные олимпиады(684 задач)
Страница: 1 2 3 4 5 6 7 >> Отображать по:
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Профиль Уральских гор задается ломаной (x1, y1), (x2, y2), …, (xN, yN), для координат вершин которой верны неравенства x1 < x2 < … < xN. Начальные и конечные точки профиля расположены на уровне моря (y1 = yN = 0).

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

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

1

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

2

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

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

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

Последующие N строк содержат координаты вершин ломаной (x1, y1), (x2, y2), …, (xN, yN). Координаты вершин ломаной, а также точек A и B, задаются парой целых чисел, не превосходящих по абсолютному значению 106. Гарантируется, что x1 < x2 < … < xN и y1 = yN = 0, а также, что точки A и B принадлежат ломаной.

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

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

Примечание

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

Примеры
Входные данные
5 3
1 1
3 1
-1 0
0 2
2 0
4 2
5 0
Выходные данные
2.000000000
1.00000 1.00000
3.00000 1.00000
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

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

Примеры
Входные данные
1
Выходные данные
1
Входные данные
2
Выходные данные
5
Входные данные
4
Выходные данные
27
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

Примеры
Входные данные
4
Выходные данные
7
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

Примеры
Входные данные
1
Выходные данные
2
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

Пример

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

Страница: 1 2 3 4 5 6 7 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест