#1139

Город

Темы: [Одномерные массивы]

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

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

Правительство страны Ректилании решило построить новый город. По плану правительства, город должен быть построен на сетке M на N прямоугольных участков, размером 100 на 100 метров. Все улицы должны иметь ширину 100 метров и занимать соответственно одну горизонталь или вертикаль сетки. Вертикальные улицы должны пролегать по вертикалям с номерами X₁...X_V, горизонтальные – по горизонталям с номерами Y₁...Y_H. При этом улицы не соприкасаются, то есть не бывает X_i = X_i-1 + 1 и соответственно Y_j = Y_j-1 + 1.

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

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

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

На первой строке входного файла находятся числа M, N, V и H. (2 ≤ V < M ≤ 1000, 2 ≤ H < N ≤ 1000). На второй строке находятся координаты вертикальных улиц — V чисел: 1 = X₁ < X₂ < … < X_V = M. На третьей строке находятся координаты горизонтальных улиц — H чисел 1 = Y₁ < Y₂ < … < Y_H = N. Все числа в строках разделены пробелами.

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

Выведите в выходной файл три числа: A – количество домов в новом городе, B — количество клеток, в которых будет разбит парк и C — количество клеток, по которым будут пролегать улицы. Разделяйте числа пробелами.

Примеры

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

4 4 2 2
1 4
1 4

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

4 0 12

#1140

HTHL

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

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

