Страница: 1 Отображать по:
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
32 megabytes
Дана строка и подстрока. Требуется определить, сколько раз в строке встречалась подпоследовательность, состоящая из символов подстроки.

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

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

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

Археологи ищут некоторое слово $W$. Они знают значки для него, но не знают все возможные способы их расположения. Поскольку они знают, что Вы приедете на IOI ’06, они просят Вас о помощи. Они дадут Вам $g$ значков, составляющих слово $W$, и последовательность $S$ всех значков в надписи, которую они изучают, в порядке их появления. Помогите им, подсчитав количество возможных появлений слова $W$.

Задание

Напишите программу, которая по значкам слова $W$ и по последовательности $S$ значков надписи подсчитывает количество всех возможных вхождений слова $W$ в $S$, то есть количество всех различных позиций идущих подряд $g$ значков в последовательности $S$, которые являются какой-либо перестановкой значков слова $W$ .

Ограничения

1 ≤ $g$ ≤ 3 000, $g$ – количество значков в слове $W$

$g$ ≤ |$S$| ≤ 3 000 000 где |$S$| – количество значков в последовательности $S$

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

На вход программы поступают данные в следующем формате:

СТРОКА 1: Содержит два числа, разделенных пробелом – $g$ и |$S$|.
СТРОКА 2: Содержит $g$ последовательных символов, с помощью которых записывается слово $W$ . Допустимы символы: ‘a’-‘z’ и ‘A’-‘Z’; большие и маленькие буквы считаются различными.
СТРОКА 3: Содержит |$S$| последовательных символов, которые представляют значки в надписи. Допустимы символы: ‘a’-‘z’ и ‘A’-‘Z’; большие и маленькие буквы считаются различными.

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

Единственная строка выходных данных программы должна содержать количество возможных вхождений слова $W$ в $S$.

Оценивание

Для части тестов, оцениваемых в 50 баллов, выполняется ограничение $g$ ≤ 10.

Важно для программирования на PASCAL

По умолчанию во FreePascal переменная типа string имеет ограничение размера в 255 символов. Если Вы хотите использовать более длинные строки, Вы должны добавить директиву {$ H +} в ваш код, сразу после строки program ...;.

Примеры
Входные данные
4 11
cAda
AbrAcadAbRa
Выходные данные
2
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
32 megabytes

После победы в великой битве Король Ягуар хочет построить пирамиду, которая будет одновременно монументом в честь победы и гробницей для погибших солдат. Пирамида будет построена на поле боя. Она должна иметь прямоугольное основание, состоящее из $a$ столбцов и $b$ строк. Для сохранения останков и оружия павших солдат внутри основания пирамиды будет располагаться небольшая прямоугольная комната, состоящая из $c$ столбцов и $d$ строк.

Архитекторы Короля представили поле боя в виде прямоугольной сетки. Эта сетка состоит из квадратных клеток единичной площади и имеет $m$ столбцов и $n$ строк. Для каждой клетки они измерили ее высоту и получили некоторое целое число.

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

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

Задание

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

Ограничения

3 ≤ $m$ ≤ 1000
3 ≤ $n$ ≤ 1000
3 ≤ $a$ ≤ $m$
3 ≤ $b$ ≤ $n$
1 ≤ $c$ ≤ $a$ – 2
1 ≤ $d$ ≤ $b$ – 2
Все высоты – целые числа от 1 до 100.

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

Ваша программа получает входные данные в следующем формате:
СТРОКА 1: Содержит шесть целых чисел, разделенных пробелами, в следующем порядке: $m$, $n$, $a$, $b$, $c$ и $d$.
СЛЕДУЮЩИЕ $n$ СТРОК: Каждая из этих строк содержит m целых чисел, разделенных пробелами. Эти числа соответствуют высотам клеток в одной строке сетки. Первая из этих строк соответствует верхней строке (строке 1) сетки, а последняя – нижней строке (строке $n$). При этом $m$ чисел в каждой строке соответствуют высотам клеток этой строки, начиная со столбца 1.

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

