Однажды Максим поспорил, что сможет придумать задачу с самым коротким условием, способную растрогать любого. Он выиграл спор:

«По заданным числам $$$n$$$ и $$$p$$$ посчитайте количество возможных пар ($$$a, b$$$), таких что $$$a + b = n$$$ и $$$-10^{p} \le a, b \le 10^{p}$$$.»

Никита и Максим оценивают сложность задач. Каждая задача характеризуется длиной условия $$$x$$$ и длиной кода-решения $$$y$$$. Никита предполагает, что сложность задачи определяется как $$$x^{y}$$$, а Максим считает, что сложность задачи это $$$y^{x}$$$.

Помогите ребятам понять какое отношение имеют оценки сложности $$$x^{y}$$$ и $$$y^{x}$$$.

Максим большой любитель всевозможных игр. В этот раз он играет в игру под названием «Minecraft».

В этот раз ему пришла отличная идея построить огромную мишень и потренироваться стрельбе из лука. По задумке Максима мишень будет выглядеть как квадрат с четной стороной $$$x$$$ и каждый внутренний слой покрашен или в белый или в красный цвет, при этом цвета должны чередоваться (для лучшего понимания смотрите картинку):

Пример мишени $$$8 \times 8$$$.

Пример мишени $$$4 \times 4$$$.

Также Максим хочет сделать эту мишень из шерсти, однако у него не так много шерсти красного цвета, а именно $$$n$$$ блоков. Помогите Максиму выяснить какая максимальная сторона $$$x$$$ может быть у его мишени!

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

К примеру, Маша хочет взять пирожок $$$3, 6, 9, 12, 15, 18, 21, 24$$$ и так далее, а Петя $$$7, 14, 21, 28...$$$ Внуки берут пирожки по очереди, начиная слевой стороны духовки. Маша начинает первой брать пирожки. Если один из внуков взял уже пирожок под номером $$$x$$$, то другой берёт следующий. Например, Петя возьмет третий пирожок под номером $$$21$$$. Следовательно, когда Маша будет брать свой седьмой пирожок, она возьмёт пирожок под номером $$$24$$$.

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

В вашем распоряжении $$$k$$$ серверов, на этих серверах хранится информация, ее можно представить в виде массива из $$$n$$$ элементов. В изначальный момент времени вся информация на всех $$$k$$$ серверах одинаковая, вам она будет дана в виде массива $$$a$$$. Также в некоторые моменты времени к серверам поступают запросы, запросы бывают двух типов:

• «Set sid pos val» – изменить информацию на sid-м сервере в позиции pos на значение val.
• «Get sid pos» – получить значение на sid-м сервере в позиции pos.

Вы бы хотели создать такую систему, которая позволит быстро обрабатывать все эти запросы. Но это еще не все, также вы бы хотели настроить синхронизацию между всеми серверами раз в $$$s$$$ секунд, то есть каждые $$$s$$$ секунд серверы обмениваются информацией и обновляются так, что между данными двух различных серверов нет различий. Конфликты, которые возникают при синхронизации, должны устраняться в автоматическом режиме следующим образом: допустим на серверах в позиции $$$i$$$ находятся разные значения, тогда при синхронизации для обновления будет выбрано то значение, которое было позже обновлено, то есть если на сервере $$$x$$$ в $$$i$$$-й позиции значение было изменено в момент времени $$$t_{1}$$$, а на сервере $$$y$$$ в $$$i$$$-й позиции в момент $$$t_{2}$$$ и при этом $$$t_{1} \gt t_{2}$$$, то будет выбрано значение на сервере $$$x$$$.

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

Студенты ВГУ не только участвуют в различных соревнованиях по программированию, но и посещают музеи. В этот раз в очередном городе Никита предложил сходить в музей изобразительных искусств. Из всех представленных картин ему больше всего понравились работы Ивана Шишкина. Вдохновлённый великим русским живописцем, Никита решил нарисовать свой шедевр в виде ASCII рисунка. Для того чтобы ASCII рисунок был шедевром, в нём должно быть следующее:

1. Рисунок обрамлён прямоугольной рамкой, которая состоит из символов '+' по углам, '-' на горизонтальных границах и '|' на вертикальных границах.
2. На рисунке изображено $$$n$$$ деревьев. Каждое дерево состоит из ствола и кроны, которые задаются параметрами $$$s_{i}$$$ и $$$t_{i}$$$. Ствол дерева состоит из $$$s_{i}$$$ символов '|', при этом самая нижняя часть ствола обязательно рисуется от нижней границы рамки. Деревья бывают трёх видов в зависимости от символа, из которого состоит крона дерева. Крона дерева представляет из себя равнобедренный треугольник с высотой $$$t_{i} + 1$$$ и основанием $$$2 \cdot t_{i} + 1$$$, который граничит с верхней частью ствола и состоит из одинаковых символов $$$c$$$. Ствол дерева при этом находится ровно посередине основания треугольника кроны. В зависимости от типа дерева символ $$$c$$$ равен '*', '+' или '#'. Для лучшего понимания, как рисуется дерево, обратите внимание на рисунок.
3. Каждое дерево полностью помещается на рисунке, то есть рисунки деревьев и границы рамки не пересекаются, но могут касаться.
4. Если два любых дерева касаются кронами, то они должны быть разных видов. Деревья $$$x$$$ и $$$y$$$ касаются кронами, если существует символ кроны, принадлежащий дереву $$$x$$$, у которого есть соседний по стороне символ кроны, принадлежащий дереву $$$y$$$.
5. Прямоугольная рамка рисунка имеет минимальный периметр.
6. Символы внутри рамки, которые не принадлежат ни одному из деревьев, – пробелы (то есть символ с ASCII кодом $$$32$$$).

Правильные рисунки деревьев.

Неправильные рисунки деревьев.

По заданным $$$n$$$ деревьям скажите, как будет выглядеть шедевр Никиты!

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

Маша и её бабушка играют в кости. Девочка подбрасывает кубик и говорит число, оказавшееся на нем. Бабушка очень стара и плохо видит, но всё слышит. Маша может исказить результат любого броска кости. Например, если выпало на кубиках $$$2$$$, а Маша сказала, что $$$5$$$, то результатом будет $$$5$$$. Однако, если бабушка слышит подряд три шестёрки, то она берёт лупу и проверяет только последний бросок, после этого количество подряд идущих шестерок сбрасывается.

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

Это интерактивная задача.

Вы же любите проходить тесты, так?

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

• Менее $$$50\%$$$ правильных ответов – оценка $$$2$$$.
• От $$$50\%$$$ до $$$69\%$$$ правильных ответов – оценка $$$3$$$.
• От $$$70\%$$$ до $$$89\%$$$ правильных ответов – оценка $$$4$$$.
• От $$$90\%$$$ правильных ответов – оценка $$$5$$$.

Оценки $$$3, 4, 5$$$ являются удовлетворительными.

Тест можно проходить максимум $$$3$$$ раза.

Пройдите тест на удовлетворительную оценку!

После того, как вы считали $$$n$$$, вы можете начать попытку. Для этого выведите: «Start test» на новой строке.

После того как началась попытка, вам будут подаваться вопросы. Каждый вопрос состоит из трех строк. В первой строке находится описание вопроса, во второй – первый вариант ответа, на третьей – второй вариант ответа. Для каждого вопроса вы должны вывести на новой строке «A», если вы выбрали первый вариант ответа, или «B», если второй.

Обратите внимание, что следующий вопрос вы получите только после того, как выберете вариант для текущего. После того, как вы ответите на $$$n$$$-й вопрос, вам необходимо считать строку – результат за текущую попытку, строка имеет формат «Your result: mark», где mark – ваша оценка. Если эта оценка удовлетворительная, то более ничего делать не нужно, и ваша программа должна завершиться. В противном случае вы можете начать следующую попытку, если еще не превысили лимит.

Обратите внимание, что начать попытку вы можете максимум $$$3$$$ раза. Если же вы превысите лимит попыток, то следующая строка, которую вы считаете, будет «Attempts exceeded». В таком случае ваша программа должна немедленно завершиться. Также, если вы сделаете некорректный выбор или выведете не то, что ожидает система, то в ответ вы получите «Incorrect output», и ваша программа должна завершиться.

Гарантируется, что все тесты состоят только из ASCII символов с кодами от $$$32$$$ до $$$126$$$, а также что длина любой строки не превышает $$$256$$$ символов.

После любого вывода не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

• fflush(stdout) или cout.flush() или std::endl в C++;
• System.out.flush() в Java;
• flush(output) в Pascal;
• stdout.flush() в Python;
• смотрите документацию для других языков.

У вас есть число $$$x$$$. Это число слишком большое, вы хотели бы записать его в сокращенной форме. Для однозначности вы решили ввести правила сокращения любого неотрицательного числа следующим образом:

