Задача Сумма двух чисел ≡

Условие

Вывести сумму двух заданных чисел.

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

На первой строке входного файла находятся два целых числа a и b ( − 10⁹ ≤ a, b ≤ 10⁹).

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

Вашей программе требуется вывести единственное число — сумму заданных чисел a + b.

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

2 3

5

17 -18

-1

Задача 1. K-й через min и max ≡

Условие

Найти выражение, использующее функции от двух аргументов min и max, а также N переменных x₁, x₂, ..., x_N, значение которого при подстановке любых чисел вместо переменных равнялось бы K-му по порядку числу.

Например, если N = 3, x₁ =  − 2, x₂ = 5, x₃ = 1, то первое по порядку число — это  − 2, второе по порядку — 1, третье — 5.

Если ответов несколько, вывести любой из них.

Примечание. Тесты к задаче можно скачать здесь. В качестве решения принимается либо программа, либо ZIP-архив с файлами 01.out, 02.out, и т.д., содержащими ответы к каждому из тестов.

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

Входной файл содержит целые числа N K.

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

Требуется вывести в выходной файл одну строку. Строка может содержать маленькие латинские буквы, цифры, запятые, круглые скобки и пробелы.

Длина строки должна быть не более 2000 символов.

Ограничения

2 ≤ N ≤ 7, 1 ≤ K ≤ N

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

2 1

min(x1,x2)

3 3

max( x2, max(x1, x3))

Задача A1. Установить бит в числе ≡

Условие

Требуется написать программу, которая устанавливает i-й бит в целом числе n с помощью битовых операций.

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

Входные данные содержат целое число n и номер бита i. Нумерация битов начинается с нуля от младшего к старшему.

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

Выходные данные должны содержать целое число n с установленным битом под номером i.

Ограничения

 − 2³¹ ≤ n ≤ 2³¹ − 1

0 ≤ i ≤ 31

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

2 0

3

-2 0

-1

Задача A2. Битовый диктатор ≡

Условие

Вася диктует формулу словами, а вам надо её запрограммировать для чисел a, b и с. Все действия надо сделать с помощью битовых операций.

Возьми число a, подели нацело его на 4 (2²), далее умножь на 16 (2⁴), после этого сделай побитовое "ИСКЛЮЧАЮЩЕ ИЛИ" с числом b, получившийся результат умножь на 2 (2¹), и сделай побитовое "ИЛИ" с числом c. Ответом будет побитовое "И" уже получившегося результата и числа 1073741823.

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

Первая строка входного файла содержит три числа a, b и c.

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

Входной файл должен содержать одно число — значение результат формулы.

Ограничения

0 ≤ a, b, c ≤ 2 ⋅ 10⁵

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

0 10 25

29

123 123 123

895

Задача A3. Двоичный порядок float ≡

Условие

Требуется написать программу, которая считывает вещественное число в переменную типа float и выводит его двоичный порядок по стандарту IEEE-754.

Для поиска порядка необходимо использовать битовые операции.

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

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

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

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

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

2.0

1

0.5

-1

Задача A4. K-й бит в числе ≡

Условие

Дано целое неотрицательное число x, требуется вернуть значение k-го бита числа x, то есть k-й разряд двоичного представления числа x. Разряды нумеруются с 0 начиная с младшего. Считается что число содержит неограниченное количество лидирующих нулей.

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

Первая строка входного файла содержит два числа x, k.

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

Входной файл должен содержать одно число  — значение k-го бита числа x.

Ограничения

0 ≤ x ≤ 2 ⋅ 10⁹

0 ≤ k ≤ 300

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

0 10

0

123 0

1

12345 100

0

Задача A5. В ожидании Нового года ≡

Условие

31 декабря. Марфа Геннадьевна и Глафира Сергеевна уже приготовили новогодний ужин, и теперь они с нетерпением ждут Нового года.

Каждые 5-10 минут они смотрят на часы и вычисляют, сколько часов и минут осталось до Нового года. При этом на вычисление у них уходит много времени.

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

Число секунд в текущем времени принять равным 0.

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

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

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

Требуется вывести в выходной файл, сколько времени осталось до Нового года — часы и минуты.

Ограничения

Часы от 0 до 23. Минуты от 0 до 59.

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

12 0

12 0

23 59

0 1

22 25

1 35

Задача B1. Среднее арифметическое ≡

Условие

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

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

Входные данные содержат число n, за которым следует n положительных вещественных чисел.

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

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

Ограничения

1 < n < 10⁵

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

3
1 3 5

3

Задача B2. НОД и числа Фибоначчи (исправленная) ≡

Условие

k-тым числом Фибоначчи называется k-тый член последовательности F_k = F_k − 1 + F_k − 2 , F₀ = 0 , F₁ = 1

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

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

В выходном файле должно содержаться единственное число — наибольший общий делитель F_n и F_k.

Ограничения

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

1 2

1

6 9

2

Задача B3. Заплыв ≡

Условие

Оксана любит плавать и готовится к заплыву через Амурский залив. Для подготовки она каждый день приходит в бассейн и проводит там несколько часов, переплывая от одного края бассейна до другого. Длина бассейна, где занимается Оксана — N метров. Она успевает пересечь его за M секунд, и ещё K секунд тратит на разворот. Сколько метров Оксана успеет проплыть за L минут?

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

Первая строка входного файла содержит четыре натуральных числа: N M K L.

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

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

Ограничения

1 ≤ N, M, K, L ≤ 1000

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

25 76 2 45

865

50 50 1 60

3530

Задача B4. Сложение массива чисел ≡

Условие

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

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

Ограничения

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

3
1 2 3

6

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

Условие

