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

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

Осьминог Сквидвард любит путешествовать по массиву. Сейчас он находится в ячейке $$$n$$$. Сквидвард очень хочет вернуться домой, который находится в ячейке $$$1$$$, для этого он хочет передвигаться прыжками по массиву. Осьминог умеет делать $$$m$$$ разных прыжков силой $$$k_i$$$. Прыжок силой $$$k_i$$$ перемещает его из ячейки $$$x$$$ в ячейку $$$\dfrac{x}{k_i}-1$$$ в том и только том случае, если $$$x$$$ делится без остатка на $$$k_i$$$.

За какое минимальное количество прыжков Сквидвард вернется домой?

2157 год. Полдень человечества. Вооруженные Великой теорией Воспитания, люди забыли о войнах, голоде и терроризме. Возродилась природа. Прорыв в медицине избавил людей от болезней, позволил использовать скрытые ресурсы человеческого тела. Жители Земли осваивают отдалённые планеты, а Андрей и Илья сражаются за звание чемпиона района по шахматам.

Правила в шахматах в будущем сильно изменились. Например, игроки играют не на обычной доске, а на так называемом «Торе» – фигуры могут ходить через границы поля, переставляя свою фигуру в соответствующую клетку с другой стороны доски (подсчёт клеток, находящихся под боем фигуры, определяется аналогично). Так, например, ход короля с клетки H4 на одну вправо приведёт к появлению его в клетке A4, а ход ферзя на одну клетку по диагонали вниз и вправо из клетки E1 ведёт к появлению ферзя на клетке F8. Игра происходит на доске 8 на 8.

Ниже показан пример возможных ходов ферзя по одной из диагоналей:

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

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

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

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

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

Вы играете за белых и делаете первый ход. Каждый ваш ход должен описываться единственной строкой, содержащей три числа, разделённых пробелом. Первое число – номер ферзя, который должен сейчас походить (ферзи пронумерованы во входных данных). Затем должны идти два числа, каждое из которых не превосходит 7 по модулю – смещение соответствующего ферзя по первой и второй координате соответственно. Смещения не должны быть одновременно равны нулю и должны быть корректным ходом ферзя.

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

Возможны исключительные случаи.

Во-первых, вы можете поставить мат чёрному королю. В таком случае следует в отдельной строке вывести слово «Checkmate!» без кавычек, и после этого завершить работу программы.

Во-вторых, вы можете случайно нарушить какие-нибудь правила. Например, сделать более 7 ходов, поставить чёрного короля в пат, забыть вывести слово «Checkmate!» в конце или даже сделать какой-нибудь некорректный ход(попытаться походить ферзём как конём или поставить ферзя в уже занятую другим ферзём клетку). Во всех этих случаях вы получите на вход строку, состоящую из двух нулей, разделённых пробелом. После этого вам необходимо завершить работу программы. Также вы получите эту строку, если потеряете хотя бы одного ферзя или выведите неправильный номер ферзя (не равный 1 или 2).

После каждого действия вашей программы выводите символ перевода строки. После вывода очередной строки обязательно используйте функции очистки потока, чтобы часть вашего вывода не осталась в каком-нибудь буфере. Например, на С++ надо использовать функцию «fflush(stdout)», на Java и Kotlin вызов «System.out.flush()» и «stdout.flush()» для языка Python.

Ваня построил бесконечное бинарное дерево по следующему правилу:

• В корне находится число 1 / 1;
• Левый сын вершины p / q будет иметь значение p / (p + q);
• Правый сын вершины p / q будет иметь значение (p + q) / q.

На рисунке вы можете видеть три верхних уровня дерева:

Затем Ваня пронумеровал вершины дерева сверху вниз по схеме, указанной на рисунке (следите за стрелочкой). Обозначим через F(i) i-ю дробь дерева, тогда первые его элементы будут иметь следующие значения: $$$F(1) = 1/1, F(2) = 1/2, F(3) = 2/1, F(4) = 1/3, F(5) = 3/2, F(6) = 2/3$$$.

Ваня придумал интересную задачу. Дано число $$$N$$$. Нужно найти дробь $$$p/q$$$, которой соответствует значение $$$F(N)$$$.

