Задача A. Average thrice ≡

Условие

Артём загадал три целых числа и сообщил Евгению их попарные средние арифметические. Евгений без проблем восстановил исходные числа. Попробуйте и вы!

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

Входные данные содержат три числа: x, y и z. Числа либо целые, либо дробные с дробной частью 0.5. Хотя бы одно из чисел отлично от нуля.

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

Выведите в порядке неубывания три исходных целых числа (входные данные таковы, что найденные числа окажутся целыми).

Ограничения

 − 10⁸ ≤ x, y, z ≤ 10⁸

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

В примере x = 1.5, y = 2 и z = 3.5. Это попарные средние арифметические для чисел a = 0, b = 3 и c = 4. В самом деле:

a + b2 = 0 + 32 = 1.5 = x;

a + c2 = 0 + 42 = 2 = y;

b + c2 = 3 + 42 = 3.5 = z.

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

1.5 2 3.5

0 3 4

Задача B. Bread crusts ≡

Условие

В харчевне "Три пескаря" за a золотых монет можно получить три корочки хлеба и сдачу, а за b золотых монет — пять корочек хлеба и сдачу. Сколько корочек хлеба можно гарантированно получить за c золотых монет?

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

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

Три строки входного файла содержат три натуральных числа a, b и c. Входные данные таковы, что ответ существует.

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

Выведите одно целое число — ответ на вопрос задачи.

Ограничения

1 ≤ a < b ≤ 10⁹

1 ≤ c ≤ 10⁹

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

В примере за 8 золотых монет можно получить три корочки хлеба и сдачу, а за 13 золотых монет — пять корочек хлеба и сдачу.

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

8
13
100

38

Задача C. Current year problem ≡

Условие

Найдите наименьшее положительное целое число, которое делится на n и начинается с цифр 2021 в десятичной записи.

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

Входные данные содержат единственное целое число n — делитель искомого числа.

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

Выведите одно натуральное число — ответ на задачу.

Ограничения

1 ≤ n ≤ 10¹²

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

2022

20211912

Задача D. Dynamic Cinderella ≡

Условие

В сказке братьев Гримм одним из испытаний для Золушки был эпизод, когда злая мачеха рассыпала крупы в кучу на пол и приказала перебрать их, разложив по тарелочкам. Крупы варьируются в зависимости от версии. В одной сказке Золушка перебирала просо и мак. В другой она раскладывала бобы и чечевицу. В третьей отделяла ячмень от овса. Были и горох с рисом, и гречка с пшеном, и мешки с красной и белой фасолью. Какой из вариантов правдивый — неизвестно, поэтому в этой задаче мачеха сформировала кучу из десятичных цифр и потребовала, чтобы Золушка посчитала количество каждой цифры в куче.

Всего в куче n уровней, на самом верхнем — единственная цифра d, в каждом следующем уровне на одну цифру больше, чем на уровне выше. Для удобства представим кучу (в ней n = 4 и d = 8) так, как указано на рисунке.

Куча цифр сформирована мачехой по определенным правилам. Самое первое число на уровнях, начиная со второго, равно первому числу на уровне выше, увеличенному на 1 и взятому по модулю 10. Например, первое число на втором уровне равно (8 + 1) % 10 = 9. Первое число на третьем уровне равно (9 + 1) % 10 = 0, и так далее.

Остальные цифры в куче формируются следующим образом: берется два числа — левее в том же уровне и на уровне выше над только что взятым числом, складываются и результат берется по модулю 10. Например, второе число на втором уровне равно (9 + 8) % 10 = 7.

Если бы Золушка знала, что такое динамическое программирование, то правила заполнения кучи выглядели бы так:

DP[1, 1] = d;
DP[i, 1] = (DP[i - 1, 1] + 1) % 10;
DP[i, j] = (DP[i, j - 1] + DP[i - 1, j - 1]) % 10.

Ходят слухи, что мачеха способна за секунду определить количество всех цифр в куче и проверить правильность работы Золушки. Вам придется взять на себя роль доброй феи и помочь девушке выполнить это нелегкое задание.

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

Входные данные содержат два целых числа: n и d.

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

Выведите десять чисел — количество цифр от 0 до 9 в куче.

Ограничения

2 ≤ n ≤ 10⁵

1 ≤ d ≤ 9

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

4 8

2 2 0 0 0 0 2 1 1 2

Задача E. Enclosed by curves ≡

Условие

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

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

X_i(t) = AX_i ⋅ t³ + BX_i ⋅ t² + CX_i ⋅ t + DX_i;

Y_i(t) = AY_i ⋅ t³ + BY_i ⋅ t² + CY_i ⋅ t + DY_i,

где t — скалярный параметр, изменяющийся в диапазоне [0, 1].

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

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

В начале входных данных содержится целое N, за которым следует 8 × N вещественных чисел, задающих коэффициенты соответствующих сплайнов

AX_i, BX_i, CX_i, DX_i,
AY_i, BY_i, CY_i, DY_i.

Далее записано целое число M, за которым следует 2 × M вещественных чисел, задающих координаты точек (X_j, Y_j).

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

Выходные данные должны содержать последовательность из M целых чисел (ответов на каждый запрос):
1 — если соответствующая точка лежит внутри контура,
0 — если лежит снаружи.

Ограничения

В пределах заданной точности контур непрерывен и не имеет самопересечений.

Расстояние от каждой из точек до границы контура не меньше 10^− 5.

Контур целиком лежит внутри прямоугольной области [ − 10, 10] × [ − 10, 10].

1 ≤ N ≤ 1000, 1 ≤ M ≤ 10⁵.

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

6
 3.53200 -4.87400  1.66600 -0.46000
 0.67600 -0.70800  0.26600 -0.20200
 1.74000 -2.86600  0.84800 -0.13600
 1.29000 -1.88200  0.61200  0.03200
-1.40400  2.10600 -0.51200 -0.41400
-0.17200  0.25800  0.10600  0.05200
-1.40000  1.57000  0.00000 -0.22400
-0.22200  0.01600 -0.00000  0.24400
-3.42400  4.60600 -1.06000 -0.05400
 0.11600  0.22800 -0.63400  0.03800
 0.60200 -0.07000 -1.06000  0.06800
 1.77400 -2.52800  0.80400 -0.25200

8
-0.23000 -0.27000
-0.37094 -0.10086
 0.00000  0.15040
-0.39010  0.20360
-0.31067  0.04029
-0.20000 -0.08960
 0.03000 -0.05071
-0.18603  0.17014

0
1
1
0
1
1
0
1

Задача F. Fine segments ≡

Условие

Юному программисту Илье подарили на день рождения последовательность чисел a_i длиной n. Илья решил выделить из этой последовательности хорошие отрезки. Хорошим отрезком называется последовательность подряд идущих элементов a_i, содержащая внутри себя элемент, равный сумме своего первого и последнего элементов. Например, последовательность [1, 2, 5, 4] является хорошей, так как сумма самого левого и самого правого элементов равна 5, а число 5 есть в данной последовательности; последовательность [1, 2, 3, 4] не является хорошей, так как сумма самого левого и самого правого элементов дает нам 5, а числа 5 нет в данной последовательности. Требуется программу, которая посчитает количество хороших отрезков в данной последовательности.

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

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

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

Выведите единственное целое число — количество хороших отрезков в последовательности.

Ограничения

1 ≤ n ≤ 10³

1 ≤ a_i ≤ 10⁵

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

В первом примере один хорошой отрезок: [3, 7, 5, 4].

Во втором примере два хороших отрезка: [1, 5, 4] и [1, 5, 4, 7, 6].

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

5
3 7 5 4 8

1

5
1 5 4 7 6

2

Задача G. Generator of palindromes ≡

Условие

Палиндромом называется строка символов, которая одинаково читается в обоих направлениях (слева направо и справа налево).

Пусть имеется произвольная строка S. Рассмотрим лексикографически упорядоченный список всех различных палиндромов, которые могут быть получены путём удаления и перестановки символов в исходной строке.

Из указанного списка требуется исключить палиндромы, лексикографически меньшие заданной строки T.
Если после этого длина списка всё ещё больше n, лишние палиндромы с конца также следует удалить.

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

Первые две строки входных данных содержат строки S и T, состоящие из цифр и строчных букв латинского алфавита.
За ними следует целое число n.

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

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

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

Ограничения

0 < |T| ≤ |S| ≤ 100,

0 < n ≤ 2 ⋅ 10⁴

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

abcbac
aca
15

aca
acbbca
acbca
acca
b
baab
bab
bacab
baccab
bb
bcaacb
bcacb
bcb
bccb
c

123243
21a
50

22
23132
232
2332
23432
242
3
313
32123
3223
323
32423
33
343
4

Задача H. Hide the dot ≡

Условие

Мы уже привыкли к продвинутым алгоритмам автоматической обработки изображений. С их помощью нам ничего не стоит убрать фон с фотографии, замазать морщины и даже сделать совместный коллаж с любой знаменитостью. Но задумывались ли Вы, как работают такие программы? Сложно ли их написать? Вам предлагается простая задача: найти и убрать единственный лишний символ из ASCII-рисунка.

На рисунке размером n × m расположено изображение пустого прямоугольника толщиной в один пиксель и одного лишнего пискеля, обозначаемых символами "#" (ASCII-код 35). Прямоугольник имеет длину и ширину не менее трех пикселей, а его стороны параллельны границам изображения. Фон рисунка заполнен символами "." (ASCII-код 46).

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

Первая строка входных данных содержит два целых числа: n и m. В следующих n строках расположены строки длиной m, состоящие из символов "#" и ".".

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

Выведите n строк по m символов — то же самое изображение с удалённым лишним пикселем.

Ограничения

3 ≤ n, m ≤ 100

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

5 5
..#..
.####
.#..#
.####
.....

.....
.####
.#..#
.####
.....

3 3
###
###
###

###
#.#
###

7 8
........
.#####..
.#...#..
.#...#..
.#####..
........
...#....

