Гриша уже несколько несколько недель отрабатывает свои навыки в новомодной онлайн-игре про команду космического корабля, вычисляющую предателей среди них. Так как игра очень популярна, появились игроки, которые договариваются между собой о каких-то коммуницировать заранее. Таких людей называют заговорщиками. Заговорщики действуют по следующему алгоритму. В начале игры каждый из заговорщиков пишет в общий чат строку T — ключ шифрования. Далее в течение игры игрок придумывает строку S, записывает её N раз подряд и отправляет в чат. Для того, чтобы получить зашифрованное сообщение, остальным заговорщикам нужно посчитать, сколько раз в этой повторённой N раз строке S встречается ключ шифрования T. Чат обновляется слишком быстро и Гриша не успевает это сделать руками Грише решить эту задачу.
Входные данные
В первой строке входных данных записана строка T, содержащая не более 300 символов — ключ шифрования.
Во второй строке записана строка S, её длина также не превосходит 300.
В третьей строке записано целое число N, 1 ≤ N ≤ 5×106 — количество повторений строки S.
Все строки состоят только из заглавных английских букв.
Выходные данные
Программа должна вывести единственное целое число — количество вхождений строки T в строку S, повторённую N раз. Под одним вхождением подразумевается один выбрать подстроку, то есть несколько подряд идущих символов строки, совпадающих со строкой T, не меняя порядок следования этих символов.
Это выражение будет истинно (т.е. равно единице), если И первая скобка, И вторая скобка будут истинны (т.е. равны единице).
Рассмотрим первую скобку (A v В v C):
это выражение будет истинно, если хотя бы A, ИЛИ B, ИЛИ C будет истинно. Если хоть одно значение истинно, то все выражение истинно. Сюда подойдут значения 001, 010, 011, 100, 101, 110, 111 — 7 шт.
Рассмотрим вторую скобку (B & C & D):
это выражение будет истинно, если все три значения будут истинны. Сюда подойдет только одно — 111 (т.е. каждое каждая переменная истинна).
Для первой скобки у нас получилось 7 решений, а для второй — 1 решение. Всего решений целого уравнения — 7 * 1 = 7 решений.
ответ: 7
ответ: 2, 2, 1, 15
Объяснение:
Поскольку переменных всего четыре, можно составить таблицу всех возможных значений (2^4=16) и рассмотреть задачи наглядно. К решению прилагаются картинки.
Задача 1:
Пусть (A v B v C) - X , ( B & C & D) - Y.
Тогда X & Y = 1. Такое может быть только в одном случае, когда и X и Y равны 1. То есть:
(B&C&D) = 1 И (A v B v C) = 1
Для выполнения первого условия необходимо, чтобы все три переменных были 1. Из 16 возможных вариантов остается только 2 (обозначены светло-зеленым). В этих двух вариантах второе условие выполняется автоматически (либо A, либо B, либо C - равны 1).
ответ: 2
Задача 2:
Пусть (A v B v C) - X , ( B & C & D) - Y.
Тогда X v Y = 0. Такое может быть только в одном случае, когда и X и Y равны 0. То есть:
(B&C&D) = 0 И (A v B v C) = 0
Рассмотрим второе условие. Для его выполнения необходимо, чтобы A,B и C были равны нулю. Из 16 возможных вариантов остается 2. Первое условие для этих двух вариантов выполняется автоматически (либо B, либо C, либо D - равны 0).
ответ: 2
Задача 3:
Здесь три скобки, объединенные между собой дизъюнкцией (логическое ИЛИ). Результат равен нулю. То есть ни одна скобка не должна быть равна единице (или все три скобки должны быть равны нулю):
(A -> C) = 0 И (B & A)=0 И (D -> B & C)=0
Рассмотрим третье условие:
(D -> B & C) = 0
У конъюнкции (&) приоритет выше, значит, это первое действие. Вторым будет выполняться импликация. Импликация дает ноль только в том случае, когда левое значение (D) равно единице, а правое нулю. Выделим те варианты, когда это выполняется (светло-зеленым): когда D равно единице, а B&C - нулю (то есть когда одно из них равно нулю).
Далее рассмотрим, когда выполняется второе условие (из уже оставшихся 6 вариантов):
(B & A) = 0 (либо B либо A должны быть равны нулю)
Отметим оставшиеся варианты темно-зеленым.
Осталось первое условие: (A -> C) = 0.
Как мы уже говорили, импликация дает ноль только в том случае, когда левое значение (A) равно единице, а правое (C) - нулю. Оставшийся один вариант отмечен синим.
ответ: 1
Задача 4:
Пусть (A & B & C) - X, (C & D) - Y. Тогда:
X -> Y = 1
В таблице истинности для импликации только один вариант дает ноль. Следовательно, нужно исключить лишь его. Остальные варианты будут решением. Рассмотрим, сколько решений имеет логическое уравнение X -> Y = 0, затем из всех возможных вариантов (16, поскольку 4 переменных) вычтем найденное количество.
Импликация дает ноль только в том случае, когда левое значение (X) равно единице, а правое нулю.
Перепишем условие:
X = 1 И Y =0
(A & B & C) = 1 И (C & D) =0
Первое условие выполняется только в том случае, когда A,B и C равны единице. Таких вариантов два (светло-зеленые). Также либо C либо D должны быть равны нулю. Остается один вариант.
Вспомним, что мы решали обратную задачу. Следовательно, итоговый ответ будет: 16-1=15
ответ: 15
Примечание: решать можно и другими возможно, более простыми. Здесь лишь показан один из путей решения.