Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 2 задач <---
Источники --> Личные олимпиады --> Международные олимпиады --> 2006
    1 тур(3 задач)
    2 тур(3 задач)
Страница: 1 Отображать по:
#553
Расшифровка письменности Майя
  
ограничение по времени на тест
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
#556
Мехико
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
16 megabytes

Город Мехико расположен в прекрасной долине, известной как Долина Мехико, на месте которой много лет назад было озеро. Около 1300 года ацтекские религиозные лидеры выпустили указ о том, что центр озера должен быть засыпан, чтобы построить столицу их империи. В настоящее время озеро полностью осушено.

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

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

*Он начинается в каком-либо городе, проходит через каждый прибрежный город и заканчивается в городе, отличном от того, в котором он начался.
*Маршрут проходит через каждый город ровно один раз.
*Любые два последовательно посещаемых города маршрута обязаны иметь между собой коммерческое соглашение.
*Маршрут состоит из отрезков прямых, каждый из которых соединяет два последовательно посещаемых города маршрута.
*Чтобы избежать столкновения лодок, маршрут не должен иметь самопересечений.


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

Этот маршрут нигде не имеет самопересечений. Но если построить маршрут, идущий из города 2 в город 6, затем в город 5, а затем в город 1, то он будет неправильным, поскольку имеет самопересечения.

Города нумеруются целыми числами от 1 до \(c\) по направлению часовой стрелки.

Задание

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

Ограничения

3 ≤ \(c\) ≤ 1000, \(c\) – число городов вокруг озера

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

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

СТРОКА 1: Содержит целое число \(c\).
СТРОКА 2: Содержит целое число \(n\) – количество коммерческих соглашений.
СЛЕДУЮЩИЕ \(n\) СТРОК: Каждая строка описывает одно коммерческое соглашение (одно соглашение описывается один раз). В строке задаются два целых числа, разделенных пробелами, которые соответствуют номерам городов, заключивших между собой коммерческое соглашение.

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

Если возможно построить маршрут товароперевозок, выведите c строк, в каждой из которых записано целое число. Эти числа представляют собой порядок посещения городов по маршруту товароперевозок. Если невозможно построить маршрут товароперевозок, удовлетворяющий всем указанным требованиям, выведите одну строку, содержащую отрицательное целое число -1.

Замечание

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

Оценивание

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

Примеры
Входные данные
7
9
1 4
5 1
1 7
5 6
2 3
3 4
2 6
4 6
6 7
Выходные данные
5
6
7
1
4
3
2
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест