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

#1025

Робот K-79

Темы: [Двумерные массивы]

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

Петя написал программу движения робота К-79. Программа состоит из следующих команд:

S — сделать шаг вперед
L — повернуться на 90 влево
R — повернуться на 90 вправо

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

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

Во входном файле записана одна строка из заглавных латинских букв S, L, R, описывающая программу для робота. Общее число команд в программе не превышает 200, при этом команд S — не более 50.

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

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

Примеры

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

RSSSRSLSLSSRSRS

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

-1

#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

#1027

Головоломка

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

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

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

Петя разгадывает головоломку, которая устроена следующим образом. Дана квадратная таблица размера NxN, в каждой клетке которой записана какая-нибудь латинская буква. Кроме того, дан список ключевых слов. Пете нужно, взяв очередное ключевое слово, найти его в таблице. То есть найти в таблице все буквы этого слова, причем они должны быть расположены так, чтобы клетка, в которой расположена каждая последующая буква слова, была соседней с клеткой, в которой записана предыдущая буква (клетки называются соседними, если они имеют общую сторону — то есть соседствуют по вертикали или по горизонтали). Например, на рисунке ниже показано, как может быть расположено в таблице слово olympiad.

P	O	L	T	E
R	W	Y	M	S
O	A	I	P	T
B	D	A	N	R
L	E	M	E	S

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

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

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

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

В первой строке входного файла записаны два числа N (1N10) и M (0M200). Следующие N строк по N заглавных латинских букв описывают ребус. Следующие M строк содержат слова. Слова состоят только из заглавных латинских букв, каждое слово не длиннее 200 символов. Гарантируется, что в таблице можно найти и вычеркнуть по описанным выше правилам все ключевые слова.

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

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

Примеры

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

5 3
POLTE
RWYMS
OAIPT
BDANR
LEMES
OLYMPIAD
PROBLEM
TEST

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

AENRSW

#1028

Поиск прямоугольников

Темы: [Динамическое программирование на таблицах] [Клеточная геометрия]

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

0	2	2	2	2
0	2	2	2	2
1	1	2	2	2
1	1	0	0	0

На поле NxM клеток (N строк и M столбцов) положили K прямоугольников один поверх другого в случайном порядке. Длины сторон прямоугольников выражаются целым числом клеток. Прямоугольники не выходят за границы поля. Границы прямоугольников совпадают с границами клеток поля.

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

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

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

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

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

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

В выходной файл необходимо выдать K строк. Каждая строка должна описывать соответствующий ее номеру прямоугольник четырьмя числами R C H W (R и C должны описывать координаты левого нижнего угла прямоугольника, а H и W — координаты правого верхнего угла). Числа должны разделяться пробелом.

Оси координат устроены следующим образом: начало координат находится в нижнем левом углу поля, а оси координат направлены вдоль сторон поля (ось Ox — вдоль нижней стороны, а ось Oy — вдоль левой стороны). Клетки поля имеют размер 1x1. Таким образом, координаты левого нижнего угла поля — (0,0), правого верхнего — (M,N). Заметьте, что вы должны вывести координаты углов прямоугольников (как точек) в этой системе координат, а не координаты угловых клеток, покрытых прямоугольниками.

Примеры

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

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

0 0 2 2
1 1 5 4