Темы --> Информатика --> Алгоритмы --> Обработка текста
    Конечные автоматы(10 задач)
    Разбор выражений(17 задач)
---> 7 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(17 задач)
    Школьная личная олимпиада ФМШ №2007 г. Москвы(7 задач)
    Золотая середина (Новосибирск)(10 задач)
    Нижегородская олимпиада школьников(42 задач)
    Московская олимпиада школьников(168 задач)
    Индивидуальная олимпиада по информатике и программированию (ИОИП)(22 задач)
    Открытая олимпиада школьников(173 задач)
    Украинские олимпиады(61 задач)
    Республиканская олимпиада школьников (Беларусь)(6 задач)
    Жаутыковские олимпиады(8 задач)
    Всероссийская олимпиада школьников(304 задач)
    Международные олимпиады(32 задач)
    Central European Olympiad in Informatics (4 задач)
    Интернет-олимпиады(2 задач)
    COCI(36 задач)
    Турнир Архимеда(36 задач)
    Baltic Olympiad in Informatics(10 задач)
Страница: << 1 2 Отображать по:
#3332
Дуэт на клавиатуре
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

В 2030 году Очень Известная Компания выпустила новую клавиатуру. Разработчики решили избавиться от всех ненужных кнопок и оставить только кнопки с первыми \(A\) буквами латинского алфавита. Новая клавиатура пользуется большой популярностью, поэтому Петя решил научиться печатать на ней свое любимое слово (оно не содержит букв, отличных от первых \(A\) букв латинского алфавита).

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

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

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

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

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

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

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

Выведите одно число - искомое количество нажатий клавиш.

Примечания

Тесты состоят из четырёх групп.

  1. Тесты 1--3, из условия, оцениваются в 0 баллов.
  2. В тестах этой группы \(1 \le N < A \le 26\), \(1 \le K \le 100\). Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы (при этом прохождения всех тестов из условия не требуется).
  3. В тестах этой группы \(1 \le N \le 300\), \(1 \le A \le 26\), \(1 \le K \le 300\). Эта группа также оценивается в 30 баллов, они начисляются только при прохождении всех тестов группы.
  4. Offline-группа, \(1 \le N \le 100\,000\), \(1 \le A \le 26\), \(1 \le K \le 10^9\). Баллы за тесты этой группы начисляются только при прохождении всех тестов 1-й и 2-й групп. Эта группа оценивается в 40 баллов, они начисляются только при прохождении всех тестов группы.

Примеры
Входные данные
2 1 2
aa
Выходные данные
2
Входные данные
3 4 3
abc
Выходные данные
9
Входные данные
3 2 1
aab
Выходные данные
4
#111857
Телефонные номера
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Телефонные номера в адресной книге мобильного телефона имеют один из следующих форматов:

+7<код><номер>

8<код><номер>

<номер>

где <номер> — это семь цифр, а <код> — это три цифры или три цифры в круглых скобках. Если код не указан, то считается, что он равен 495. Кроме того, в записи телефонного номера может стоять знак “-” между любыми двумя цифрами (см. пример).

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

Два телефонных номера совпадают, если у них равны коды и равны номера. Например, +7(916)0123456 и 89160123456 — это один и тот же номер.

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

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

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

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

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

Примеры
Входные данные
8(495)430-23-97
+7-4-9-5-43-023-97
4-3-0-2-3-9-7
8-495-430
Выходные данные
YES
YES
NO
Страница: << 1 2 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест