--->
35 задач
<---
Источники
#22
Источники:
[
Личные олимпиады,
Всероссийская олимпиада школьников,
Заключительный этап,
2007,
1 день,
Задача C
]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes
Профиль Уральских гор задается ломаной (x1, y1), (x2, y2), …, (xN, yN), для координат вершин которой верны неравенства x1 < x2 < … < xN. Начальные и конечные точки профиля расположены на уровне моря (y1 = yN = 0).
На горном профиле заданы две различные точки A и B, между которыми требуется проложить дорогу. Эта дорога будет проходить по склонам гор и проектируемому горизонтальному мосту, длина которого не должна превышать L. Оба конца моста находятся на горном профиле. Дорога заходит на мост с одного конца и выходит с другого. Мост не может содержать точек, расположенных строго под ломаной (строительство тоннелей не предполагается).
|
Возможные примеры расположения моста
|
Невозможное расположение моста
|
Достоверно известно, что строительство такого моста в данной местности возможно, причем позволит сократить длину дороги из точки 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 знаков после десятичной точки. В случае, когда решений несколько, выведите любое из них.
В примере в первой строке указана длина дороги от точки A до точки B с учётом построенного моста. Её не нужно выводить.
Примечание
Решения, корректно работающие при 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
#45
Темы:
[Эвристические методы]
[Стек]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
На складе хранятся контейнеры с товарами N различных видов. Все контейнеры составлены в N стопок. В каждой стопке могут находиться контейнеры с товарами любых видов (стопка может быть изначально пустой).Автопогрузчик может взять верхний контейнер из любой стопки и поставить его сверху в любую стопку. Необходимо расставить все контейнеры с товаром первого вида в первую стопку, второго вида — во вторую стопку и т.д.
Программа должна вывести последовательность действий автопогрузчика или сообщение о том, что задача решения не имеет.
Входные данные
В первой строке задается одно натуральное число N, не превосходящее 500. В следующих N строках описаны стопки контейнеров: сначала записано число ki — количество контейнеров в стопке, а затем ki чисел — виды товара в контейнерах в данной стопке, снизу вверх. В каждой стопке вначале не более 500 контейнеров (в процессе переноса контейнеров это ограничение может быть нарушено).
Выходные данные
Выведите описание действий автопогрузчика: для каждого действия укажите два числа — из какой стопки брать контейнер и в какую стопку класть. (Обратите внимание, что минимизировать количество операций автопогрузчика не требуется.) Если задача не имеет решения, выдайте одно число 0. Если контейнеры изначально правильно размещены по стопкам, выводить ничего не надо.
Оценка задачи
1 балл будут получать программы, верно работающие при следующих ограничениях: количество стопок не больше 10, в каждой стопке не более 10 контейнеров.
Комментарий к примеру:
Изначально в первой стопке лежат четыре контейнера — снизу контейнер с товаром первого вида, над ним — с товаром второго вида, над ним — третьего, и сверху — еще один контейнер с товаром второго вида.
Одна из правильных последовательностей действий (вместо ответа в примере задачи):
1 2
1 3
1 2
Примеры
Входные данные
3 4 1 2 3 2 0 0
Выходные данные
1
Рассмотрим последовательность, состоящую из круглых, квадратных и фигурных скобок. Программа дожна определить, является ли данная скобочная последовательность правильной.
Пустая последовательность явлется правильной. Если A – правильная, то последовательности (A), [A], {A} – правильные. Если A и B – правильные последовательности, то последовательность AB – правильная.
Входные данные
В единственной строке записана скобочная последовательность, содержащая не более 100000 скобок.
Выходные данные
Если данная последовательность правильная, то программа должна вывести строку yes, иначе строку no.
Примеры
Входные данные
()[]
Выходные данные
yes
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
В постфиксной записи (или обратной польской записи) операция записывается после двух операндов. Например, сумма двух чисел A и B записывается как A B +. Запись B C + D * обозначает привычное нам (B + C) * D, а запись A B C + D * + означает A + (B + C) * D. Достоинство постфиксной записи в том, что она не требует скобок и дополнительных соглашений о приоритете операторов для своего чтения.
Входные данные
В единственной строке записано выражение в постфиксной записи, содержащее цифры и операции +, -, *. Цифры и операции разделяются пробелами. В конце строки может быть произвольное количество пробелов.
Выходные данные
Необходимо вывести значение записанного выражения.
Примеры
Входные данные
8 9 + 1 7 - *
Выходные данные
-102
На складе хранятся контейнеры с товарами N различных видов. Все контейнеры составлены в N стопок. В каждой стопке могут находиться контейнеры с товарами любых видов (стопка может быть изначально пустой).
Автопогрузчик может взять верхний контейнер из любой стопки и поставить его сверху в любую стопку. Необходимо расставить все контейнеры с товаром первого вида в первую стопку, второго вида – во вторую стопку и т.д.
Программа должна вывести последовательность действий автопогрузчика или сообщение о том, что задача решения не имеет.
Формат входных данных
В первой строке входных данных записано одно натуральное число N, не превосходящее 500. В следующих N строках описаны стопки контейнеров: сначала записано число ki – количество контейнеров в стопке, а затем ki чисел – виды товара в контейнерах в данной стопке, снизу вверх. В каждой стопке вначале не более 500 контейнеров (в процессе переноса контейнеров это ограничение может быть нарушено).
Формат выходных данных
Программа должна вывести описание действий автопогрузчика: для каждого действия напечатать два числа – из какой стопки брать контейнер и в какую стопку класть. (Обратите внимание, что минимизировать количество операций автопогрузчика не требуется.) Если задача не имеет решения, необходимо вывести одно число 0. Если контейнеры изначально правильно размещены по стопкам, то выводить ничего не нужно.
Пример
|
Входные данные |
Выходные данные |
| 3 4 1 2 3 2 0 0 |
1 2 1 3 1 2 |
Объяснение примера. Изначально в первой стопке лежат четыре контейнера – снизу контейнер с товаром первого вида, над ним – с товаром второго вида, над ним третьего, и сверху еще один контейнер с товаром второго вида. Вторая и третья стопки – пусты.
Выбрано
:
|