Детские пазлы  — развивающая игра для маленьких детей. В коробке на дне прикреплен рисунок, ребенку необходимо подставлять фрагменты к картинке, определять, где он располагается на поле, и прикреплять его к соседям. В результате сборки вся картинка будет покрыта, и сами фрагменты будут плотно прилегать к бортам коробки. Пазлы представляют собой прямоугольное поле $$$n$$$ на $$$m$$$, каждый фрагмент имеет $$$4$$$ стороны, при этом каждый пазл размещается в определенном пересечении столбца и строки поля. Фрагменты $$$a$$$, $$$b$$$ считаются соседними, если у них есть общая сторона. Фрагменты $$$a$$$, $$$b$$$ считаются скрепленными, если существует набор фрагментов, образующих непрерывную цепочку соседей, соединяющих $$$a$$$ и $$$b$$$. Фрагмент можно сдвинуть наверх, вниз, влево, вправо, если все скрепленные с ним пазлы тоже можно сдвинуть в этом же направлении и не покинуть поле коробки.

Перед сном Вероника случайно опрокинула коробку с пазлами на пол. Игорь смог найти часть фрагментов на полу и аккуратно расположить их внутри коробки по картинке. Игорь задался серьезным вопросом, можно ли какие-нибудь фрагменты в коробке сдвинуть?

Для одного из своих заказчиков компания «Рафт» обучила нейросеть, состоящую из $$$N$$$ слоёв. Вес каждого отдельного слоя равен $$$a_i$$$. Программисты могут проранжировать слои нейросети любым способом, однако недавно был открыт критерий, который гарантированно позволяет назвать построенную нейросеть качественной: последовательности весов в слоях образуют пилообразную последовательность. Числовая последовательность называется пилообразной, если каждый ее элемент (кроме первого и последнего) либо больше обоих своих соседей, либо меньше обоих соседей. Например, последовательность $$$4, 2, 5, 3$$$ является пилообразной, а $$$1, 2, 4, 3$$$ – нет, поскольку $$$1 \lt 2 \lt 4$$$. Сотрудников компании заинтересовал следующий вопрос: сколько качественных нейросетей может быть построено из имеющихся слоёв? Помогите им – напишите программу, которая по заданной последовательности весов слоёв определит, сколькими способами можно их переставить так, чтобы они образовывали пилообразную последовательность.

Компанией «Арго» разработан продукт, позволяющий обеспечивать полный цикл работы с кодом. При сборке новой версии продукта, во время автоматического тестирования были обнаружены ошибки, которые потребовалось исправить. Известно, что ошибки были допущены в течение последних $$$24$$$ часов, также имеется лог изменений, в котором указано имя разработчика и время внесения им изменений в продукт. Было выявлено, что ошибки были допущены теми программистами, которые внесли нечётное количество изменений, причём последнее по времени изменение содержало ошибку. Напишите программу, которая поможет найти всех разработчиков, которые внесли изменения с ошибками, и время ошибки.

Пытаясь зайти в личный онлайн-кабинет Т-Банка, люди нередко делают ошибки при наборе пароля. Это может стать большой проблемой, так как от пользователей требуется придумать довольно длинные пароли (как мы знаем, чем больше символов в пароле, тем больше вероятность совершить ошибку при его наборе). Любители техники слепой печати склонны совершать серьёзные ошибки, если одна из рук не находится в правильном положении при печати, поскольку печатающие не смотрят на клавиатуру во время печати. Это может привести к тому, что все символы, набранные неправильно расположенной рукой, будут на одну клавишу дальше. Например, на $$$QWERTY$$$-клавиатуре «you» превратится в «upi», если правая рука будет размещена на одну клавишу правее обычного исходного положения.

Т-банк решил внедрить новый алгоритм проверки паролей, который учитывает некоторые распространенные ошибки (но не все), допускаемые людьми при вводе паролей на $$$QWERTY$$$-клавиатуре (см. рисунок ниже).

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

Эффект нажатия Caps Lock ограничен буквенными символами и переключает действие клавиши Shift относительно этих символов. Другими словами, когда Caps Lock не нажат, все буквы печатаются как строчные, если только не нажата одна или обе клавиши Shift. Противоположное поведение происходит, когда включен Caps Lock – по умолчанию печатаются заглавные буквы, если только не нажата одна или обе клавиши Shift, что приводит к получению строчных букв. Разработчики алгоритма предполагают, что состояние клавиши Caps Lock не переключается во время ввода пароля.

