Задача A. Appropriate applicant ≡

Условие

Сотрудникам НИИЧАВО повстречалась в лесу группа программистов. Выяснилось, что ровно a процентов из них небалованные, b процентов — добровольцы и c процентов — согласны жить в общежитии. Определите наименьшее возможное число людей в такой группе и найдётся ли гарантированно в ней хотя бы один программист, обладающий всеми тремя необходимыми качествами.

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

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

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

Выведите в первой строке одно натуральное число. Во второй строке выведите Yes или No — ответы на вопросы задачи.

Ограничения

1 ≤ a, b, c ≤ 99

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

В первом примере наименьшее возможное количество людей будет равно 20, для этого числа все указанные проценты окажутся целыми числами (4, 5 и 6). Однако, возможно, что нужными качествами будут обладать разные люди.

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

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

20
25
30

20
No

75
75
75

4
Yes

Задача B. Bouncing particles ≡

Условие

Пусть имеется прямоугольная область, разделенная N × M квадратных ячеек. В некоторых из указанных ячеек были размещены частицы.

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

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

Так как полученное число может оказаться слишком большим, в качестве ответа следует вывести остаток от его деления на (2³² − 5).

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

В начале входных данных записана тройка чисел N, M и L.

Далее указано число K, за которым следует набор из 2 × K индексов стартовых ячеек: X_i, Y_i.

Здесь полагается, что индексация ячеек начинается с нуля.

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

Выходные данные должны содержать полученное число.

Ограничения

1 ≤ N ⋅ M ≤ 2 500, 0 ≤ L ≤ 50, 2 ≤ K ≤ 50, 0 ≤ X_i < N, 0 ≤ Y_i < M.

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

10 10 2
2
4 5
5 4

256

10 10 2
2
2 3
7 6

0

Задача C. Compound palindrome ≡

Условие

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

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

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

При этом сами слова, из которых составлен такой палиндром, не обязаны являться палиндромами.

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

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

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

Входные данные содержат единственную строку S.

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

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

Если таких нет, выход следует оставить пустым.

Ограничения

1 ≤ |S| ≤ 2 ⋅ 10⁶.

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

abcdefxyz123412xyzabcdef

6
3
2

ab32cdefxyz12xyzab14cdef

Задача D. Distribution by desks ≡

Условие

Для проведения олимпиады по математике для 8 − 11 классов выделили несколько кабинетов. В первом кабинете стоит n рядов из парт, в каждом ряду по 3 парты, за одной партой может сидеть ровно один человек.

Организаторы олимпиады хотят посадить учеников за все парты первого кабинета так, что в любом квадрате из парт со стороной 2 будут сидеть ученики попарно разных классов (то есть, в любом квадрате сидит по одному ученику из 8-го, 9-го, 10-го и 11-го классов).

На рисунке вы можете видеть один из вариантов подходящей рассадки при n = 2 (и в красном, и в зелёном квадратах все ученики из разных параллелей).

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

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

Единственная строка входных данных содержит натуральное число n.

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

Выведите одно натуральное число — ответ на вопрос задачи по модулю 10⁹ + 7 (так как число может быть очень большим).

Ограничения

1 ≤ n ≤ 10¹⁸

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

1

36

Задача E. Easy banknote thrower ≡

Условие

Если вы уже прочитали условие задачи H. Hard banknote thrower: условие этой задачи отличается лишь в операции, которую делает банкнотомёт. А именно: операция сложения вместо операции поразрядного умножения.

Олег долгое время пользуется услугами банка Деньгофф. Сегодня ему потребовалось метнуть большую сумму денег с карты, но он забыл от неё пин-код. К счастью для компании, банкнотомёты Деньгофф умеют давать подсказки про пин-код.

Во-первых, банкнотомёт сообщает результат сравнения соседних цифр в пин-коде. Например, для пин-кода 0911 получится <>=, а для популярного пин-кода 1234 — <<<.

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

Помогите Олегу определить пин-код от карты до того, как она заблокируется.

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

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

Сначала программа жюри отправляет вашей программе целое число N — количество цифр в пин-коде. Далее, в новой строке отправляется строка из N − 1 символа <, > и = — сравнение соседних цифр в пин-коде.

После этого ваша программа может делать запросы вида "? X", где X — целое число, попытка ввести пин-код, можно выводить без лидирующих нулей. Если пин-код правильный, то программа жюри отвечает вашей программе строкой "ok", после этого ваша программа должна завершиться. Иначе программа жюри отвечает строкой из минимум N − 1 символа <, > и = — сравнение соседних цифр результата операции сложения правильного и введенного пин-кодов.

Ваша программа может сделать только 9 запросов с неправильным пин-кодом. Если ваша программа превысит допустимое количество запросов, то она получит вердикт "Wrong answer".

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

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

Если ваша программа получила от программы жюри строку "-1", то она должна немедленно завершиться. Такое возможно, если ваша программа нарушила протокол взаимодействия. Если ваша программа не завершится, то вердикт может отличаться от описанных выше (например, может быть вердикт "Runtime error").

Ограничения

2 ≤ N ≤ 18

0 ≤ X < 10^N

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

4
<<>

<<>

<<>

<<>

=<=

==>

><>

><>

><>

><>

ok

? 1001

? 2002

? 3003

? 4004

? 5100

? 6000

? 7000

? 8000

? 9000

? 0451

3
==

>=

>=

><=

ok

? 100

? 200

? 300

? 777

18
====<<<<<<<<<====

ok

? 1234567899999

Задача F. Function with constraints ≡

Условие

Рассмотрим функцию следующего вида: F(X, Y) = AB ⋅ X + CD ⋅ Y.

Требуется найти такие целочисленные A, B, C и D, при которых на заданном наборе точек (X_i, Y_i)
указанная функция удовлетворяет заранее известным условиям:
RoundDawn(F(X_i, Y_i)) = Z_i либо RoundUp(F(X_i, Y_i)) = Z_i,
где RoundDawn() и RoundUp() — округление в меньшую и большую сторону соответственно.

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

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

Вначале указывается знак операции: '>' для RoundDawn либо '<' для RoundUp.

Далее следуют три целых числа: X_i, Y_i, Z_i.

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

Если задача имеет решение, в выходные данные записывается число 1,
за которым следуют найденные значения A, B, C и D.

Если существует более одного решения,
выводится любое из них.

Если решения не существует, выводится
единственное число 0.

Ограничения

Все входные значения являются целыми десятичными числами.

 − 40 ≤ (X_i, Y_i, Z_i) ≤ 40, 0 < N ≤ 2000

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

4

> -2 -5 -6
<  3  7  8
> -1  1  1
<  4 -3 -5

1
-16 37
93 74

4

> -3 -1  1
<  5 -3 -6
>  7  4  1
<  2 -1 -3

0

Задача G. Game of Mafia ≡

Условие

Петя и его друзья решили поиграть в популярную игру Мафия. Каждый игрок в этой игре получает одну из ролей: шериф, мафиози или мирный гражданин. После раздачи ролей город засыпает, все игроки закрывают глаза, после чего их открывают только мафиози, чтобы познакомиться друг с другом, другие игроки при этом не будут знать наверняка кто есть кто. Игра поделена на раунды, один раунд состоит из дня и ночи. Днем игроки общаются и голосуют за то, кого отправить в тюрьму. Ночью шериф ищет мафию, а мафия кого-то убивает.

Всего на игру собралось N человек. Для такого количества игроков оптимальное распределение ролей следующее: один шериф и M мафиози.

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

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

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

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

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

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

Гарантируется, что входные данные корректные и соответствуют ситуации описанной в условии.

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

В единственной строке выведите YES или NO — можно ли однозначно определить игроков с ролью мафиози.

Ограничения

6 ≤ N ≤ 500

1 ≤ M ≤ ⌊ N2⌋

1 ≤ a_i,j ≤ N

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

В первом примере мафией являются игроки 3 и 5.

Во втором примере мафией могут быть пары игроков 1 и 5, 3 и 7, 4 и 8.

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

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

YES

8 2
3 7
7 5
1 8
7 1
2 7
2 5
4 8
5 1

NO

Задача H. Hard banknote thrower ≡

Условие

Если вы уже прочитали условие задачи E. Easy banknote thrower: условие этой задачи отличается лишь в операции, которую делает банкнотомёт. А именно: операция поразрядного умножения (смотрите Пояснение) вместо операции сложения.

Олег долгое время пользуется услугами банка Деньгофф. Сегодня ему потребовалось метнуть большую сумму денег с карты, но он забыл от неё пин-код. К счастью для компании, банкнотомёты Деньгофф умеют давать подсказки про пин-код.

Во-первых, банкнотомёт сообщает результат сравнения соседних цифр в пин-коде. Например, для пин-кода 0911 получится <>=, а для популярного пин-кода 1234 — <<<.

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

Помогите Олегу определить пин-код от карты до того, как она заблокируется.

Пояснение

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

Более формально, операцию поразрядного умножения можно выразить формулой ∑_i = 0 a_i * b_i * 10ⁱ, где a_i и b_i — цифры на i-й позиции.

Примеры поразрядного умножения представлены на картинке.

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

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

Сначала программа жюри отправляет вашей программе целое число N — количество цифр в пин-коде. Далее, в новой строке отправляется строка из N − 1 символа <, > и = — сравнение соседних цифр в пин-коде.

После этого ваша программа может делать запросы вида "? X", где X — целое число, попытка ввести пин-код, можно выводить без лидирующих нулей. Если пин-код правильный, то программа жюри отвечает вашей программе строкой "ok", после этого ваша программа должна завершиться. Иначе программа жюри отвечает строкой из минимум N − 1 символа <, > и = — сравнение соседних цифр результата операции поразрядного умножения правильного и введенного пин-кодов.

Ваша программа может сделать только 9 запросов с неправильным пин-кодом. Если ваша программа превысит допустимое количество запросов, то она получит вердикт "Wrong answer".

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

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

Если ваша программа получила от программы жюри строку "-1", то она должна немедленно завершиться. Такое возможно, если ваша программа нарушила протокол взаимодействия. Если ваша программа не завершится, то вердикт может отличаться от описанных выше (например, может быть вердикт "Runtime error").

Ограничения

2 ≤ N ≤ 18

0 ≤ X < 10^N

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

4
<<>

===

=<>

<>=

=<>

=<>

=<>

=<=

<>>

<>>

ok

? 1000

? 0010

? 0020

? 0012

? 0013

? 0014

? 0015

? 0210

? 0150

? 0451

3
==

>=

>=

>=

<>=

ok

? 100

? 200

? 300

? 400

? 333

18
====<<<<<<<<<====

ok

? 1234567899999

Задача I. Improvement of tessitura ≡

Условие

Голос исполнителя характеризуется диапазоном нот, которые он может спеть. Этот диапазон называется тесситурой. А песня характеризуется одним числом h_i — высотой. Если h_i попадает в тесситуру исполнителя, то песня может быть спета.

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

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

Первая строка входных данных содержит пять целых числа l, r, d, c, k. Вторая строка содержит одно число n. Третья строка содержит n целых чисел h_i.

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

Выведите "YES" если все c концертов состоятся и "NO" в противном случае.

Ограничения

1 ≤ n, k ≤ 10⁵

1 ≤ h_i, l, r, d ≤ 10⁹

1 ≤ c ≤ 100

l,r ∈ [h₁, h₂, …, h_n]

Все h_i различны.

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

1 100 200 2 2
5
1 100 200 300 400

YES

7 8 4 3 2
6
5 6 7 8 11 12  

YES

1 5 1 6 1
6
1 2 3 4 5 10

YES

4 6 4 3 2
6
4 6 10 11 12 13 

NO

Задача J. Jump to number ≡

Условие

Требуется найти k-е по порядку q-ичное число (начиная с 1-го), сумма цифр которого равна n, а длина не превосходит l.

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

Во входных данных записаны четыре целых числа: q, n, l и k.

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

Выходные данные должны содержать полученное число.

Если такого числа нет, либо оно выходит за пределы допустимого диапазона,
выходные данные следует оставить пустыми.

Ограничения

2 ≤ q ≤ 10, 1 ≤ (n, l) ≤ 4000, 1 ≤ k ≤ 10¹⁸

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

10 100 12 1

199999999999

2 1 1 2

Задача K. Knitting sweaters ≡

Условие

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

Скоро Новый Год! А значит — самое время подумать о праздничном наряде.

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

Тимофей, как истинный программист, решил, что оленьи рога должны представлять собой бинарное дерево c 2ⁿ листьями и со смещенными к центру вертикальными линиями длины k.

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

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

Две строки входного файла содержат два натуральных числа n и k.

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

Выведите требуемое изображение. Для формирования линий используйте символ # (ASCII-код 35), для фона — символ . (ASCII-код 46). Ваша программа не должна выводить лишние строки или столбцы, заполненные только символами фона.

Ограничения

1 ≤ n ≤ 8

2 ≤ k ≤ 10

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

1
8

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

3
2

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

2
5

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

Задача L. Lines and triangles ≡

Условие

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

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

В начале входных данных записано натуральное число n, за которым следует ровно n прямых. Каждая прямая задается парой несовпадающих точек: (Ax_i, Ay_i), (Bx_i, By_i).

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

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

Ограничения

Гарантируется, что никакие две прямые не совпадают между собой.

Все входные значения являются целыми десятичными числами.

 − 10⁴ ≤ (Ax_i, Ay_i, Bx_i, By_i) ≤ 10⁴, 3 ≤ n ≤ 300

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

5
  0 -20  15 -20
-10  10  35 -35
  0   0   0 -10
-10   0  30   0
-20   0   0  20

3

5
-10   0   0 -20
-20 -10 -10 -30
  0   0  10  24
  0  10  10 -10
-10   0   0  24

0

Задача M. Mountain ≡

Условие

Гора представлена двоичной кучей на n вершинах. Также есть число k, которое равно сумме расстояний между всеми парами вершин. Зная k, найдите n.

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

• Каждая вершина имеет не более трех соседей
• Глубина всех листьев (расстояние до корня) различается не более чем на 1 слой.
• Последний слой заполняется слева направо без «дырок».

К примеру, двоичная куча на 4 вершинах:

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

Единственная строка входных данных содержит натуральное число k.

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

Выведите n.

Ограничения

0 ≤ k ≤ 10¹⁸

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

Расстояние между 1-ой и 2-ой вершиной равно 1. Расстояние между 1-ой и 3-ой вершиной равно 1. Расстояние между 1-ой и 4-ой вершиной равно 2. Расстояние между 2-ой и 3-ой вершиной равно 2. Расстояние между 2-ой и 4-ой вершиной равно 1. Расстояние между 3-ой и 4-ой вершиной равно 3. Сумма всех расстояний равна 1 + 1 + 2 + 2 + 1 + 3 = 10.

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

10

4