Задача A. Перестановки с подстрокой ≡

Условие

Даны строки S и P, состоящие из малых латинских букв. Требуется определить сколько различных слов, составленных из букв строки S, содержат в себе подстроку P.

Например, если S = dcba, P = bc, то получится 11 строк: bc, abc, bca, dbc, bcd, adbc, dabc, abcd, dbca, bcad, bcda.

Формат входного файла

Формат выходного файла

Ограничения

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

dbca
bc

11

xyz
xx

0

Задача B. Барбара ≡

Условие

На некотором языке все слова записываются заглавными латинскими буквами, и состоят из слогов. Слогом называется непустая последовательность согласных, заканчивающаяся гласной. Все остальные последовательности букв словами этого языка не являются. Например, слово BARBARA состоит из трех слогов — BA, RBA и RA. Последовательности букв ААХ, Е, К, АНА словами не являются. Осмысленными считаются слова, в которых все согласные различны.

По данной последовательности из N заглавных латинских букв определить, является ли она осмысленным словом и, если да, то сколько различных слогов можно составить из букв этого слова. Например, из слова BARAKA можно составить 15 слогов — BA, KA, RA, BKA, KBA, BRA, RBA, KRA, RKA, BKRA, BRKA, RBKA, RKBA, KBRA, KRBA.

Формат входного файла

Формат выходного файла

Ограничения

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

BARAKA

15

Задача C. Код Грея ≡

Условие

Дана строка, состоящая из N символов 0 и 1. Требуется построить последовательность из всех возможных строк длиной N, состоящих из 0 и 1, такую что:

• первая строка последовательности — входная строка;
• каждая строка входит в последовательность один раз;
• соседние строки последовательности отличаются друг от друга ровно в одном символе.

Формат входного файла

Во входном файле содержится строка из символов 0 и 1

Формат выходного файла

Выходной файл должен содержать 2^N строк — искомую последовательность.

Ограничения

1 ≤ N ≤ 15

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

1

1
0

110

110
111
101
100
000
001
011
010

Задача D. Количество инверсий последовательнсти ≡

Условие

Пара элементов (A_i, A_j) последовательности A_N называется инверсией, если A_i > A_j и i < j.

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

Формат входного файла

В первой строке входного файла содержится число N — количество элементов последовательности

Последующие N целых чисел задают саму последовательность

Формат выходного файла

В выходном файле должно содержаться единственное число — количество инверсий входной последовательности.

Ограничения

2 ≤ N ≤ 10⁵

0 ≤ A_i ≤ 10⁹

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

7 1 2 5 9 13 16 20

0

9
1 1 2 3 8 6 1 9 9

5

Задача E. Кривосчетная машина ≡

Условие

При изучении темы "системы счисления" студенты ДВГУ решили, что алгоритм перевода чисел слишком сложен. Поэтому они разработали новую счетную машину, которая предствавляет числа только в собственной системе счисления. Перевод чесел из этой системы в десятичную осуществляется по следующему прстому правилу: первый разряд числа умножить на 1 + второй умножить на 2 + ... + N-й разряд умножить на N. При этом в каждый разряд числа может принимать значения от 0 до K.

К сожалению, студенты были отчислены раньше, чем успели разработать программу для обратного перевода — из десятичной системы в систему счисления, понятную новой машине. Теперь эта задача досталась вам.

Разряды числа должны быть выведены в "обратном" порядке (первым - младший разряд, последним - старший). С целью экономии памяти, отводимой под число, если десятичное число можно представить разными способами, то должно быть выведено кратчайшее (содержащее меньше всего разрядов) представление.

Формат входного файла

Формат выходного файла

Ограничения

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

16 5

5 4 1

20 11

10 5