Алгоритм, разработанный специалистами Т-Банка, ищет отклонения от правильной последовательности нажатий клавиш. Например, если правильный пароль — «BYt*», правильная последовательность, используя клавиатуру, указанную выше, – Shift+b, Shift+y, t, Shift+8. Если пользователь случайно нажал клавишу Caps Lock перед вводом пароля, но затем использовал правильную последовательность нажатий клавиш, он в конечном итоге набрал бы «byT*».

Т-Банк решил разрешить определенные отклонения или комбинации отклонений от правильной последовательности, которые описаны в таблице ниже. Допускается максимум одна из ошибок 1, 2, 3 и 4 типов, но любая из них может возникнуть в сочетании с ошибкой 5 типа.

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

Профессор Р. в свободное время увлекается шахматами, а его любимой математической задачей является задача о ходе коня. Задача о ходе коня — задача о нахождении маршрута шахматного коня, проходящего через все поля доски по одному разу. В терминах теории графов, данная задача идентична задаче поиска гамильтонова пути в графе. Для доски $$$8 \times 8$$$ количество всех замкнутых маршрутов коня (гамильтоновых циклов) без учёта направления обхода равно $$$13~267~364~410~532$$$. Количество всех незамкнутых маршрутов (с учётом направления обхода) равно $$$19~591~828~170~979~904$$$.

На рисунке ниже показан один из возможных маршрутов коня на доске (числами от 1 до 64 пронумерованы ходы):

Профессора Р. заинтересовали магические маршруты. Назовём маршрут коня магическим, если суммы номеров ходов в каждом столбце и каждой строке одинаковы (для доски размера $$$8 \times 8$$$ это значение равно 260). Профессор Р. придумал следующую задачу: из магического маршрута коня удаляется некоторое количество ходов, требуется восстановить любой маршрут, который содержит неудалённые ходы именно в таком порядке, в котором они расположены на доске.

Помогите профессору – напишите программу, которая найдёт магический маршрут, удовлетворяющий условиям.

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

Профессор дал студентам тест, в котором каждый из вопросов подразумевает выбор либо ответа «Истина», либо ответа «Ложь» (профессор предпочитает эти варианты традиционным «Да» и «Нет», так как очень любит дискретную математику и математическую логику). Студент может либо ответить на вопрос, отметив один из вариантов, либо оставить оба поля пустыми. Известно, что каждый студент ответил хотя бы на два вопроса. Профессор Р. хочет сделать так, чтобы все студенты не сдали тест, поэтому он собирается изменить последовательность правильных ответов так, чтобы ни один студент не дал более одного правильного ответа.

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

Профессор Р. очень любит алгебру, особенно сильно он любит складывать числа. Недавно он изобрёл новый способ кодирования чисел – каждому целому неотрицательному числу он ставит в соответствие последовательность из пар, где первый элемент пары равен цифре, а второй – сколько раз подряд встречается эта цифра после предыдущих описанных цифр, причём корректным представлением является то, в котором количество пар минимально. Так, например, число $$$1333377$$$ будет записано в виде трёх пар: $$$(1, 1), (3, 4)$$$ и $$$(7, 2)$$$. Профессор решил взять числа $$$A$$$ и $$$B$$$, закодировать их, сложить и вывести результат в закодированном виде, однако у него не получилось это сделать. Тогда он пришёл с этой задачей к своим студентам и на паре по алгебре задал её на дом. Студенты тоже не смогли её решить и решили обратиться к вам.

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

Игорь очень проголодался, составляя задачи на очередную олимпиаду, и решил перекусить пиццей с пепперони из «ПиццаФабрика».

Привезённая курьером пицца оказалась занимательной с точки зрения математики. Форма начинки на пицце имеет форму круга с радиусом $$$R$$$ с центром окружности $$$(0,0)$$$, каждая пепперони также представляет собой круг, и все они имеют одинаковый радиус, равный $$$r$$$, центры всех пепперони располагаются на начинке в координатах $$$(x_i, y_i)$$$. Игорь задался интересным вопросом: какая площадь поверхности начинки пиццы не покрыта пепперони? Помогите ему – напишите программу, которая посчитает эту площадь.