Пара элементов (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

Задача B6. Фонари ≡

Условие

На улице длиной в 100 метров установлено N фонарей высотой y₁, y₂, …, y_N метров на расстоянии x₁, x₂, … x_N метров от начала улицы. Форма отражателей такова, что свет каждого фонаря распространяется в пределах конуса с углом при вершине 90°.

Рекомендуется рассмотреть частичные решения:

1. N ≤ 2

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

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

Ограничения

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

3
1 1 50 10 51 10

2

Задача C1. Две пешки и слон ≡

Условие

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

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

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

Входной файл содержит числа x₁ y₁ x₂ y₂ — координаты первой и второй пешек.

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

Если задача имеет решение, то выходной файл должен содержать два числа — координаты слона. Если решений несколько, вывести любое из них. Если задача не имеет решения, вывести единственное число 0.

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

3 6 7 5

0

3 4 5 6

4 5

4 5 5 6

0

Задача C2. Точка в углу ≡

Условие

Прямоугольник со сторонами, параллельными осям координат, задан координатами противоположных вершин (x₁, y₁) и (x₂, y₂).

Будем считать, что точка (x, y) внутри прямоугольника находится в углу, если расстояние от точки до одной из вершин прямоугольника строго меньше, чем до центра прямоугольника.

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

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

Входной файл содержит целые числа x₁ y₁ x₂ y₂ x y — координаты вершин прямоугольника и точки.

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

Выходной файл должен содержать единственную строку CORNER, если точка находится в углу, или CENTER в противном случае.

Ограничения

 − 10⁴ ≤ x₁,y₁,x₂,y₂ ≤ 10⁴

min(x₁, x₂) ≤ x ≤ max(x₁, x₂)

min(y₁, y₂) ≤ y ≤ max(y₁, y₂)

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

100 200 300 400 290 210

CORNER

100 200 300 400 200 300

CENTER

Задача C3. Подсчёт баллов за задачу ≡

Условие

В одной из задач итоговой олимпиады летней школы по информатике имеется N тестов. i-ый тест оценивается в a_i баллов. Итоговый балл за задачу — сумма баллов за каждый тест, ответ на который является правильным.

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

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

В первой содержится единственное число N.

Во второй содержатся N чисел — на i-ом месте находятся баллы за i-ый тест.

В файла содержаться N символов '+' (ASCII 43) или '-' (ASCII 45). Если ответ на i-ый тест верный, то i-ый символ — '+', в противном случае — '-'

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

Выходной файл должен содержать единственное число — количество баллов за задачу.

Ограничения

1 ≤ N ≤ 100

1 ≤ a_i ≤ 100

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

5
1 2 3 5 10 
+-++-

9

6
1 1 3 5 10 25
+-+--+

29

Задача C4. Фибоначчи ≡

Условие

Необходимо вывести N первых чисел Фибоначчи, начиная с 0.

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

Входной файл содержит одно целое неотрицательное число N.

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

Выходной файл должен содержать N первых чисел последовательности Фибоначчи.

Ограничения

0 ≤ N ≤ 94

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

2

0 1

Задача D1. НОД и НОК ≡

Условие

Необходимо вычислить НОД и НОК для пары целых положительных чисел a и b.

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

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

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

Выходной файл должен содержать НОД и НОК пары чисел.

Ограничения

1 ≤ a,b ≤ 10⁶

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

2 3

1 6

24 28

4 168

Задача D2. Простые числа ≡

Условие

Необходимо вывести N простых чисел в порядке их возрастания.

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

Входной файл содержит одно целое неотрицательное число N.

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

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

Ограничения

0 ≤ N ≤ 1000

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

1

2

3

2 3 5

Задача D3. Квадратное уравнение ≡

Условие

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

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

Входной файл содержит три вещественных числа - коэффициенты квадратного уравнения с точностью до четырех знаков после запятой.

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

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

Ограничения

0 ≤ a, b, c ≤ 1000

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

3 5 2

-0.6667 -1.0000

0 7.245 -5.222

0.7208 0.7208

Задача E1. Забор по фен-шую ≡

Условие

Марфа Геннадьевна попросила внука построить новый забор вдоль огорода. Внук выполнил просьбу бабушки и построил забор из N досок, в котором доска с номером i имела высоту a_i сантиметров.

Марфа Геннадьевна недавно прочитала книгу, в которой было написано, что гармоничным является забор, состоящий из чередующихся высоких и низких деревянных досок, то есть должно выполняться либо условие a₁ < a₂ > a₃ < a₄ > …, либо условие a₁ > a₂ < a₃ > a₄ < ….

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

Напишите программу, которая по указанным длинам досок a_i определяет новый набор длин b_i, в котором:

1. a_i ≤ b_i,
2. либо b₁ < b₂ > b₃ < b₄ > …, либо b₁ > b₂ < b₃ > b₄ < …
3. сумма b_i минимальна.

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

Входной файл содержит целое число N за которым следует N чисел a_i — длины досок.

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

Входной файл должен содержать N целых чисел b_i — новые длины досок. Если существует несколько решений, выведите любое из них.

Ограничения

1 ≤ N ≤ 100; 1 ≤ a_i ≤ 100

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

1
20

20

4
11 10 11 15

11 12 11 15

Задача E2. Количество каждого числа ≡

Условие

Вася записал в файл input.txt N чисел. Когда Петя открыл этот файл, он решил посчитать, сколько раз в файле записано каждое число.

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

Заметим, что это позволяет выполнить сортировку массива чисел по возрастанию при помощи простого подсчёта.

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

Входной файл содержит целое число N, за которым следуют N целых чисел a_i.

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

Выходной файл должен содержать пары чисел: число из входного файла и количество раз, сколько оно встретилось в файле.

Пары должны быть выведены в порядке возрастания встречающихся во входном файле чисел.

Ограничения

1 ≤ N ≤ 1000000

 − 1000 ≤ a_i ≤ 1000

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

4
1 2 1 0

0 1
1 2
2 1

7
9 1 3 2 3 -2 7

-2 1
1 1
2 1
3 2
7 1
9 1

Задача E3. Куб со спицами ≡

Условие

Возьмём N³ одинаковых кубиков. Раскрасим кубики в N цветов так, чтобы в каждый цвет было раскрашено ровно N² кубиков. Сложим из всех кубиков один большой куб. Начнём протыкать этот куб спицами параллельно его рёбрам. Любая спица пройдёт сквозь ровно N кубиков.

Требуется сложить куб так, чтобы любая спица проходила сквозь кубики всех N цветов.

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

Во входном файле содержится единственное натуральное число N.

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

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

Ограничения

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

2

1 2
2 1
2 1
1 2

Задача E4. Максимальный элемент массива ≡

Условие

Вам необходимо написать программу, которая находит наибольший элемент в массиве.

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

В первой строке записано одно целое число N — количество элементов в массиве.

Далее следует N целых чисел a_i — элементы массива.

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

Выведите единственное целое число — наибольший элемент массива.

Ограничения

1 ≤ N ≤ 10³

 − 10⁶ ≤ a_i ≤ 10⁶

Описание подзадач и системы оценивания

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

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

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

Подсказка

Для того чтобы считывать элементы массива на языке Pascal следует использовать функцию read(). Применение функции readln() невозможно, так как все элементы массива записаны в одной строке.

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

3
1 3 2

3

5
8 5 6 10 3

10

1
1000000

1000000

Задача E5. Обход матрицы: обход 'змейкой' ≡

Условие

• в левом верхнем углу находится число 1
• далее числа распологаются "змейкой", т.е. по возрастанию слева направо в нечётных строках, и справа налево — в чётных

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

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

Ограничения

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

2

1 2
4 3

3

1 2 3
6 5 4
7 8 9

Задача F1. Отгадай слово ≡

Условие

Хрюша и Степашка играют в игру "Отгадай слово". Правила игры просты. Хрюша придумывает слово, состоящее из букв латинского алфавита, придумывает загадку и загадывает её Степашке. Задача Степашки — отгадать слово.

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

Ход Степашки заключается в том, что Степашка называет любую букву латинского алфавита.

1. Если такая буква есть в слове и все такие буквы закрыты, то все они открываются.
2. Если такая буква есть в слове и все такие буквы открыты, то все они закрываются.
3. Если такой буквы нет в слове, то никакие буквы не открываются и не закрываются.

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

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

Входной файл содержит ровно две строки.

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

Вторая строка входного файла также состоит из маленьких букв латинского алфавита и представляет собой последовательность букв, которые называет Степашка (буквы идут в том порядке, в котором их называет Степашка).

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

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

Если i-я буква открыта, то i-й символ выходной строки должен совпадать с i-м символом первой строки входного файла.

Если же буква закрыта, то соответствующий символ выходной строки должен быть '.' (точка).

Ограничения

Количество букв в слове от 1 до 15.

Количество ходов Степашки от 1 до 20.

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

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

frog
or

.ro.

frog
oro

.r..

frog
fffrrroooog

fr.g

frog
golf

f.og

frog
gorf

frog

Задача F2. Дифтонги ≡

Условие

Слова марсианского языка состоят из малых латинских букв. Буквы a, e, i, o, u, y считаются гласными, остальные — согласными.

Дифтонгом называется пара подряд идущих гласных букв, окружённых либо согласными буквами, либо границами слова. Например, в слове preemptio имеется два дифтонга, а в слове aaa — ни одного.

Требуется среди N данных слов найти те, в которых количество дифтонгов максимально.

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

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

Ограничения

1 ≤ N ≤ 100

Слова содержат от 1 до 255 символов.

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

3
e
ee
eee

ee

3
aabbee
cyydyyy
xiixiixiii

aabbee
xiixiixiii

Задача F3. Цензура ≡

Условие

В государстве Алюкобондии введена цензура на всех письменных СМИ. В соответствии с новым законом, все строки S1 во всех текстах должны быть заменены на строки S2. Помогите редактору Густаву автоматизировать этот процесс.

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

Входной файл содержит три строки: исходный текст, текст, который нужно заменить, текст на который нужно заменить.

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

Выходной файл должен содержать одну строку - получившийся текст после цензуры. В случае, если выполнить требуемое невозможно, вывести "-1".

Ограничения

1 ≤ length(S) ≤ 1000 1 ≤ length(S1), length(S2) ≤ 50

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

Hello World
Hello
Hell

Hell World

Задача F4. Миллион Z ≡

Условие

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

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

Ограничения

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

3
A 1 50
X 90 1000
D 30 1000000

2

Задача F5. 0 - a, 1 - ab ≡

Условие

Дана строка s, состоящая из N символов 0 или 1, а также строка t, состоящая из M символов a или b,

Над строкой s разрешено производить следующие действия:

• заменять символ 0 на строку из одного или более символов a
• заменять символ 1 на строку из одного или более символов a, либо на строку из одного или более символов b

Требуется определить, можно ли преобразовать строку s в строку t при помощи указанных действий.

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

Первая строка входного файла содержит числа N M.

Вторая строка входного файла содержит строку s.

Третья строка входного файла содержит строку t.

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

Ограничения

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

3 3
101
bab

Y

4 3
1001
bab

N

Задача G1. WK ≡

Условие

В рамках социального проекта ЦПД в кампусе ДВФУ была организована социальная сеть WK, чтобы студенты могли обмениваться через неё учебными материалами и решать все насущные вопросы.

У каждого пользователя этой сети есть список контактов. Однажды в сеть WK поступил вброс о том, что студентам стали снижать оценки за лайки не(у)годным преподавателям.

Однажды утром на департамент мемов матфака поступило видео из серии "Капоэйра в неожиданных местах", в котором сотрудник кафедры информатики, математического и компьютерного моделирования ШЕН рассказал о произошедшем языком танца. Затем из этого видео выбрали понравившийся фрагмент и стали распространять в сети WK как мем.

Итак, однажды утром админ группы "Учеба каждый день, какой ужас" переслал всем своим контактам этот мем. Вечером его контакты получили мем.

Затем информация распространялась по сети WK следующим образом.

1. Сообщения отправляются только утром, а получаются только вечером.
2. Если пользователь B получил информацию от пользователя A, то утром следующего дня пользователь B разошлёт эту информацию всем своим контактам, от которых он не получал эту информацию и которым он не отправлял эту информацию.

Социальная сеть WK устроена таким образом, что если пользователь B находится в списке контактов пользователя A, то и пользователь A находится в списке контактов пользователя B. Никакой пользователь не может находиться в своём же списке контактов.

Требуется определить, сколько раз каждый пользователь социальной сети WK получит мем с вбросом.

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

Первая строка входного файла содержит целое число N — количество пользователей социальной сети WK.

Далее для каждого пользователя во входном файле записана следующая информация. Сначала идёт целое число k_i — количество пользователей в списке контактов пользователя i, за которым следуют k_i различных целых чисел от 1 до N — номера пользователей из списка контактов i-го пользователя.

Админ группы "Учеба каждый день, какой ужас", он же админ группы "Стримы от Малявина" — это пользователь с номером 1.

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

Требуется вывести в выходной файл N целых чисел: для каждого пользователя социальной сети WK нужно вывести, сколько раз он получит мем.

Ограничения

1 ≤ N ≤ 100.

0 ≤ k_i < N.

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

3
2  2 3
1  1
1  1

0 1 1

3
2  2 3
2  3 1
2  1 2

0 2 2

6
1  2
3  1 3 4
2  5 2
2  2 5
2  4 3
0

0 1 1 1 2 0

Задача H1. Максимум в скользящем окне ≡

Условие

Пусть задан массив из n целых чисел. По этому массиву будут ходить два указателя l и r. Изначально оба они указывают на первый элемент массива. Оба указателя могут двигаться только вправо, на одну позицию за раз. При этом указатель l никогда не оказывается правее указателя r, и ни один из них не выходит за пределы массива. Вам нужно после каждого перемещения указателя определить максимум всех элементов от указателя l вправо до указателя r (включая позиции, на которые указывают l и r).

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

Первая строка входного файла содержит целое число n - размер массива. Во второй строке содержится строке n целых чисел a_i - сам массив.

В третьей строке указано число m — количество перемещений. В четвертой строке — m символов 'L' или 'R', разделенных пробелами. 'L' означает, что нужно сдвинуть l вправо, 'R' — что нужно сдвинуть r вправо.

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

В выходной файл выведите в одну строку ровно m чисел, где i-е число — максимальное значение на отрезке от l до r после выполнения i-й операции.

Ограничения

1 ≤ n ≤ 10⁵

|a_i| ≤ 10⁹

0 ≤ m ≤ 2n − 2

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

4
-3 -2 -1 0
6
RRRLLL

-2 -1 0 0 0 0

10
1 4 2 3 5 8 6 7 9 10
12
RRLRRRLLLRLL

4 4 4 4 5 8 8 8 8 8 8 6

Задача H2. 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

Задача H3. Перевод длинных чисел ≡

Условие

Дано неотрицательное целое число a, записанное в системе счисления по основанию p. Требуется перевести это число в систему счисления по основанию q. Для представления цифр больше 9 используются заглавные латинские буквы (A — 10, B — 11, &hellip;, Z — 35).

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

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

Ограничения

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

2 10
10010

18

31 17
AF2J5

6DG3BE

Задача I1. Очередь к врачу ≡

Условие

Поликлиника города N просит вас о помощи. В период пандемии на прием к терапевту стало приходить слишком много посетителей. Прием у терапевта длится ровно K минут. Если очередной посетитель приходит в тот момент, когда терапевт уже принимает кого-то, то он встает в очередь. Никто не любит очереди, поэтому перед тем, как предпринимать какие-то действия, администрация поликлиники попросила вас найти максимальную длину очереди за последний день.

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

Первая строка входных данных содержит два целых числа N — количество посетителей за последний день и K — длительность приема одного пациента.

Вторая строка содержит N чисел, отсортированных по возрастанию: t_i  — время, когда i − ый посетитель пришел на прием к терапевту.

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

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

Ограничения

1 ≤ N ≤ 10⁵

1 ≤ K ≤ 10⁹

0 ≤ t_i ≤ 10⁹

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

5 5
0 5 5 6 20

2

5 2
1 4 6 8 20

0

6 5
0 5 10 15 19 25

1

Задача I2. Ближайшее число ≡

Условие

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

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

Входной файл содержит целое число N за которым следует N целых чисел a_i - исходная последовательность.

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

В выходной файл необходимо вывести N целых чисел b_i, таких что b_i является ответом на задачу для числа a_i.

Ограничения

1 ≤ N ≤ 10⁶

|a_i| ≤ 10⁹

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

4 1 2 3 4

2 3 4 4

1
1

1

Задача K1. Двоичные последовательности ≡

Условие

Здравствуй, юный падаван!

Прошу тебя вывести все двоичные последовательности длины N.

Реши задачу двумя способами:

• рекурсивным перебором
• прибавлением 1 к числу в двоичной системе счисления

Да пребудет с тобой произведение массы на ускорение!

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

Входной файл содержит единственное целое число N.

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

Требуется вывести в выходной файл все двоичные строки длины N в лексикографическом порядке, по одному в каждой строке.

Ограничения

1 ≤ N ≤ 15

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

2

00
01
10
11