Некоторый алгоритм шифрования устроен следующим образом.
Исходная строка разбивается на блоки по 36 символов. Если в конце остается часть, которой недостаточно для полного блока, то она не шифруется.
Шифрование происходит с помощью квадратного трафарета, в котором имеется 9 прорезей для записи символов.
Пример трафарета показан на рисунке.
Например, если в начале блока шло слово «Криптография», то его символы будут расположены вот так:
Символы из таблицы выписываются в порядке слева направо и сверху вниз - таким образом получается зашифрованный блок.
Затем трафарет возвращается в исходное положение и операция повторяется для остальных блоков.
Гарантируется, что трафарет корректен (то есть в процессе шифрования одного блока над каждой клеткой таблицы прорезь появляется ровно один раз).
Дана строка, состоящая из английских букв (заглавных и строчных) и пробелов. Также дан трафарет. Напишите программу шифрования данной строки по трафарету.
В первой строке находится исходный текст (одна непустая строка длинной не более 200 символов).
В следующих 6 строках описан трафарет в следующем формате: закрытая клетка обозначается символом ‘#’ (решетка), прорезь обозначается символом ‘.’ (точка).
Например, трафарет из условия задачи будет вводиться так:
.##### #..### ###.## .###.# ###### #..#.#
Выведите строку, полученную в результате шифрования исходного текста.
ABCDE .##### #..### ###.## .###.# ##### #..#.#
ABCDE
Дано дерево из n вершин. У каждой вершины есть цвет. Нужно обработать q запросов ( v i , c i ): найти расстояние от v i до ближайшей к v i вершины цвета c i . Расстоянием между вершинами называется минимальное количество рёбер в пути между ними.
На первой строке число n ( 1 ≤ n ≤ 10 5 ), следующая строка содержит числа p 1 , p 2 , ..., p n - 1 . 0 ≤ p i < i . p i – отец вершины i в дереве. Далее строка с числами a 0 , a 1 , ..., a n - 1 . 0 ≤ a i < n . a i – цвет вершины i . Далее строка с числом q ( 1 ≤ q ≤ 10 5 ). Следующие q строк содержат запросы v iq i ( 0 ≤ v i < n , 0 ≤ c i < n ).
Для каждого запроса выведите одно число – расстояние до ближайшей вершины нужного цвета, или - 1 , если в дереве нет вершин такого цвета.
5 0 1 1 3 1 2 3 2 1 9 0 1 0 2 0 3 1 0 2 1 2 2 3 3 3 1 4 2
0 1 2 -1 2 1 2 1 1
В супермаркете «На троечку» часто происходят распродажи товаров, срок годности которых подходит к концу. Каждый товар привозят в магазин в определенное время, а через некоторое его вывозят из магазина, в связи с окончанием срока годности. Более формально, каждый товар имеет стоимость c i , время его завоза в магазин a i и время его вывоза из магазина b i .
У Иннокентия есть хитрый план похода в магазин. Даже несколько. Каждый план похода в магазин выглядит так: Иннокентий выбирает какое-то время, когда он появится в магазине m j , время s j , которое он проведет в магазине среди огромных стеллажей товаров, и сумму денег k j , которую он рассчитывает потратить. Для каждого плана он хочет узнать, сможет ли он осуществить его, т. е. верно ли, что он сможет во время своего пребывания в магазине купить несколько товаров суммарной стоимостью ровно k j , при этом все выбранные товары должны быть в магазине на протяжении всего пребывания Иннокентия в магазине.
Помогите Иннокентию определить, какие из его планов можно выполнить.
В первой строке входных данных содержится число N — общее количество товаров в магазине ( 1 ≤ N ≤ 500 ). Далее содержатся описания товаров, каждый товар описывается тремя целыми числами c i , a i , b i , обозначающими стоимость товара, время его завоза и время его вывоза из магазина ( 1 ≤ c i ≤ 1 000 , 1 ≤ a i < b i ≤ 10 9 ).
Далее содержится число M — количество планов Иннокентия ( 1 ≤ M ≤ 500 000 ). Каждый план описывается тремя целыми числами m j , k j , s j , обозначающими время прихода Иннокентия в магазин, сумму денег, которую он готов потратить в этом плане и длительность его пребывания в магазине ( 1 ≤ m j ≤ 10 9 , 1 ≤ k j ≤ 100 000 , 0 ≤ s j ≤ 10 9 ).
Помните, что это только планы, т. е. ситуация в магазине не меняется вне зависимости от того, может ли Иннокентий осуществить план или нет.
Для каждого плана в отдельной строке выведите « YES », если Иннокентий может его осуществить, и « NO » в противном случае.
Тесты к этой задаче состоят из четырех групп.
- Тест 1. Тест из условия, оценивается в ноль баллов.
- Тесты 2–7. В тестах этой группы M ≤ 10 , a i , b i , m j , s j ≤ 20 000 , k j ≤ 1 000 . Эта группа оценивается в 30 баллов.
- Тесты 8–11. В тестах этой группы N ≤ 200 , M ≤ 200 , k j ≤ 5 000 . Эта группа оценивается в 30 баллов.
- Тесты 12–23. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 40 баллов.
Баллы за каждую группу тестов ставятся только при прохождении всех тестов группы.
5 6 2 7 5 4 9 1 2 4 2 5 8 1 3 9 5 2 7 1 2 7 2 3 2 0 5 7 2 4 1 5
YES NO YES YES NO
Назовём неподвижной точкой перестановки такой индекс i , что a i = i . Посчитайте число перестановок длины n , в которых нет неподвижных точек. Так как это число может быть воистину огромным, выведите его по модулю 10 9 + 7 .
В единственной строке входного файла задано целое число n ( 1 ≤ n ≤ 10 7 ) — количество элементов в перестановке.
В единственной строке выведите количество перестановок из n элементов без неподвижных точек, взятое по модулю 10 9 + 7 .
n ≤ 10 — 30 баллов.
n ≤ 5000 — 40 баллов.
n ≤ 10 6 — 20 баллов.
n ≤ 10 5 — 10 баллов.
3
2
Вася открыл для себя классическую игру «Bomberman», действующий лицом которой является Бомбермен. Этот персонаж передвигается по игровому полю, представляющему собой прямоугольник из N строк и M столбцов. Каждая клетка поля либо свободна для прохода, либо занята стеной. В одной из клеток находится бонус, к которому необходимо добраться Бомбермену. Для этого у него есть ровно 3 бомбы. За ход Бомбермен может сдвинуться в соседнюю клетку, если она свободна, или взорвать стену, расположенную в ней, использовав одну бомбу.
В последнем случае клетка становится проходимой и впоследствии Бомбермен может на нее встать. Вася хочет определить, за какое минимальное количество ходов Бомбермен сможет добраться до бонуса, или же узнать, что это сделать невозможно, тогда Вася может спокойно удалить «Bomberman» - а и вернуться к старой доброй Дотке.Соседними являются клетки, имеющие общую сторону. Бомбермен не может выходить за границы поля.
В первой строке содержатся два числа N и M — количество строк и столбцов поля соответственно ( 1 ≤ N , M ≤ 20 ). Каждая из следующих N строк содержит ровно M символов, описывающих поле. Свободные клетки обозначены символом «.» (ASCII код 46), занятые—символом «W» (ASCII код 87), бонус—символом «*» (ASCII код 42), Бомбермен—символом «B» (ASCII код 66). Гарантируется, что на поле находится ровно один бонус.
Выведите одно число—минимальное количество ходов, необходимое для того, чтобы добраться до бонуса, либо −1, если добраться до бонуса невозможно.
В первом примере необходимо взорвать стену во второй строке в первом столбце и пройти Бомберменом вниз, а затем вправо. Во втором примере необходимо взорвать минимум 4 стены, чтобы добраться до бонуса, поэтому ответ −1.
5 6 B..... WWWWW. ...... .WWWWW .....*
10
9 12 WWWWWWWWWWWW WW...B..WWWW WW.WWWW.WWWW WW.WWWW...WW WW.WWWWWWWWW WWWWWWWWWWWW WWWWWWWWWWWW WWWW*WWWWWWW WWWWWWWWWWWW
-1