У профессора Р. есть записная книжка, в которой он хранит номера телефонов, по которым когда-то звонил. Главная проблема заключается в том, что номера в ней записаны в разных форматах. Так, все городские номера телефонов были записаны без кода города, а мобильные – без указания кода страны либо без восьмёрки в начале номера, причём все городские номера состояли из шести цифр, а мобильные – из десяти либо одиннадцати с восьмёркой в начале.

Профессор решил записать номера следующим образом: городские записать в формате +7(XXXX)XX-XX-XX, где XXXX – код города. Так как сейчас профессор Р. живёт в Ярославле, то код города в его случае будет равен 4852, однако не всё так просто: некоторое время профессор прожил в Майкопе, где все городские номера начинались с цифры 5, причём по счастливой случайности оказалось, что ни один ярославский городской номер в записной книжке Р. не начинался с 5. Для таких номеров кодом города стоит указать число 8772. С мобильными номерами всё проще: они должны быть записаны в формате +7(XXX)XXX-XX-XX.

Помогите профессору Р. – запишите очередной номер в его записной книжке в указанном формате.

Сегодня, придя на пару по дискретной математике, профессор Р. решил рассказать студентам первого курса о генерации QR-кодов.

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

QR-код поддерживает несколько способов кодирования данных, в зависимости от того, какие символы используются: цифровое, буквенно-цифровое, кандзи (китайско-японские иероглифы) и побайтовое кодирование. Так как студенты учатся на первом курсе, профессор Р. решил затронуть только цифровое кодирование. Цифровое кодирование подразумевает использование только цифр от 0 до 9. Сначала требуется создать пустую последовательность бит, которая дальше будет заполняться.

Этот тип кодирования требует $$$10$$$ бит на $$$3$$$ символа. Вся последовательность символов разбивается на группы по $$$3$$$ цифры, и каждая группа (трёхзначное число) переводится в 10-битное двоичное число и добавляется к последовательности бит. Если общее количество символов не кратно 3, то если в конце остаётся 2 символа, полученное двузначное число кодируется 7 битами, а если 1 символ, то 4 битами.

Например, есть строка «12345678», которую надо закодировать. Мы разбиваем её на числа: $$$123, 456$$$ и $$$78$$$, затем переводим каждое из них в двоичный вид: $$$0001111011, 0111001000$$$ и $$$1001110$$$, и объединяем это в один поток: $$$000111101101110010001001110$$$.

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

Незнайка решил открыть кружок по спортивному программированию. Для этого Незнайка сделал огромное количество визиток с qr-кодами и сложил их в одну стопку, забыв исходное напечатанное количество. Чтобы вспомнить, сколько было визиток, Незнайка выполнил $$$k$$$ последовательных действий. Он брал самую маленькую стопку визиток разбивал ее на две стопки по $$$a$$$ и $$$b$$$ визиток таким образом, чтобы в двух получившихся стопках было либо одинаковое количество визиток, либо чтобы количества визиток в стопках отличались ровно на 1 визитку, после чего возвращал эти стопки обратно к остальным. После всех $$$k$$$ действий Незнайка смог посчитать, что в самой маленькой стопке лежит ровно $$$n$$$ визиток.

Помогите Незнайке определить максимальное и минимальное количество визиток в исходной стопке.

В задаче 2 теста, ограничения для которых указаны ниже. Тесты из условия оцениваются в 0 баллов.

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

Также профессор ввёл понятие высоты дерева. Высота двоичного дерева – высота его корневого узла. Дерево из примера имеет высоту 6. Вершины, находящиеся на одной высоте, образуют уровни с первого (корень) по шестой (вершины с номерами $$$3$$$ и $$$5$$$)

На дом студентам была дана следующая задача.

Имеется бинарное дерево, обладающее следующими свойствами:

1. Его высота равна $$$n$$$;
2. На уровнях $$$1 \dots n - 2$$$ у каждой вершины $$$2$$$ сына.

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

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

Для постепенного добавления веществ в химии используются пипетки различных видов. Представьте, что у Вас в наличии есть пипетка, градуированная на $$$ n $$$ одинаковых делений. Жидкость, налитая в пипетку, имеет вязкость $$$ \eta $$$. Для простоты считайте, что все капли, формируемые пипеткой, имеют объём, равный одному делению, а время формирования такой капли описывается формулой $$$ t = \lceil h / \eta \rceil $$$, где $$$ \eta $$$ – коэффициент вязкости; $$$ h $$$ – высота жидкости в пипетке (в делениях) на момент формирования капли; а $$$ \lceil x \rceil $$$ – округление числа $$$x$$$ вверх к ближайшему целому.

