#431

Темы: [Условный оператор (if)] [Эвристические методы]

Источники: [ Личные олимпиады, Открытая олимпиада школьников, 2004, Задача M ] [ Командные олимпиады, ВКОШП, 2004, Задача I ]

Задана последовательность команд "поворот налево" и "поворот направо". Требуется каждой команде сопоставить число шагов, чтобы путь не пересекал и не касался самого себя.

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

Программа для робота представляет собой последовательность команд. Команды робота приведены в следующей таблице:

Команда	Обозначение	Действия робота
Перемещение	(X)	Переместиться вперед на X километров, прокладывая за собой оросительный канал
Поворот налево	L	Повернуть налево на 90^o
Поворот направо	R	Повернуть направо на 90^o

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

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

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

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

Входные данные содержат команды поворота исходной программы в том порядке, в котором они в ней следовали. Каждая команда представляет собой символ «L» либо «R», команды друг от друга не отделяются. Количество команд не превышает 30 000.

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

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

Примеры

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

LLLRRR

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

(4)L(3)L(1)L(2)R(2)R(1)R(1)

#432

Лесопилка

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

Источники: [ Командные олимпиады, ВКОШП, 2004, Задача J ]

Имеется неограниченное количество досок, длины Z. Необходимо напилить A досок длины X и B досок длины Y. Необходимо подсчитать минимальное количество распилов, обрезки можно выкидывать.

Недавно на лесопилку, где работает Вася, поступил новый заказ. Для постройки нового дома мэру соседнего города требуется a досок длины x футов и b досок длины y футов.

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

Например, если на лесопилке имеются доски длины 80, а клиенту требуется две доски длины 30 и семь досок длины 20, то достаточно сделать семь распилов: одну доску распилить двумя распилами на доски длины 20, 30 и 30, одну тремя распилами на четыре доски длины 20 и одну двумя распилами на доски длины 20, 20 и 40. Доска длины 40 клиенту не нужна, она останется на лесопилке, остальные доски будут отправлены клиенту.

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

На вход программы поступают числа \(a, x, b, y \) и \( z \). Все числа положительны и не превышают 300, \( x \le z, y \le z, x \neq y \).

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

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

Примеры

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

2 30 7 20 80

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

#433

Точка пересечения прямых

Темы: [Элементарная геометрия]

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

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

Вводятся сначала координаты двух различных точек, через которые проходит первая прямая, а затем - координаты еще двух различных (но, быть может, совпадающих с первыми двумя) точек, через которые проходит вторая прямая. Координаты каждой точки - целые числа, по модулю не превышающие 1000.

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

Если прямые не пересекаются, выведите одно число 0. Если прямые совпадают, выведите 2. Если прямые пересекаются ровно в одной точке, то выведите сначала число 1, а затем два вещественных числа - координаты точки пересечения.

Примеры

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

0 0 1 1
1 0 -1 2

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

1  5.0000000E-0001  5.000000E-0001

#434

Положение точек вне прямой

Темы: [Элементарная геометрия]

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

Семь чисел - координаты двух точек вне прямой и коэффициенты A, B и C её уравнения.

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

Выведите одну строку: "YES", если точки лежат по одну сторону прямой, и "NO" в противном случае.

Примеры

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

0 1 1 0 0 -4 8

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

YES

#435

Перпендикулярная прямая

Темы: [Элементарная геометрия]

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

Пять чисел - коэффициенты A, B и C уравнения прямой и координаты некоторой точки X, Y (точка может быть как на прямой, так и вне ее). Все числа целые, по модулю не превосходят 1000.

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

Выведите три числа - коэффициенты A, B и C уравнения прямой, перпендикулярной заданной и проходящей через заданную точку. Числа в ответе должны быть выданы с точностью не менее 5 знаков после десятичной точки.

Примеры

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

0 -4 8 5 0

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

-4.00000 0.00000 20.00000