Ваша программа должна вывести следующие данные:
СТРОКА 1: Должна содержать два целых числа, разделенные пробелом, – координаты левой верхней клетки основания пирамиды, при этом первое число соответствует столбцу, а второе – строке.
СТРОКА 2: Должна содержать два целых числа, разделенные пробелом, – координаты левой верхней клетки комнаты, при этом первое число соответствует столбцу, а второе – строке.

Замечание

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

Оценивание

Ряд тестов с общей суммой 30 баллов будет удовлетворять следующим ограничениям:
3 ≤ $m$ ≤ 10
3 ≤ $n$ ≤ 10

Примеры
Входные данные
8 5 5 3 2 1
1 5 10 3 7 1 2 5
6 12 4 4 3 3 1 5
2 4 3 1 6 6 19 8
1 1 1 3 4 2 4 5
6 6 3 3 3 2 2 2
Выходные данные
1
4 1
6 2
ограничение по времени на тест
5.0 second;
ограничение по памяти на тест
64 megabytes

В игре "Чёрный ящик" используется квадратный чёрный ящик, лежащий на столе. Каждая из его сторон имеет $n$ отверстий, в каждое из $4n$ которых можно запустить шарик, который через некоторое время вылетит обратно из одного из отверстий.

Внутренность коробки можно представить в виде сетки $n \times n$. Отверстия ящика - это границы сетки. Каждая из ячеек сетки либо пуста, либо содержит отражатель

Отражатель - это стенка, направленная под углом 45 градусов к линиям сетки так, что при соударении шарика с отражателем он меняет направление своего полёта на 90 градусов.

Шарик, запущенный внутрь коробки, катится прямолинейно, пока либо он не вылетит из коробки, либо не встретится с отражателем. При попадании в отражатель он отскакивает от него (направление его полёта меняется на 90 градусов), а отражатель поворачивается на 90 градусов.

a) Шарик запущен в отверстие; он ударяется об отражатель и летит вниз.

b) После соударения с шариком отражатель инвертирует своё положение. Новый шарик запущен в чёрный ящик в то же отверстие, что и первый, и после соударения с отражателем он полетит вверх.

c) Отражатель меняет своё состояние после каждого соударения.

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

Коробка имеет две кнопки. Первая кнопка сбрасывает все отражатели - каждый отражатель возвращается в своё исходное положение. Вторая инвертирует все отражатели в коробке.

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

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

Сначала вам на вход подаётся одно целое число $n (1 \leq n \leq 30)$. Далее процесс общения программы с чёрным ящиком устроен в форме "запрос-ответ". Возможные запросы:

$1$ $s$ $h$ - после этого запроса запускается шар в отверстие, расположенное на стороне $s$ (1 - верхняя сторона, 2 - правая сторона, 3 - нижняя сторона, 4 - левая сторона), и имеющее номер $h (1 \leq h \leq n)$ (отверстия нумеруются сверху вниз и слева направо). Ваша программа должна считать три числа - $c, s', h'$, разделённых пробелами, соответственно количество соударений и номер стороны и номер отверстия вылета в формате, описанном выше.

$2$ - после этого запроса все отражатели сбрасываются.

$3$ - после этого запроса все отражатели инвертируются

$0$ - после этого запроса вы заканчиваете работу с чёрным ящиком и должны вывести содержимое коробки (см. пример для точного понимания формата).

Обратите внимание, что после каждого запроса вы должны вывести перевод строки и сбросить буфер вывода командой flush(output) в Паскале, fflush(stdout) (cout.flush()) на языках C/C++. В других языках достаточно вывести после команды перевод строки. Следуйте формату общения с чёрным ящиком с точностью до пробела.

Пример тестов

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

1 4 3

1 1 3


3 1 2


4 2 3


0 3 1




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

1 3 3

1 2 1

3
1 2 3

2
1 4 2

2
1 1 1

0
./\
./.
..\

Дополнительная информация

Решение жюри находит содержимое коробки на каждом тесте жюри не более чем за 1.8 секунды. Жюри не гарантируется существование решения на всех возможных тествах.


Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест