Алгоритмы

На уроке информатики Фоме задали задачу о проверке гипотезы Гольдбаха.
Условие задачи выглядело так:
Гипотеза Гольдбаха (не доказанная до сих пор) утверждает, что любое четное число (кроме 2) можно представить в виде суммы двух простых чисел.
Фома легко решил данную задачу методом поиска "первого решения".
Дома, Фома заметил, что во время отладки, он получал решения, в которых одно из чисел было не очень большим.
Так, для числа 1000000, он получил разложение 1000000=17+999983. Фома решил проверить, в чем сложность гипотезы Гольдбаха.
Для этого Фома придумал задачу:
Определим функцию g(n) = количеству разложений числа n в сумму двух простых чисел. (разложения, отличающиеся порядком слагаемых, считаются одинаковыми).
На отрезке натуральных чисел от A до B найдите чётное число x такое, что: g(x) кратно 5 и имеет минимальное значение среди всех g(x) кратных 5 на этом отрезке.
Решите задачу Фомы.

Входные данные
Границы отрезка A, B (два натуральных числа 5≤ A<B≤106 )
Выходные данные
- "Impossible" если для всех чётных x из отрезка [A;B] значение g(x) не кратно 5.
- два числа - x, g( x ) ( g(x) кратно 5 и минимальное для A≤ x≤B). Если таких x несколько, то выведите минимальное значение x.

Примеры

№	Входные данные	Выходные данные	Примечание
1	5 10	Impossible	На отрезке всего три четных числа (6, 8, 10) Число 8 =3+5 и других представлений нет (5+3 считается таким же как 3+5) Для 10 есть два представления (3+7 и 5+5) Таким образом значений x, при которых g(x) кратно 5 нет.
2	20 60	48 5	g(x) может принимать значения меньшие 3 (g(20)=2) g(x)=5 для x из множества {48, 54}. 48 -минимальное значение
3	2000 2005	Impossible

Галактическая станция «Вавилон» имеет N (0 < N <= 10) ангаров для космических кораблей.
Цикл предполетной подготовки длится M (0 < M <= 10) суток. Цикл начинается в тот же момент, как корабль залетает в ангар. До окончания цикла корабль не может покинуть ангар и соответственно начать новый рейс.
Сутки на станции составляют 24 часа. Календарь на станции составляет 365 дней, которые не делятся на месяцы.
Вам попали в руки фрагменты станционного журнала (0 < K <= 1000 строк). В нем фиксируются даты и время прибытия кораблей в зону станции, а также заявки на рейсы со станции. Гарантируется, что все страницы относятся к одному году.
Если корабль подлетает к станции, а все ангары заняты, то ему отказывают в обслуживании. Если вылет со станции назначен на тот же час, что и прилет нового корабля, будем считать, что сначала ангар освобождается, а потом новый корабль размещается в пустом ангаре (начало цикла будет считаться с момента прилета).
Если приходит запрос на рейс со станции, то в рейс уходит тот корабль, который готов к вылету. Если таких кораблей несколько, то выбирается тот, который дольше находится на станции. Если готовых к рейсу кораблей нет, то рейс задерживают и ждут, когда появится корабль, который пройдет цикл предполетной подготовки. Если до конца периода кораблей для выполнения рейса не найдется, то заявка считается НЕ задержанной, а отклоненной.
По данным журнала определите скольким кораблям было отказано и сколько рейсов было отклонено в рассматриваемый период.

Входные данные:
В первой строке через пробел три числа N M K.
Дальше K строк в формате
День Час Признак
Где День – это номер дня от начала года; Час – час события; Признак это 1, если корабль прилетает, -1, если это запрос на вылет.
Выходные данные:
Два целых числа, каждое на новой строке:
– количество отказов в обслуживании;
– количество отклоненных заявок.

Примечание
В журнале 9 записей.
1) 1 9 1
2) 8 12 -1
3) 6 15 -1
4) 6 12 -1
5) 2 18 1
6) 5 6 1
7) 6 12 1
8) 7 12 -1
9) 2 21 1
Корабли, прибывшие 1-го в 9:00 и 2-го в 18:00, были поставлены в два ангара, имеющиеся на станции (1-ая и 5-ая строки журнала).
6-го числа в 12:00 1-ый ангар покинул корабль по заявке из 4-ой строки журнала. В тот же момент его место занял корабль с 7-ой строки.
На момент прилета кораблей из 6-ой и 9-ой строк оба ангара были заняты. Эти корабли получили отказ.
Выполнение заявок с 3-ей и 8-ой строк журнала было задержано, так как не было готовых к вылету кораблей.
Заявка со 2-ой строки была отклонена, так как в ангарах и на подлете в рассматриваемый интервал времени кораблей не было.

Аспирант Шлёпов собирается провести чемпионат вуза по шахматам. Так как игроков в вузе много, у сообщества есть свой рейтинг ELO. Шлёпов собирается разделить игроков на основании этого рейтинга на две лиги. В высшей лиге должно играть не менее трети игроков, но при этом наименьшее возможное количество; отбор в лигу идёт на основании ELO. Двух игроков с одинаковым ELO распределять в разные лиги нельзя. Высшая лига на турнире должна быть обязательно. Определите, начиная с какого ELO, игроки попадают в высшую лигу.

Формат входных данных
На вход программе в первой строке подаётся натуральное число N (N ≤ 1000) – количество игроков. Далее в N строках идёт по одному натуральному числу k_i – рейтинг ELO игрока номер i (1 ≤ k_i ≤ 2500).
Формат выходных данных
Выведите одно целое число – ELO, начиная с которого, игроки попадают в высшую лигу. Если в высшей лиге окажется весь турнир, надо вывести наименьший ELO среди заявленных игроков.

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

Заданы два различных целых положительных числа a и b, записанные в восьмеричной системе счисления. Оба числа двузначные. В условии данной задачи в двузначном числе старшая цифра может быть и нулем.
В двузначном числе за один ход разрешается заменить любую цифру на сумму цифр по модулю 8 (остаток от деления суммы цифр на 8). Построить цепочку ходов минимальной длины, которая переводит a в b. Если существует несколько цепочек минимальной длины, то выбрать ту из них, в которой сумма всех чисел максимальна (числа a и b являются частью цепочки). В качестве ответа записать сумму чисел в найденной цепочке. Результат записывается в десятичной системе счисления. В случае невозможности построить цепочку вывести число 0.

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

Находясь в агрессивной среде аппарат, снабженный целым комплексом датчиков, мониторит сразу несколько параметров. Необходимо написать программу анализа для параметра F. Этот параметр принимает целые значения. Задан диапазон допустимых значений [X; Y] (границы отрезка тоже являются допустимыми значениями). Каждую минут снимаются показания с датчика F. После выключения оборудования датчик показывает 0. Это значение в серию измерений уже не включается. Необходимо посчитать наибольшее отклонение от допустимых значений и сколько раз за время наблюдения оно было зафиксировано.

Формат входных данных
На первых двух строчках вводятся два целых числа X и Y (X < Y), которые задают диапазон допустимых значений.
На последующих строчках вводятся целые числа (по одному в каждой строке) – показания параметра F, передаваемые аппаратом. Последнее значение 0 – признак выключения аппарата – это значение в показания НЕ включается.
Все числа по модулю не превосходят 1 000.
Гарантируется, что хотя бы один выход из допустимого диапазона значений был.
Формат выходных данных
Два целых числа в одной строке через пробел: максимальное отклонение и количество отклонений на такое значение за время наблюдения.

Примечание
В данном примере 11 измерений. Максимальное отклонение 2 от заданного допустимого диапазона [-4; 11] будет достигнуто 3 раза на значениях -6, 13 и 13
|-6 – (-4)| = |13 – 11| = 2

В сказочном мире Геомаба живут необычные существа в виде прямоугольников. Все они разного размера, но передвигаются все они одинаково –перекатыванием сбоку на бок. В очередной из дней жители Геомаба решиливыбрать себе мэра, так как дороги в их мире очень опасные – в них очень многоям и в них легко застрять, так как жители-прямоугольники могут передвигатьсятолько по плоским дорогам.
Мэр решил незамедлительно собрать группу добровольцев и направить их по дорогам Геомаба, но дорог так много, что Мэр понял, что отправлять добровольцев, а потом вытаскивать их из ям – дело трудозатратное, потому он обратился к Вам за помощью – написать алгоритм, который по размеру прямоугольника покажет все ямы, которые необходимо залатать, чтобы житель-прямоугольник смог спокойно передвигаться по дороге, а город потратил минимально ресурсов (заделал как можно меньше ям).
Прямоугольник считается застрявшим, если он не смог беспрепятственно перекатиться через яму (его угол попал в яму (не включая начало и конец ямы)).
Если прямоугольник попал не углом в яму, а попал точно стороной на границы ямы, то он не считается застрявшим.

Формат входных данных
На вход на первой строке подаётся число X (1 <= X <= 100000) – длина дороги в метрах.
На второй строке подаются числа W, H (1 <= W,H <= 100) – высота и ширина жителя-прямоугольника в метрах соответственно.
На третьей строке подаётся число N (1 <= N <= 1000) – количество ям на дороге.
Далее на N-строках подаются координаты начала ямы (в метрах от начала дороги) и её ширина в виде целых положительных чисел от 1 до X. Координаты ям могут подаваться в любом порядке. Но все ямы не пересекаются и не накладываются.
Формат выходных данных
Выведите на первой строке количество ям, которые необходимо заделать, чтобы житель-прямоугольник, для которого производится расчёт, смог добраться до конца дороги.
Далее выведите координаты всех ям отсортированные в порядке появления от начала дороги до конца, КАЖДУЮ С НОВОЙ СТРОКИ.

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

В данном случае житель может стоять основанием перед началом дороги на стороне 2 (положение №1) или 3 (положение №2).
Если он стоит на основании длиной 2, то он попадёт только в яму под номером 14.
Если он стоит на основании длиной 3, то он попадёт в ямы 10 и 14.
Городу выгоднее заделать только одну яму, под номером 14.

Положение №1.


Положение №2.

 

В школе №1920 решили провести соревнование по написанию небольших игр среди школьников. Первым критерием данного соревнования было условие того, что в игре нельзя заранее рассчитать результат зная входные данные.
Коля написал игру, в которой задаётся квадратная матрица, состоящая из целых чисел, но не содержащая нулей. Суть игры в том, что в неё играют два участника и каждый может сделать одно из следующих действий:
1.Повернуть матрицу на 90 градусов по часовой стрелке
2.Повернуть матрицу на 90 градусов против часовой стрелке
3.Повернуть матрицу на 45 градусов по часовой стрелке (если есть нули,то они схлопываются (см. пример))
4.Повернуть матрицу на 45 градусов против часовой стрелке (если естьнули, то они схлопываются (см. пример))
У игроков есть ограниченное чётное количество ходов. Каждый из игроков ходит по очереди. Победой в игре считается сумма чисел на ближайшей стороне матрицы, которая находится ближе к игроку. Если матрица в конце повёрнута на 45 градусов, то результатом берётся ближайший угол матрицы к каждому из игроков (одно число в вершине).
Помогите Коле написать алгоритм, который будет по входной матрице и порядку действий ребят определять сколько очков набрал игрок №1 и игрок №2.
Поворот квадратной матрицы на 45 градусов по часовой стрелке будет выглядеть следующим образом.

Формат входных данных
На вход первой строкой подаются число N (1 <= N <= 1000) – размер исходной сгенерированной квадратной матрицы (N – количество строк). Далее на N строках подаются по N целых чисел (кроме нуля).
Далее подаётся число K (2 <= K <= 100, K – чётное)– количество ходов у игроков.
На последующих K-строках вводятся команды, которые выбрали ребята (от 1 до 4), где первая команда соответствует первому игроку (сидящему слева), следующая команда второму (сидящему справа) и так далее.
Формат выходных данных
Вывести на одной строке через пробел результат игры для первого игрока и для второго.

Примечание:

1	2	3
4	5	6
7	8	9

1 команда (повернуть на 90 градусов по часовой стрелке)

7	4	1
8	5	2
9	6	3

2 команда (повернуть на 45 градусов по часовой стрелке)

0	0	7	0	0
0	8	0	4	0
9	0	5	0	1
0	6	0	2	0
0	0	3	0	0

3 команда (повернуть на 90 градусов по часовой стрелке)

0	0	9	0	0
0	6	0	8	0
3	0	5	0	7
0	2	0	4	0
0	0	1	0	0

4 команда (повернуть на 45 градусов против часовой стрелке (нули схлопываются))

9	8	7
6	5	4
3	2	1

Первый игрок находится слева, значит ячейки, которые идут ему в счёт 9 + 6 + 3.
Для второго игрока справа 7 + 4 + 1.
 

В школе в очередной раз заболел преподаватель физкультуры Виктор Дмитриевич. Поэтому директор принял решение, что кто-то из свободных учителей проведёт занятие. После долгих размышлений, самым свободным оказался учитель информатики Анатолий Иванович, который очень любит алгоритмы сортировки, что вызвало сразу проблему у учеников. Ведь Анатолий Иванович первым делом сказал ребятам построиться в шеренгу, но не как обычно (по убыванию роста, ), а так, чтобы каждое нечётное место было отсортировано по росту по убыванию (первое место - самый высокий ученик, третье место выше пятого, пятое выше седьмого и так далее)), а каждое чётное по возрастанию (второе место - самый низкий ученик, четвёртый второй по росту среди всех, шестой - третий по росту среди всех и так далее) (учеников Анатолий Иванович нумеровал с 1).
Помогите ученикам получить правильный порядок, как встать им в шеренгу так, чтобы Анатолий Иванович оказался доволен.
Формат входных данных
На первой строке подаётся число N (1 <= N <= 121)– количество учеников в классе.
На N последующих строках подаются строки вида имя-рост (например, «Ivan 175»), где на первом месте указывается имя ученика – оно всегда одним словом на английском языке, без пробелов, а в конце указывается рост ученика (целое число от 100 до 220).
Формат выходных данных
Выведите имена учеников в одну строку через пробел, как они должны встать на уроке физкультуры.
Примечание:
Имена учеников у всех уникальны, рост ни у кого не повторяется.

В королевстве Полерам расположен длинный линейный сад из N деревьев, стоящих в один ряд (по порядку с запада на восток). У каждого дерева i (нумерация от 1 до N) имеется некоторый урожай a_i — количество собранных яблок (целое число, может быть положительным, нулевым или даже отрицательным, если учитывать затраты или потери).
Королевский интендант хочет упаковывать собранный урожай в большие ящики, рассчитанные ровно на K яблок. Для удобства он рассматривает непрерывные отрезки деревьев [L,R] и проверяет, делится ли сумма (a_L )+ (a_L+1) + … + (aR) на K без остатка. Если делится, то такой отрезок можно упаковать в ящики без недогруза и перегруза.
Требуется найти общее количество таких отрезков [L,R], для которых сумма урожая деревьев на этом участке кратно K, количество яблонь нечётное, а количество собранных яблок - положительное число.
Примечание:
В отрезке [L, R] должно быть выполнено неравенство 1<= L <= R <= N.
Формат входных данных
Первая строка: два целых числа N и K, (1 <= N <= 200000, 1 <= K <= 10⁶).
Вторая строка: N целых чисел a₁, a₂, …, a_N (-10⁶ <= a_i <= 10⁶).
Формат выходных данных
Выведите одно число — количество всех пар (L, R) для которых (a_L )+ (a_L+1) + … + (a_R) делится без остатка на K, количество яблонь нечётное, а количество собранных яблок - положительное число.

Пояснение: в данном примере есть четыре последовательности: (1 + 2), (1 + 2 + 3), (3), (6), в данном случае все с положительным количеством собранных яблок, но только 3 с нечётным количеством яблонь.

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


Примечание:

• дома могут находиться как по разные стороны пруда, так и поодну;
• требуется рассчитать ответ с точностью до десятых (если ответполучился целый, то выводить всегда после запятой один знак);
• передвигаться можно только по прямым, но не дугам;
• стороны пруда всегда параллельны осям OX и OY;
• точки, обозначающие дома могут лежать на границе пруда, и передвигать по границе пруда разрешено. 

Формат входных данных
На первой строке подаются параметры пруда через пробел a, x1, y1 (1 <= a <= 1000; -1000 <= x1,y1 <= 1000), где x1,y1 – координаты левого верхнего угла пруда.
На второй строке подаются координаты дома Маши в виде точки xm, ym (-1000 <= xm, ym <= 1000).
На третьей строке подаются координаты дома Саши в виде точки xs, ys (-1000 <= xs, ys <= 1000).
Все числа - целые.
Формат выходных данных
Выведите на одной строке самое кратчайшее расстояние, которое можно пройти от дома Маши к дому Саши. Ответ представляет собой всегда вещественное число с одним знаком после запятой. Если ответ получился больше, то округлить до одного знака после запятой (было 4.5764, стало 4.6).

 

В мире двоичных чисел решили разобраться, почему некоторые числа не дружат друг с другом, потому после ряда проведённых экспериментов было выявлено, что точно не дружат друг с другом те числа, которые нельзя поставить рядом так, чтобы в их последовательности не было двух и более единиц подряд, а также не было трёх и более нулей подряд.
Помогите понять жителям двоичного мира, сколько пар чисел от 1 до N нельзя точно никак подружить.
Например: есть два числа 4 и 5, в двоичной системе счисления они представлены как 100 и 101. Если их поставить как 101 и 100, получится 101100, что даёт две единицы подряд в строке, значит дружить они не будут, но если поставим наоборот 100 и 101 = 100101, то двух единиц подряд нет, а также нет трёх и более нулей подряд, значит числа могут подружиться.
Формат входных данных
На первой строке подаётся число N (1 <= N <= 10⁵) – количество чисел в двоичном мире от 1 до N (включительно).
Формат выходных данных
Вывести на первой строке количество пар чисел, которые никак нельзя будет подружить друг с другом. Рассматриваются все числа от 1 до N, но все числа уникальны, потому не рассматриваются пары одинаковых чисел и повторяющиеся пары (если нельзя подружить число x с числом y, то пара (x, y) и (y, x) считается одной парой чисел).

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

• 1 + 1 = 0
• 1 + 0 = 1
• 0 + 1 = 0
• 0 + 0 = 1

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

Формат входных данных
На первой строке подаётся первое слагаемое – двоичное число без значащих нулей длины N (1 <= N <= 10⁵).
На второй строке подаётся второе слагаемое – двоичное число без значащих нулей также длины N.

Формат выходных данных
Вывести на первой строке результат суммы двух двоичных чисел. Если в результате есть незначащие нули, то выводить без них. Если получился 0, то вывести просто 0.

Алгоритм вычисления функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = n, если n < 11,
F(n) = n + F(n­ –1), если n ≥ 11

По заданным числам A и B вычислите значение выражения F(A) – F(B)?

Входные данные
А и B вводятся с клавиатуры (2000 <= A, B <= 5000). Каждое число в отдельной строке.

Выходные данные
Выведите ответ на задачу.
 

Примеры

№	Входные данные	Выходные данные
1	2023 2007	32248

Злым числом в математике называется неотрицательное целое число с чётным числом единиц в его двоичной записи (например, число 5 — злое, в его двоичной записи две единицы). Они используются в теории чисел при исследовании последовательности Морса–Туэ и применяются в алгоритмах фрактального сжатия изображений. Натуральное число будем называть очень злым, если само оно чётное и количество единиц в его двоичной записи также чётное. Это такие числа, как 6, 10, 12, 18, 20 и так далее. По данному n определите количество очень злых чисел, не превосходящих n.

Формат входных данных
Единственная строка входного файла содержит натуральное число n (1 ≤ n ≤ 10⁹ ).

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

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

Формат входных данных
Первая строка входных данных содержит целое число N, вторая строка — целое число K (1 ≤ N ≤ 10⁹ , 1 ≤ K ≤ N).
Формат выходных данных
В первой строке выведите «Yes», если заявление с номером K будет подписано, и «No», если оно будет выброшено. Во второй строке выведите номер шага, на котором это произойдёт.

Замечание
В первом примере из условия в стопке находятся 4 заявления: (1, 2, 3, 4). Заявление 1 подписывается, заявление 2 выкидывается, заявление 3 перекладывается в конец. После выполнения трёх шагов в стопке будут заявления (4, 3). Поэтому на пятом шаге заявление 3 будет выброшено.
Во втором примере из условия стопка имеет вид (1, 2, 3, 4, 5). После выполнения трёх шагов стопка будет иметь вид (4, 5, 3). За следующие три шага заявление 4 будет подписано, заявление 5 будет выброшено, а заявление 3 — переложено в конец стопки (в которой ничего не будет, кроме заявления 3). Поэтому после шести шагов стопка будет иметь вид (3). На седьмом шаге заявление 3 будет подписано.

Тимофею на день рождения родители подарили металлоискатель. Естественно, наутро мальчик отправился на поиски клада. Он предположил, что когда-то давно кто-то мог обронить золотую монету на древней прямой дороге и для облегчения поиска придумал систему координат. Ось абсцисс OX направлена вдоль дороги, а ось ординат OY направлена вверх.
Устройство работает следующим образом: на его индикаторе выставляется натуральное число r и если ровно на этом расстоянии имеется золотой предмет, то загорается зелёная лампочка.
Сначала юный кладоискатель выставил число r1 в точке x = 0, затем отошёл в точку с абсциссой x = a и выставил число r2, как показано на рисунке. Новичкам везёт, оба раза загорелась зелёная лампочка. Определите координаты потерянной когда-то давно золотой монетки.

Формат входных данных
Программа получает на вход три целых числа a, r1 и r2, записанных в отдельных строках (1 ≤ a, r₁, r₂ ≤ 10⁹ ).
Формат выходных данных
Выведите в двух строках два числа – координаты сокровища (сначала — абсциссу, потом — ординату). Значение ординаты должно быть не положительным (монетка не может висеть в воздухе). Гарантируется, что входные данные таковы, что ответ существует и обе координаты монеты будут целыми числами.

Замечание
Рисунок соответствует примеру из условия.

В деревне Летовецк, где живут мудрые старцы и их ученики, существует древний банк, который хранит богатства в виде ле́токоинов — особых монет, обладающих магической силой. Однако банк установил строгие правила: чтобы снять деньги, нужно использовать только определённые суммы за одну операцию:

• за одну операцию можно снять только 1 ле́токоин,

• за одну операцию можно снять сумму 6^x, где x  - любое натуральное число (можно снять сумму равную 6, 36, 216, и т.д.),

• за одну операцию можно снять сумму 9^x, где x  - любое натуральное число  (можно снять сумму равную 9, 81, 729, ...).

Старец Летовец спросил своих учеников: за какое минимальное количество операций вы сможете снять ровно N ле́токоинов?

Примечание: невозможно повторно вносить снятые деньги в банк!

Формат входных данных
На вход подается целое число N (\(1<=N<=100000\)).

Формат выходных данных
Выведите ответ на задачу.

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	127	4	При снятии 1 + 9 + 36 + 81 получится снять 127 летокоинов за 4 операции.
2	3	3	1+1+1 = 3, всего 3 операции
3	44852	16

 

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

Замок на двери подвала устроен следующим образом:

• на нем есть два кодовых механизма, первый из которых изначально указывает на число \(a\), а второй — на число \(b\);

• первый кодовый механизм сломан, поэтому изменить значение \(a\) нельзя;

• второй кодовый механизм можно вращать только в одном направлении, тем самым увеличивая значение \(b\);

• замок открывается тогда и только тогда, когда существует целое число \(d > 1\), делящее и \(a\), и \(b\) (иными словами, когда у \(a\) и \(b\) есть общий делитель больше единицы).

За одну секунду Эрен может повернуть второй кодовый механизм так, что \(b\) увеличится ровно на \(1\). Определите, за какое минимальное время Эрен сможет открыть подвал.

Формат входных данных
В первой строке дано единственное целое число \(t\) — количество тестовых случаев \((1 \leqslant t \leqslant 1000)\).