Напишите программу, которая по заданным целым величинам $$$ n $$$, и $$$ \eta $$$ вычислит суммарное время, за которое вся жидкость вытечет из пипетки.

В далеком 2094 году в Киберславле, простояв в очереди длиной полквартала, Q покупателей пришли в продовольственный магазин. Здесь на полках расположены товары N типов, каждый из которых стоит a_i крышек. Причём запас товаров в таком профиците, что можно считать количество товаров каждого типа неограниченным.

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

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

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

Саша и Алексей придумали новую игру с камнями и спешат поделиться ею с вами. В начале игры имеются две кучки камней, в одной $$$a$$$ камней, в другой – $$$b$$$. За один ход разрешается взять либо $$$1$$$ камень из меньшей кучки, либо $$$2$$$ из большей. Если в кучках одинаковое количество камней, то разрешается сделать любой из двух возможных ходов. Если осталась одна кучка из $$$1$$$ камня, а вторая пустая, то мы можем взять последний камень. Побеждает тот, кто взял последний камень. Саша и Алексей придумали правила, но не смогли определиться с лучшей стратегией. Помогите им определить, кто победит при оптимальной игре.

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

Не написать задачу после этого было невозможно.

Незнайка приземлился на Луну и находится на 1 платформе. Незнайке предстоит сложный путь до платформы с номером $$$n$$$, чтобы доставить посылку.

На Луне располагается $$$n$$$ платформ, каждая платформа находится на высоте $$$a_i$$$. Гравитация на Луне позволяет Незнайке безопасно прыгать с $$$i$$$-й платформы на $$$j$$$-ю платформу, если разница между номерами платформ не превышает значения $$$d$$$ ($$$|i-j| \leq d$$$) и $$$j$$$-я платформа не более чем на $$$h$$$ ($$$a_j-a_i\leq h$$$) выше $$$i$$$-й платформы.

Помогите Незнайке определить, за какое минимальное количество прыжков он сможет добраться до $$$n$$$-й платформы.

With the introduction of Large Language Models (LLMs), Alex began to actively use them for various purposes: to explain an incomprehensible topic on the subject, make a training plan, and even write a birthday greeting to his friends. To use LLM, you need to write a lead-in called prompt. The aim of the prompt is to explain to the model what is to be done and what is expected as a response. Thus the whole question cannot consist of a prompt only. The prompt usually looks like this:

You work as a proofreader for educational books. Rewrite the following text, correcting grammatical, punctuation, and semantic errors.

Alex's friends also began using LLMs and actively sharing their generation results. Alex decided to make a collection of successful prompts to use them more actively later. A prompt is considered successful if the result of most generations with this prompt is considered successful.

Alex has a set of questions that he and his friends have asked LLM. He came up with the following algorithm to find all the prompts from a set of questions:

1. At the beginning, all questions are divided into two non-empty sequences of words called the prefix and suffix of the string. If you write all the words from the prefix and suffix sequentially with a space, you will get the original question. Then only the prefixes are processed.
2. Next, two random prefixes $$$q_i$$$ and $$$q_j$$$ are taken. If these prefixes have the largest common non-zero prefix $$$q^{*}$$$ such that $$$q_i = q^{*} + q_i^{+}$$$ and $$$q_j = q^{*} + q_j^{+}$$$, then $$$q_i$$$ and $$$q_j$$$ are replaced by $$$q^{*}$$$ and are not processed further (By $$$q+$$$ we mean a non-empty subsequence of words from $$$q$$$).
3. Step 2 is repeated as long as it is possible to replace prefix pairs by the largest common non-zero prefixes.

At the end of this algorithm, we obtain the set of all prompts for the questions.

Help Alex: find all the successful prompts from the questions Alex and his friends asked LLM.

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

Незнайка решил задать собственную последовательность, в которой каждый элемент задаётся формулой $$$a_i=(a_{i-1}+2*a_{i-2}+3*a_{i-3})\% mod$$$, где $$$a_1=1$$$, $$$a_2=1$$$, $$$a_3=2$$$, $$$mod=10^9+7$$$, а символ % обозначает взятие остатка от деления.

Незнайка сильно обрадовался собственной последовательности, однако посчитать, чему равняется $$$n$$$-й элемент, не может. Помогите Незнайке определить $$$n$$$-й элемент.