........
.#####..
.#...#..
.#...#..
.#####..
........
........

Задача I. Interactive and bidirectional ≡

Условие

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

Жюри загадало секретное строку бит X длиной N.

Ваша программа может делать запросы вида "? M L R". Ответ на запрос — результат сравнений в порядке слева-направо и справа-налево двух строк по M бит: начинающейся с позиции L и начинающейся с позиции R. Биты нумеруются справа налево.

Требуется определить значение X, сделав не более ⌈ N + 12⌉ запросов.

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

В первой строке входных данных записано целое число N — количество бит в X.

Протокол взаимодействия

Чтобы сделать запрос, ваша программа должна вывести "? M L R", где M — количество бит для сравнения, а L и R — позиции для сравнения. На каждый запрос программа жюри ответит двумя символами — результат сравнений слева-направо и справа-налево. Возможные результаты сравнения:  < ,  >  и  = . Запросы должны быть такими, что не будет происходить обращения к битам за пределами X.

Когда ваша программа определила X, она должна вывести "! X", где X — строка бит X. После вывода ответа программа должна завершиться.

Если ваша программа сделает недопустимый запрос, то она получит вердикт "Presentation error". Если ваша программа превысит допустимое количество запросов, то она получит вердикт "Wrong answer".

Каждый запрос и вывод окончательного результата должен быть одиночной строкой заканчивающейся одиночным переводом строки (\n). Буфер вывода необходимо сбрасывать после каждой строки:

Ограничения

1 ≤ N ≤ 60

0 < X < 2^N

1 ≤ M ≤ N

0 ≤ L, R < N

L + M, R + M ≤ N

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

В первом примере загадано число 01101. В первом запросе сравнивались 101 с 011 и 101 с 110, поэтому ответ  >  < .

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

5

><

<<

==

? 3 0 2

? 1 1 3

? 2 3 0

! 01101

3

==

? 2 0 1

! 111

Задача J. Juxtaposition joke ≡

Условие

На доске в кабинете математики было записано натуральное число n. Нигде в записи числа не содержалось нулей. Проходящий мимо Тимофей из озорства k раз поменял местами две соседние цифры. Какое наибольшее число после этого могло получиться?

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

Входные данные содержат целые числа n и k, по одному с строке.

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

Выведите одно целое число — ответ на вопрос задачи.

Ограничения

11 ≤ n ≤ 10²⁵⁰

k ≤ 10⁹

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

В первом примере дано n = 97 и одна перестановка, дающая результат 79.

Во втором примере оптимально переместить тройку на первое место и получить 312.

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

97
1

79

123
2

312

5833917
9

9875331

Задача K. Kode work? ≡

Условие

Группа студентов решила создать стартап для замены QR-кодов на новую улучшенную систему. Они решили представлять двоичные данные как строку из шаблонов цифр 0 и 1. Также на рисунке изображено представление двоичной строки 1001.

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

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

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

Входные данные содержат в первой строке одно целое число n — ширину изображения. В следующих трёх строках расположено само изображение. Каждый его символ равен либо '#' (ASCII 35), либо символ '.' (ASCII 46).

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

Выведите одно целое число — наименьшую возможную ошибку распознавания.

Ограничения

2 ≤ n ≤ 100000

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

5
.#..#
##.##
.#..#

0

14
.#.#.#.##.#..#
##.#.#.##.#.##
.#####.####..#

14

Задача L. Learning distribution ≡

Условие

Два студента готовятся к экзамену, во время которого им будет предложен один из n вопросов (нумерация от 1 до n). Они решили разделить между собой вопросы для подготовки следующим образом:

Первый студент выбирает одно число a от 1 до n и учит a вопросов с номерами a, a + 1, a + 2, ... , a + a − 1. Если какой-то из номеров превышает n, нумерация продолжается с 1. Например, если n = 5 и a = 1, то первый студент будет учить только вопрос с номером 1, при a = 2 он будет учить вопросы с номерами 2 и 3, при a = 4 — вопросы с номерами 4, 5, 1 и 2, при a = 5 — все вопросы.

Второй студент тоже выбирает одно число b ≠ a от 1 до n и учит b вопросов с номерами b, b + 1, b + 2, ... , b + b − 1. Аналогично, если какой-то из номеров превышает n, счет продолжается с номер 1.

По известному количеству билетов n определите, сколько существует различных способов выбрать a и b, так что каждый вопросы экзамена будет подготовлен хотя бы одним из студентов.

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

Входные данные содержат целое число n.

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

Выведите целое число — количество способов выбрать a и b.

Ограничения

2 ≤ n ≤ 10⁶

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

В первом примере на экзамене три билета. Независимо от выбора a и b, студенты подготовятся к ответам на все вопросы.

Во втором примере на экзамене четыре билета. Если один из студентов выберет a = 1, а другой b = 2, ни один из них не подготовит ответ на четвертый вопрос.

Если один из студентов выберет a = 1, а другой b = 3, ни один из них не подготовит ответ на второй вопрос.

В оставшихся случаях все вопросы будут выучены.

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

3

6

4

8