#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)

#1004

Таймер

Темы: [Дата и время] [Строки] [Условный оператор (if)]

Источники: [ Личные олимпиады, Открытая олимпиада школьников, 2002, Задача A ] [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2002, Задача G ]

Задано время в формате ЧЧ:ММ:СС, а также количество часов, минут и секунд, которое необходимо прибавить к этому времени.

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

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

В первой строке входного файла записано текущее время в формате ЧЧ:ММ:СС (с ведущими нулями). При этом оно удовлетворяет ограничениям: ЧЧ - от 00 до 23, ММ и СС - от 00 до 60.

Во второй строке записан интервал времени, который должен быть измерен. Интервал записывается в формате Ч:М:С (где Ч, М и С - от 0 до 10⁹, без ведущих нулей). Дополнительно если Ч=0 (или Ч=0 и М=0), то они могут быть опущены. Например, 100:60 на самом деле означает 100 минут 60 секунд, что то же самое, что 101:0 или 1:41:0. А 42 обозначает 42 секунды. 100:100:100 - 100 часов, 100 минут, 100 секунд, что то же самое, что 101:41:40.

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

В выходной файл выведите в формате ЧЧ:ММ:СС время, во сколько прозвучит звуковой сигнал. При этом если сигнал прозвучит не в текущие сутки, то дальше должна следовать запись +<кол во> . Например, если сигнал прозвучит на следующий день – то +1 days.

Примеры

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

23:60:60
0

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

00:01:00+1 days

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

05:05:05
5:1

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

05:10:06

#1024

Сапер

Темы: [Двумерные массивы] [Условный оператор (if)]

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

Мальчику Васе очень нравится известная игра "Сапер" ("Minesweeper").

В "Сапер" играет один человек. Игра идет на клетчатом поле (далее будем называть его картой) NxM (N строк, M столбцов). В K клетках поля стоят мины, в остальных клетках записано либо число от 1 до 8 — количество мин в соседних клетках, либо ничего не написано, если в соседних клетках мин нет. Клетки являются соседними, если они имеют хотя бы одну общую точку, в одной клетке не может стоять более одной мины. Изначально все клетки поля закрыты. Игрок за один ход может открыть какую-нибудь клетку. Если в открытой им клетке оказывается мина — он проигрывает, иначе игроку показывается число, которое стоит в этой клетке, и игра продолжается. Цель игры — открыть все клетки, в которых нет мин.

У Васи на компьютере есть эта игра, но ему кажется, что все карты, которые в ней есть, некрасивые и неинтересные. Поэтому он решил нарисовать свои. Однако фантазия у него богатая, а времени мало, и он хочет успеть нарисовать как можно больше карт. Поэтому он просто выбирает N, M и K и расставляет мины на поле, после чего все остальные клетки могут быть однозначно определены. Однако на определение остальных клеток он не хочет тратить свое драгоценное время. Помогите ему!

По заданным N, M, K и координатам мин восстановите полную карту.

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

В первой строке входного файла содержатся числа N, M и K (1N200, 1M200, 0KNM). Далее идут K строк, в каждой из которых содержится по два числа, задающих координаты мин. Первое число в каждой строке задает номер строки клетки, где находится мина, второе число — номер столбца. Левая верхняя клетка поля имеет координаты (1,1), правая нижняя — координаты (N,M).

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

Выходной файл должен содержать N строк по M символов — соответствующие строки карты. j-й символ i-й строки должен содержать символ ‘*‘ (звездочка) если в клетке (i,j) стоит мина, цифру от 1 до 8, если в этой клетке стоит соответствующее число, либо ‘.‘ (точка), если клетка (i,j) пустая.

Примеры

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

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

.111.1*1.
13*2.111.
1**3.....
13*2.111.
.111.2*2.
233335*41
********1
*6*7*8*41
13*4***2.
.1122321.

#1026

Многочлен

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

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

Васе задали несколько однотипных задач по математике: «найти значение многочлена». Он хочет написать программу, которая по заданному многочлену и значению x находила бы ответ. Напишите такую программу!

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

В первой строке входного файла записан многочлен в виде суммы одночленов. Между одночленами находится знак + или –. Перед первым одночленом может быть знак –. Одночлен записывается как

[<Коэффициент>*]x[^<Степень>]

или

<Коэффициент>

где <Коэффициент> — натуральное число, не превосходящее 100, x — символ переменной (всегда маленькая латинская буква x), <Степень> — натуральное число, не превосходящее 4. Параметры, взятые в квадратные скобки, могут быть опущены. Во второй строке записано одно целое число — значение x.

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

В выходной файл нужно записать одно число — значение данного многочлена при данном значении x.

Ограничения

Все числа в исходном файле по модулю не превосходят 100. Количество одночленов не более 10 (могут быть одночлены одинаковой степени).

Примеры

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

8*x+5
7

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

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

-2+x^1-3*x^2+x^2+100*x^3-2*x
0

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

-2

#1038

Гексагон

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

Источники: [ Личные олимпиады, Открытая олимпиада школьников, 2005, Задача D ]

Поле для игры в новую игру "Гексагон" разбито на шестиугольники (см. рисунок). Игрок, стартуя из некоторого начального шестиугольника, сделал несколько ходов. Каждый ход заключается в премещении фишки в соседний шестиугольник (имеющий с тем, где находилась фишка до начала хода, общую сторону) — тем самым, ход делается вдоль одного из направлений X, Y или Z (см. рисунок). Игрок записал все свои ходы, причем если фишка двигалась вдоль какого-либо направления несколько раз подряд, то в записи это обозначается указанием направления и количества ходов, которые были сделаны.

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

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

В первой строке входного файла записано число N — количество строк в записи перемещений фишки (1N100). Далее идет N строк с записью ходов: в каждой строке записана сначала большая буква X, Y или Z, задающая направление, затем пробел, и число, задающее количество ходов в данном направлении (число может быть и отрицательным, если игрок перемещал фишку параллельно оси, но в направлении, противоположном направлению оси). Все числа по модулю не превышают 200.

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

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

Примеры

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

4
Z -2
Y 3
Z 3
X -1

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