Клуб Юных Хакеров разработал новый язык для web-страниц. В этом языке у тегов нет атрибутов, и запрещается использовать пробелы в написании тега. А именно: назовем открывающим тегом языка HTHL (Hyper Text Hackers' Language) следующую последовательность:

"<", имя тега, ">"

а закрывающим тегом последовательность

"</", имя тега, ">"

где имя тега – любая последовательность латинских букв и цифр, не длиннее 100 символов. Рассмотрим примеры тегов языка HTHL:

 <par> <hthl> <hacker2> <super>

 </hthl> </hyper> </down>

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

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

На первой строке входного файла находится число K (0 ≤ K ≤ 100) — количество имен тегов, которые не разрывают слово. Следующие K строк содержат имена этих тегов.

На следующей строке находится N — количество строк в странице HTHL, в которой следует осуществлять поиск (1 ≤ N ≤ 100). Следующие N строк содержат текст страницы, все строки не длиннее 250 символов.

Следующая строка содержит число M — количество запросов (1 ≤ M ≤ 100). Затем следует M строк — слова, поиск которых следует осуществить в документе. Словом является любая последовательность латинских букв и цифр не длиннее 250 символов.

Гарантируется, что страница HTHL является корректной, т.е. все символы "<", "/" и ">" используются только в тегах, все теги записаны корректно.

Различие между большими и маленькими буквами следует игнорировать.

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

Выведите в выходной файл M строк — для каждого слова выведите номер строки в странице, на которой оно впервые встречается, либо 0, если число не встречается на странице (Нумерация строк идет с 1).

Примеры

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

0
1
this page is very simple
5
this
page
is
very
simple

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

#1141

Нечестная игра

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

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

Есть число N. Играют два игрока, первый может отнять от числа любое число от 1 до K. На каждом следующем ходу можно отнять любое число от 1 до <предыдущий ход>+1. Проигрывает тот, кто возьмет последнюю спичку. Требуется вывести все первые ходы, приводящие к победе.

Петя придумал новую игру. На стол кладется кучка из N спичек, и затем Петя с Ваней по очереди берут спички из кучки. Первым берет Петя, ему разрешается взять от 1 до K спичек. Затем игрок может взять любое количество спичек, не более чем на 1 превышающее то количество, которое взял игрок перед ним (можно взять меньше или столько же, но обязательно хотя бы одну). Например, если N = 10, K = 5, то на первом ходу Петя может взять 1, 2, 3, 4 или 5 спичек, если Петя возьмет 3, то на следующем ходу Ваня может взять 1, 2, 3 или 4, и если Ваня возьмет 1, то Петя затем может взять 1 или 2, и т. д. Проигрывает тот, кто возьмет последнюю спичку.

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

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

На первой строке входного файла находятся числа N и K, разделенные пробелом. (1 ≤ K ≤ N ≤ 200).

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

Выведите в выходной файл все такие X, что, взяв на первом ходу X спичек, Петя выиграет. Если таких X не существует, выведите в выходной файл единственное число - 0. Числа следует разделять пробелами и выводить в порядке возрастания.

Примеры

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

2 2

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

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

5 4

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

1 4

#1142

Произведения

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

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

Дана квадратная таблица N на N. Рядом с каждым столбцом и каждой строкой написано целое положительное число. Пусть около i-го столбца написано число X_i, а около j-й строки – число Y_j. Для победы в конкурсе необходимо в некоторых клетках таблицы расположить целые положительные числа так, чтобы выполнялись следующие условия:

Все эти числа должны быть различными
В каждом столбце и каждой строке должно быть ровно 2 числа
Произведение чисел i-го столбца должно быть равно X_i.
Произведение чисел j-й строки должно быть равно Y_j.

Рисунок показывает пример решения такой задачи.

Помогите Пете!

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

На первой строке входного файла находится число N (2 ≤ N ≤ 10). На второй строке находится N чисел - X₁...X_N (1 ≤ X_i ≤ 1000 для всех 1 ≤ i ≤ N). На третьей строке также находится N чисел - Y₁...Y_N (1 ≤ Y_i ≤ 1000 для всех 1 ≤ i ≤ N).

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

Выведите в выходной файл таблицу после расстановки в ней чисел необходимым образом. Таблицу следует выводить по строкам: сначала N чисел первой строки, затем N чисел второй строки, и т. д. Если в соответствующей клетке стоит число, следует вывести это число, если клетка осталась пустой, следует вывести 0. Все числа в выходном файле следует разделять пробелами и/или переводами строк. Заботиться о красивом форматировании таблицы не надо. Если решений несколько, выведите любое из них. Гарантируется, что хотя бы одно решение будет существовать.

Примеры

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

2
15 8
6 20

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

  3   2 
  5   4

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

3
3 10 24
2 12 30

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

  1   2   0 
  3   0   4 
  0   5   6

#1143

Стена

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

Чтобы защитить свою страну от набегов кочевников, президент Флатландии решил построить Великую Флатландскую Стену. Страна Флатландия представляет собой координатную плоскость, ее столица находится в точке (0, 0). Именно из столицы и планируется начать строительство стены. Министру внутренних дел срочно поручили составить план постройки стены.

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

<направление строительства> <длина>

<направление перемещения> <расстояние>

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

Направление строительства задается заглавной латинской буквой, а направление перемещения – строчной латинской буквой. Соответствие букв направлениям приведено в следующей таблице:

Буква	Направление	Вектор
N n	Север	(0, 1)
E e	Восток	(1, 0)
S s	Юг	(0, -1)
W w	Запад	(-1, 0)

Длина и перемещение задаются в километрах и представляют собой целые числа.

Однако оказалось, что план министра может оказаться невыполнимым – в некоторый момент строители при выполнении инструкции могут столкнуться с уже построенной ими стеной! Выясните, выполним ли план министра и если нет, выведите координаты точки, в которой впервые произойдет столкновение с уже построенной стеной.

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

На первой строке входного файла расположено число N – количество инструкций в плане министра (0  N  1000). Последующие N строк содержат инструкции плана. Их формат следующий: сначала идет одна из допустимых букв, заглавная буква означает, что следует строить стену, а строчная – что следует просто переместиться. Затем, отделенное от буквы ровно одним пробелом, идет целое число X_i - какой длины следует строить стену, либо на сколько надо переместиться (1  X_i  10⁶).

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

На первой строке выходного файла выведите yes, если план можно выполнить, либо no, если нельзя. План можно выполнить, если строители, которых будем считать материальной точкой, никогда не оказываются в точке, через которую проходит участок стены, отличный от того, который они сейчас строят или только что построили (считаем стену состоящей из отрезков). В случае отрицательного ответа выведите на второй строке координаты точки, в которой произойдет столкновение со стеной, сначала X, затем Y. Числа должны быть разделены пробелом.

Примеры

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

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

YES

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

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

YES