#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

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

#498

Кубики

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

Источники: [ Командные олимпиады, Московская командная олимпиада, 8 класс, 2007, Задача H ]

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

В основании (нижнем ряду) такой лесенки расположено \(N\) кубиков, а каждый следующий ряд кубиков укладывается на предыдущий так, что один кубик укладывается ровно на один нижестоящий кубик, а по крайней мере на самый правый и самый левый кубики предыдущего ряда новые кубики не кладутся (чтобы получилась ступенька).

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

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

Вводятся два числа \(N\) и \(K\) (\(1 \le N \le 100\), \(1 \le K \le 100\)).

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

Выведите одно число – количество различных лесенок. Гарантируется, что правильный ответ не будет превышать \(10^{18}\).

Примеры

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

10 4

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

#500

Парикмахерская

Темы: [Задачи на моделирование]

Источники: [ Командные олимпиады, Московская командная олимпиада, 8 класс, 2007, Задача F ]

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

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

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

В первой строке вводится натуральное число N, не превышающее 100 – количество клиентов.

N строках вводятся времена прихода клиентов – по два числа, обозначающие часы и минуты (часы – от 0 до 23, минуты – от 0 до 59). Времена указаны в порядке возрастания (все времена различны).

Гарантируется, что всех клиентов успеют обслужить до полуночи.

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

Требуется вывести N пар чисел: времена выхода из парикмахерской 1-го, 2-го, …, N-го клиента (часы и минуты).

Примеры

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

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

10 30
10 31
10 32

#501

Пароль

Темы: [Строки]

Источники: [ Командные олимпиады, Московская командная олимпиада, 8 класс, 2007, Задача E ]

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

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

Вводится одна строка, состоящая только из латинских букв и цифр. Количество символов в строке не превышает 100.

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

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

Примеры

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

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

NO

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

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

NO