Сбор 2

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

Во входном файле записаны два целых неотрицательных числа `K` и `L` – количество узлов и единичных отрезков сетки соответственно. Оба числа не превосходят 1000.

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

2 7

2 3

1 4

2 2

Зал супермаркета имеет форму прямоугольника размером `M`x`N`, в котором расставлены витрины размером 1x1. Стороны витрин параллельны стенам супермаркета, а расстояния от витрин до стен – целые числа.

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

В первой строке входного файла записаны три натуральных числа `M`, `N` и `K` (`M,\ N\ ≤\ 100`, `K\ ≤\ M`). Начальное и конечное расположение супервитрины такие, как указано на верхнем рисунке. В следующей строке записано целое неотрицательно число `V` – количество витрин (`0\ ≤\ V\ ≤\ N*M`). В следующих `V` строках входного файла записаны различные пары целых неотрицательных чисел, характеризующие положения витрин. Первое число (от 0 до `M-1`) – расстояние от левой стены супермаркета до витрины, второе (от 0 до `N-1`) – расстояние от нижней стены до витрины (см. нижний рисунок). Гарантируется, что там, где изначально поставили супервитрину, других витрин нет.

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

Количество символов в строке не должно превышать `N`x`M`.

Если возможных маршрутов несколько, то выведите любой из них.

10 10 5
0

0
RUURUURUURUURU

9 3 2
4
2 0
5 1
5 2
8 2

1
URRRDRRRRUU

В текстовом редакторе Microsoft Word имеется достаточно мощный механизм поиска и замены, который доступен после установки флажка Подстановочные знаки (Use wildcards). При этом некоторые символы в строке поиска получают особый смысл.

Так, знаком вопроса в шаблоне поиска можно задать ровно один любой символ. Кроме того, в шаблоне поиска на месте одного из символов в квадратных скобках можно перечислить сразу несколько символов, никак их при этом не разделяя (поиск будет считаться успешным, если на этом месте стоит один из символов, указанных в [ ]). В квадратных скобках можно вместо любого символа указывать и диапазоны символов. Мы будем использовать только три следующих диапазона: 0-9, a-z и A-Z (других диапазонов не будет). В этом случае будет искаться один любой символ из указанного диапазона (диапазонов). Если же первый символ в квадратных скобках – !, то, наоборот, искаться будет любой символ, из не перечисленных после восклицательного знака в квадратных скобках (например, [!.a-z,] означает один любой символ кроме точки, запятой, и строчных латинских букв). Если же искать надо один из специальных символов !, ?, [, ], (, ), -, \ то, как в квадратных скобках, так и без скобок перед таким символом ставится \.

Еще одно замечательное свойство строки поиска – выражения. Выражением считается часть строки поиска, взятая в круглые скобки. Пар скобок может быть до 9, но вложенность не допускается. В строке замены выражения представляются в виде \`n`, где `n` – порядковый номер выражения в шаблоне поиска (от 1 до 9). Например, по шаблону поиска (k)(?)t и шаблону замены t\2\1 произойдут например, следующие замены:

kot `→` tok

kit `→` tik

Таким образом, в строке замены существует только один специальный символ – \, после которого обязательно должна идти цифра. Причем, например, цифра 5 может идти только если в строке поиска было не менее пяти выражений в скобках. При этом символы !, ?, [, ], (, ), - в строке замены указываются без предшествующего символа \, а символ \ используется только перед цифрой и обозначает номер выражения. В качестве символа, который должен попасть в конечный текст, символ \ в строке замены не может быть использован.

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

Требуется по данному образцу поиска и образцу замены, произвести все замены в заданном тексте.

В первой строке входного файла расположен текст, в котором требуется произвести все необходимые замены. Длина текста не превышает 100 символов. Во второй строке записан шаблон для поиска. Шаблон является корректным: каждой открывающей скобке соответствует закрывающая, восклицательный знак как спецсимвол употребляется только сразу за символом [ и т.д. В третьей строке расположен шаблон для замены. Выражения в шаблоне для замены также корректны. Длины шаблонов не превышают 100 символов. Коды всех символов, встречающихся как в тексте, так и в шаблонах находятся в диапазоне от 32 до 126. Символы перевода строки в сами шаблоны и в текст не входят.

Выведите в выходной файл одну строку – текст после всех произведенных замен.

Nothing is found.
find
replace

Nothing is found.

To be or not to be?
[A-Za-z][a-z]([!a-z])
be\1

be be be nbe be be?

To be or not to be?
(?)[a-z](?b)
\2\1

 bTe or not  bte?

http:\\olympiads.ru
\\\\
//!

http://!olympiads.ru

На окружности отметили `N` точек и пронумеровали их последовательно числами от 1 до `N`. Требуется найти количество различных простых ломаных с вершинами в некоторых из отмеченных точек и с концами в точках с номерами `i` и `j`.

Ломаная называется простой, если она не проходит дважды через одну точку (и не содержит самокасаний и самопересечений).

Во входном файле записано три натуральных числа `N`, `i`, `j` (`2\ ≤\ N\ ≤\ 2\ 000`, `1\ ≤\ i\ <\ j\ ≤\ N`).

В выходной файл надо вывести остаток от деления количества ломаных на `10^9`.

4 1 3

5

5 1 4

12