В \(i\)-й из следующих \(t\) строк через пробел даны два целых числа \(a_i\) и \(b_i\) — начальные значения, на которые указывают кодовые механизмы в \(i\)-м тесте (\(2 \leqslant a_i, b_i \leqslant 10^9\)).

Формат выходных данных
Для каждого теста выведите в отдельной строке минимальное время, за которое Эрен откроет подвал.

 

Новая татарская игра <<2026>> ведется на прямоугольной клетчатой доске, состоящей из \(m\) строк и \(n\) столбцов. Доска разбита на \(m \times n\) единичных клеток размером \(1 \times 1\). На некоторых клетках стоят квадратные фишки размером \(1 \times 1\), на каждой фишке написана одна из \(26\) английских букв.

С фишками производятся \(q\) операций. Каждая операция состоит в перемещении всех фишек до упора в одном из четырех направлений. Таким образом, последовательность операций задается строкой \(s\) длины \(q\), состоящей из символов, соответствующих направлениям: <<L>> — влево, <<R>> — вправо, <<U>> — вверх и <<D>> — вниз.

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

Определите, как будет выглядеть доска после выполнения всех операций.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке теста задано целое число \(t\) — количество наборов входных данных в тесте (\(1 \le t \le 200\,000\)). Далее следуют описания наборов входных данных. Каждый набор входных данных описывается следующим образом:

В первой строке набора заданы целые числа \(m\) и \(n\) — размеры доски (\(1 \le m, n \le 10^6\), \(1 \le m\times n \le 10^6\)).

В следующих \(m\) строках задано изначальное расположение фишек на доске.

В \(i\)-й строке (\(1 \le i \le m\)) находится строка \(a_{i1}a_{i2}\ldots a_{in}\) длины \(n\), задающая \(i\)-ю строку доски. Каждый символ \(a_{ij}\) является либо строчной буквой английского алфавита от <<a>> до <<z>>, либо точкой <<.>>. Если \(a_{ij}=\mbox{<<.>>}\), то клетка в \(i\)-й строке и \(j\)-м столбце является пустой, иначе в ней находится фишка, на которой написана буква \(a_{ij}\).

В последней строке заданы \(q\) символов \(s_1s_2\ldots s_q\) без пробелов, задающие последовательность операций (\(1 \le q \le 10^6\)). Каждый символ \(s_i\) является одним из символов <<L>>, <<R>>, <<U>> или <<D>>.

Сумма значений \(m \times n\) по всем наборам входных данных не превышает \(2\cdot 10^6\). Сумма значений \(q\) по всем наборам входных данных не превышает \(2\cdot 10^6\).

Формат выходных данных
Для каждого набора входных данных выведите итоговое расположение фишек на доске после выполнения всех операций в том же формате, что и во входных данных.

Обозначим через \(\sum mnq\) сумму \(mnq\) по всем наборам входных данных.

Обозначим через \(\sum mq\) сумму \(mq\) по всем наборам входных данных.

Назовем расположение фишек лестницей, если \(m=n\), \(a_{ij}={<<\texttt{.}>>}\) для всех \(1 \le i \le j \le n\) и \(a_{ij}\ne{<<\texttt{.}>>}\) для всех \(1 \le j < i \le n\). Иными словами, все фишки находятся на клетках ниже главной диагонали доски, и на каждой клетке ниже главной диагонали есть фишка.

Пояснения к примерам
В первом наборе входных данных из примера доска изначально выглядит так:

Первая операция сдвигает все фишки влево, так как \(s_1={<<\texttt{L}>>}\). После ее выполнения доска будет выглядеть следующим образом:

Вторая операция сдвигает все фишки вправо, так как \(s_2={<<\texttt{R}>>}\). После ее выполнения доска будет выглядеть следующим образом:

Третья и последняя операция сдвигает все фишки наверх, так как \(s_3={<<\texttt{U}>>}\). После ее выполнения доска будет выглядеть следующим образом:

Напишите программу на Python, которая:

1. Считывает уравнение из строки.

2. Преобразует строку в символьное уравнение с помощью SymPy.

3. Решает уравнение.

4. Выводит корни уравнения.