• Сокращенная форма числа состоит из не более чем $$$4$$$ символов.
• Если число $$$x \lt 1000$$$, то его сокращенная форма совпадает с полной, иначе сокращенная форма состоит из числа $$$a$$$ (возможно вещественного) и латинского символа $$$c$$$ (одного из K, M, B), обозначающего степень десятки: K – тысяча, M – миллион, B – миллиард. Значением сокращенной записи назовем число $$$y$$$, равное $$$a$$$, умноженному на соответствующую степень десятки, в зависимости от символа $$$c$$$.
• Цифры сокращенной формы совпадают с первыми цифрами полной формы.
• Из всех возможных вариантов сокращенной формой $$$x$$$ является та, чье значение не превосходит $$$x$$$ и наиболее близко к $$$x$$$. Если таких форм несколько, то выбирается наиболее короткая (см. примеры).

Запишите число в его сокращенной форме!

Максим большой любитель всевозможных игр. В этот раз он играет в игру под названием «Heroes of might and magic III».

Каждый сценарий в ней играется на определенной карте, которая представляет собой прямоугольник из $$$n \times m$$$ клеток. Каждая клетка имеет свой тип ландшафта, например «трава», «болото», «песок» и т.д. Визуально, некоторые клетки с одинаковым типом ландшафта образуют компоненты связности$$$^{\ast}$$$. Этих компонент может быть много, однако Максиму нравятся сценарии, где на карте есть не более двух типов ландшафтов и суммарное количество компонент связности в точности равно $$$k$$$.

Вы, как самый опытный картостроитель, пообещали придумать карту, которая понравится Максиму. Сможете ли вы сдержать это обещание?

Компонента связности$$$^{\ast}$$$ – это связная область таблицы, состоящая из одного и того же символа, а также для любой пары клеток $$$(x_{1}, y_{1})$$$, $$$(x_{2}, y_{2})$$$, принадлежащих этой области, существует путь из $$$(x_{1}, y_{1})$$$ в $$$(x_{2}, y_{2})$$$$$$^{\ast}$$$, состоящий только из клеток этой связной области.

Путь в таблице из $$$(x_{1}, y_{1})$$$ в $$$(x_{2}, y_{2})$$$$$$^{\ast}$$$ – это последовательность клеток, которая начинается в $$$(x_{1}, y_{1})$$$, заканчивается в $$$(x_{2}, y_{2})$$$ и любые две рядом стоящие клетки в этой последовательности являются соседними по стороне.

Вам дана строка $$$s$$$, состоящая из $$$n$$$ маленьких латинских букв. Вы бы хотели найти ее ключевую анаграмму порядка $$$k$$$. Ключевая анаграмма порядка $$$k$$$ – это лексикографически минимальная строка $$$t$$$ длины $$$k$$$, которая получается из некоторой подстроки исходной строки $$$s$$$ путем перестановки букв в ней. Другими словами, ключевая анаграмма порядка $$$k$$$ это лексикографически минимальная анаграмма какой-то подстроки длины $$$k$$$ исходной строки $$$s$$$.

Напоминаем, что строка $$$a$$$ лексикографически меньше строки $$$b$$$, если и только если выполняется один из следующих пунктов:

• $$$a$$$ – префикс $$$b$$$, но $$$a \neq b$$$;
• в первой позиции, где $$$a$$$ и $$$b$$$ различны, в строке $$$a$$$ находится буква, которая встречается в алфавите раньше, чем соответствующая буква в $$$b$$$.

Это интерактивная задача.

Мы загадали прямую в виде $$$y = kx + b$$$. Ваша задача отгадать эту прямую.

Вы можете делать запросы, в одном вопросе вы указываете точку ($$$x, y$$$) и получаете в ответ кратчайшее расстояние от точки до прямой.

Сможете ли вы справиться не более чем за $$$5$$$ запросов?

Вы можете сразу начать делать запросы. Чтобы это сделать, выведите:

• «? x y» ($$$-100 \le x, y \le 100$$$)

на отдельной строке. После вывода запроса считайте неотрицательное вещественное число $$$d$$$ с точностью до $$$20$$$ знаков – кратчайшее расстояние от данной вами точки до прямой. Если вы сделаете некорректный запрос или превысите установленный лимит в $$$5$$$ запросов, то в ответ вы получите число $$$-1$$$, в таком случае ваша программа должна немедленно завершиться.

Чтобы вывести ответ, выведите

• «! k b»

на отдельной строке. Ваш ответ будет считаться правильным, если относительная или абсолютная погрешность коэффициентов $$$k$$$ и $$$b$$$ будет не более $$$10^{-3}$$$.

После любого вывода не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

• fflush(stdout) или cout.flush() или std::endl в C++;
• System.out.flush() в Java;
• flush(output) в Pascal;
• stdout.flush() в Python;
• смотрите документацию для других языков.