Темы --> Информатика --> Язык программирования --> Типы данных --> Строки
---> 3 задач <---
Источники --> Личные олимпиады --> COCI --> COCI 2015-2016
    Раунд 1(6 задач)
    Раунд 2(6 задач)
    Раунд 3(6 задач)
    Раунд 4(6 задач)
    Раунд 5(6 задач)
    Раунд 6(6 задач)
Страница: 1 Отображать по:
#113558
Телефон Марко
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 2, Телефон Марко ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Марко обнаружил новую функцию на его телефоне - Т9. На его телефоне имеется стандартная клавиатура на 9 кнопок:

Для того чтобы вводить текст на этой клавиатуре необходимо несколько раз нажимать клавишу с соответствующей буквой. Точнее, если это первая буква на клавише, нужно нажать 1 раз, если вторая буква - 2 раза, и так далее. Например, если мы хотим ввести слово "giht", то необходимо нажать клавиши следующим образом: g-4 i-444 h-44 t-8. Новая возможность, которую открыл Марко, упрощает ввод текста, потому что больше не требуется нажимать по одной клавише несколько раз подряд - достаточно всего одного нажатия. Программа будет пытаться понять, какое слово из словаря вы пытаетесь ввести.

Марко довольно скептически относится к новым технологиями (как минимум к новым для него) и он боится, что ошибки будут довольно часто. Марко наизусть знает весь словарь мобильного телефона. Он состоит из N слов, состоящих из строчных латинских букв, длина каждого слова не превышает 1000000 символов. Марко даст массив нажатий на клавиши S длиной не более 1000, и хочет узнать как много слов из словаря он может получить при такой последовательности нажатий если используется функция Т9.

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

Первая строка содержит единственное целое число N ( 1 ≤ N ≤ 1000 ) - количество слов в словаре. Каждая из следующих N строк содержит одно слово из словаря S i ( 1 ≤ | S i | ≤ 1000000 ). Последняя строка содержит строку S ( 1 ≤ | S | ≤ 1000 ), состоящую из цифр от 2 до 9.

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

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

Примеры
Входные данные
3
tomo
mono
dak
6666
Выходные данные
1
Входные данные
2
ja
la
52
Выходные данные
2
Входные данные
3
dom
fon
tom
366
Выходные данные
2
#113572
Трезвый Доминик
  
Темы: [Строки]
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 4, Трезвый Доминик ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

Полицейский: Давайте начнём с чего-то простого. Какова асимптотика сортировки пузырьком?

Доминик: О, это просто. O ( n 2 ) .

Полицейский: Скажите английский алфавит наоборот.

Доминик: Легко, zyxwvutsrqponmlkjihgfedcba.

Полицейский: Вы просто запомнили это. Представьте, что строчные буквы латинского алфавита записаны по кругу по часовой стрелке. Начинайте с буквы 'a' и называйте все буквы подряд. После каждой сказанной буквы я могу приказать теперь называть в обратном порядке, спросить сколько раз была названа какая-то буква или ничего не делать. Приступайте.

Доминик: Хм... a, b, c...

Возможно, Доминик не настолько трезв, чтобы решить эту задачу. Помогите ему.

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

Первая строка содержит одно целое число Q ( 1 ≤ Q ≤ 10 5 ) – количество приказов полицейского. Каждая из последующих Q строк содержит один из приказов в формате "SMJER n" или "UPIT n x". Приказ первого типа обозначает, что после n -й сказанной буквы требуется поменять направление. Приказ второго типа обозначает, что Доминик должен сказать, сколько раз он произнес букву x после n сказанных букв.

Во всех запросах 1 ≤ n ≤ 10 9 , а x – строчные латинские буквы. В запросах n идут в строго возрастающем порядке.

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

Для каждого запроса вида "UPIT n x", выведите ответ на этот запрос, каждый в отдельной строке, в том же порядке, что и в вводе.

Система оценки

40 баллов: n ≤ 1000

60 баллов: n ≤ 10 5

100 баллов: n ≤ 10 9

Примечание

В первом примере Доминик говорит a, b, c, d, c, b, a, z, y, x.

Во втором примере Доминик говорит a, z, a, z, y, x, w.

Примеры
Входные данные
5
UPIT 1 b
UPIT 3 b
SMJER 4
UPIT 7 a
UPIT 10 z
Выходные данные
0
1
2
1
Входные данные
5
SMJER 1
SMJER 2
SMJER 3
UPIT 5 a
UPIT 7 w
Выходные данные
2
1
Входные данные
4
UPIT 100 a
UPIT 200 c
UPIT 300 a
UPIT 400 b
Выходные данные
4
8
12
16
#113578
Перо и страстная любовь
  
Темы: [Строки]
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 5, Перо и страстная любовь ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

Мультиграмма – это слово, которое состоит из конкатенации двух и более анаграмм. Первая из этих анаграмм называется корнем мультиграммы. Например, слово bbabab – мультиграмма с корнем bba, потому что она состоит из анаграмм bba и bab.

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

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

Единственная строка содержит слово, состоящее не более, чем из 10 5 строчных букв латинского алфавита.

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

Если данное слово – мультиграмма, выведите кратчайший из её корней. Иначе выведите -1.

Примечание

Решения, работающие когда длина строки не превосходит 500, будут оцениваться в 20 баллов.

Решения, работающие когда длина строки не превосходит 5000, будут оцениваться в 40 баллов.

Примеры
Входные данные
aaaa
Выходные данные
a
Входные данные
ab
Выходные данные
-1
Входные данные
bbabab
Выходные данные
bba
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест