Задача 5. Календарь на Альфе Центавра ≡

Условие

На планете в системе Альфы Центавра год состоит из m месяцев, пронумерованных от 1 до m, а каждый месяц из d дней, пронумерованных от 1 до d. В свою очередь, неделя у поселенцев на этой планете состоит из w дней, проиндексированных строчными английскими буквами, от "a" до w-й буквы английского алфавита.

Первый день первого месяца первого года соответствует букве "a".

Требуется определить, какой букве будет соответствовать i-й день j-го месяца k-го года.

Формат входных данных

Первая строка ввода содержит три целых числа d, m и w.

Вторая строка ввода содержит три целых числа i, j и k.

Формат выходных данных

Выведите одну строчную букву английского алфавита — какой букве соответствует i-й день j-го месяца k-го года.

Ограничения

1 ≤ d, m ≤ 100, 1 ≤ w ≤ 26

1 ≤ i ≤ d, 1 ≤ j ≤ m, 1 ≤ k ≤ 10⁹

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

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

Замечание

Обратите внимание, при решении этой задачи рекомендуется использовать 64-битные типы данных, например long long в C++, int64 в Паскале.

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

30 12 7
18 1 2021

b

Задача 6. Числа ≡

Условие

Аня любит, когда числа состоят из одинаковых цифр. Поэтому ей нравятся числа 777 или 5555, а вот число 1234 ей совсем не нравится.

Иногда у Ани бывает хорошее настроение, тогда ей по прежнему нравятся все числа, состоящие из одинаковых цифр, но также нравятся числа, в которых все цифры кроме одной одинаковые, как, например, в числе 77727.

У Ани есть число x. Аня хочет найти минимальное целое число y ≥ x, которое ей понравится.

Требуется написать программу, которая по заданному целому числу x и информации, хорошее ли настроение у Ани, находит минимальное целое число y ≥ x, которое нравится Ане.

Формат входных данных

Первая строка ввода содержит целое число x (обратите внимание, что число x не может быть сохранено в стандартном 32-битном типе данных, необходимо использовать 64-битный тип данных, например long long в C++, int64 в Паскале).

Вторая строка ввода содержит число k, равное 0 или 1. Значение k = 1 означает, что у Ани хорошее настроение, а значение k = 0 — что это не так.

Формат выходных данных

Следует вывести одно целое число y.

Должны выполняться следующие свойства:

• y ≥ x;
• если k = 0, то все цифры в десятичной записи числа y должны совпадать;
• если k = 1, то все цифры в десятичной записи числа y, кроме, может быть, одной, должны совпадать.

Ограничения

1 ≤ x ≤ 10¹⁷

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

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

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

700
0

777

700
1

700

Задача 7. Хорошие раскраски ≡

Условие

Назовем раскраску клеток таблицы n × m хорошей, если никакие четыре клетки, центры которых образуют вершины прямоугольника со сторонами, параллельными осям координат, не покрашены в один цвет.

Иначе говоря, для раскраски не должно быть такой четверки целых чисел x₁, x₂, y₁, y₂, что 1 ≤ x₁ < x₂ ≤ n, 1 ≤ y₁ < y₂ ≤ m, и клетки (x₁, y₁), (x₂, y₁), (x₁, y₂) и (x₂, y₂) покрашены в одинаковый цвет.

Требуется написать программу, которая по заданным целым числам n, m и c находит любую хорошую раскраску таблицы n × m в c цветов.

Формат входных данных

В первой строке записаны три целых числа n, m, c.

Гарантируется, что для заданных во входных данных значений существует хотя бы одна хорошая раскраска.

Формат выходных данных

Выведите n строк по m чисел в каждой.

В качестве j-го числа i-й строки выведите a_i,j — цвет клетки (i,j) (1 ≤ a_i,j ≤ c).

Если есть несколько хороших раскрасок, можно вывести любую из них.

Ограничения

2 ≤ n, m ≤ 10, 2 ≤ c ≤ 3

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

Кроме теста из примера в этой задаче 20 тестов, каждый независимо оценивается в 5 баллов. Среди этих тестов в пяти тестах c = 2 и в пятнадцати тестах c = 3.

Для каждого теста сообщается результат проверки на этом тесте.

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

2 2 2

1 2 
2 2 

Задача 8. A+B ≡

Условие

Рассмотрим a, b и c — целые неотрицательные числа, записанные в десятичной системе счисления. Пусть они имеют одинаковую длину n, при этом запись может начинаться с нуля. Числа записаны одно под другим, цифры расположены в три строки и n столбцов. Рассмотрим пример такой записи:

  01211
  12099
  23300
  

Требуется переставить столбцы в этой записи таким образом, чтобы выполнялось равенство a + b = c. В полученной записи ведущие нули уже запрещены. Сколько существует различных способов это сделать?

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

Поскольку ответ может быть довольно большим, требуется посчитать для него остаток по модулю 10⁹ + 7.

Формат входных данных

Во входных данных записаны целые неотрицательные числа a, b и c по одному в строке. Каждое число состоит из n десятичных цифр и может начинаться с нуля.

Формат выходных данных

Выведите количество подходящих перестановок столбцов по модулю 10⁹ + 7.

Ограничения

2 ≤ n ≤ 2 ⋅ 10⁵

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

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

Пояснения к примерам

В первом примере подходят все перестановки столбцов.

Во втором примере единственная подходящая перестановка — 10 + 20 = 30. 01 + 02 = 03 не считается из-за наличия ведущих нулей.

В третьем примере возможны варианты 10121 + 21909 = 32030 и 12101 + 20919 = 33020, причём каждый из них может быть получен двумя разными перестановками.

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

123
123
246

6

01
02
03

1

01211
12099
23300

4

121
214
999

0