Шахматное поле в общем случае — это квадратное поле размера $$$n \times n$$$, где каждый квадрат $$$1 \times 1$$$ раскрашен в белый или в черный цвет, левый верхний угол покрашен в черный. Каждый квадрат граничит по стороне с квадратами других цветов. Сколько на поле белых квадратов?

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

Злой гений имеет n конфет. Он хочет позвать на встречу $$$m$$$ друзей, и поделиться с ними конфетами поровну, чтобы после деления осталось ровно $$$k$$$ конфет. Процесс деления происходит следующим образом: Все друзья встают в круг, он дает по одной конфете каждому начиная с 1-го по $$$m$$$-го. Если конфет больше или равно $$$m$$$, он продолжает этот процесс. В итоге у него останется сколько-то конфет. Гений хочет, чтобы у него осталось ровно $$$k$$$ конфет. Гарантируется, что злой гений не жадный, то есть $$$n \gt k$$$.

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

Так бывает, что два очень ожидаемых блокбастера выходят в один и тот же день. Вот и в этот раз в кинотеатрах одновременно начинают показывать два легендарных, но очень разных фильма: «Борби» и «Опергеймер». У Руслана выдался редкий выходной как раз в день этой премьеры.

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

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

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

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

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

IT-парк ПетрГУ – это странный архитектурный комплекс, который представляет собой $$$n+1$$$ кабинетов, соединённых между собой проходами. Известно, что:

• между двумя кабинетами не может быть больше одного прохода;
• из каждого кабинета можно попасть в каждый другой, возможно проходя сквозь другие кабинеты;
• по IT-парку из-за планировки не получится ходить кругами: если идти из кабинета КТП в какой-то другой кабинет, обратно идти получится ровно по тем же самым кабинетам и никак иначе.

Итак, руководитель КТП находится в кабинете под номером $$$b_1$$$ и должен посетить другие кабинеты с номерами $$$b_2, ..., b_m$$$ без какого-то определённого порядка и вернуться обратно в кабинет $$$b_1$$$ как можно быстрее.

Сколько времени у него на это уйдёт, если переход между кабинетами занимает одну единицу времени?

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

Дональ Дак — ничем не примечательный селезень, за исключением того факта, что его дядя — сам Скрудж МакДак! Дядя постоянно берет своего племянника в путешествия, делится секретами и весело проводит время.

И вот однажды, они отправились в Южную Америку в поисках легендарного топаза «Акрукс». Многие думали, что этот камень давно погребен вместе с храмом в тернистых зарослях Амазонки. Но им крайне повезло найти его целым и невредимым в усыпальнице одного из еле доживших храмов. Помимо топаза, усыпальница была набита золотом, украшениями и загадочными устройствами, среди которых, Дональд приметил нечто, похожее на подзорную трубу. Но только наши герои забрали топаз с его законного места, как все затряслось, посыпались стены, пошли трещины и усыпальница, вместе со Скруджем и Дональдом, провалилась вниз...

Рис.1: механизм и наши герои.

Придя в себя, они увидели странный механизм, состоящий из круговых сегментов. В каждом сегменте было две стеклянные трубы, направленные в центр, и если представить обе трубы как отрезки, то они лежат на одной прямой. Помимо этого, сегменты можно было поворачивать с помощью рукояток. В месте, куда они сужались, плотно сидел «Акрукс», заливая комнату голубым светом. Помимо этого, топаз наполнил светом и трубки, соединенные с ним. Скрудж догадался, что им надо соединить все трубки в одну длинную, поворачивая части. Однако Скруджа будто прокляли — на него с неба начали падали кирпичи, попадая точно туда, где он был. Дядя был был бессилен, и только племянник мог что-то сделать.

Дональд вспомнил, что ранее он нашел особенную подзорную трубу с выгравированным числом $$$Q$$$. Посмотрев через неё на механизм, он увидел, что к $$$i$$$-му сегменту было приписано число $$$a_i$$$ — угол наклона прямой, содержащей трубки $$$i$$$-го сегмента. Дональд принялся думать, в надежде найти оптимальное решение и как можно скорее спасти дядю.

В своей голове, Дональд представил механизм как $$$N$$$ прямых, проходящих через начало координат, где $$$i$$$-я прямая обозначала $$$i$$$-й сегмент механизма и имела угол наклона $$$a_i/Q$$$ градусов. Дональд хочет найти такую прямую, что если к ней поворачивать все прямые, то сумма углов поворота будет минимальна. В качестве угла поворота конкретной прямой Дональд берет минимум из разницы углов поворота по часовой стрелке и против.

Рис.2: поворот всегда идёт по меньшему углу. Например, если мы поворачиваем прямую B к A, то мы будем поворачивать по меньшему углу $$$\alpha$$$ против часовой стрелки.

Мы предлагаем Вам побывать в голове Дональда и помочь решить эту задачу. Помогите им собрать механизм и сбежать из храма!

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

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

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

Имеется $$$n$$$ попарно различных натуральных чисел $$$p_1, \, p_2, \, \dots, \, p_n$$$ и $$$n$$$ натуральных чисел $$$c_1, \, c_2, \, \dots, \, c_n$$$.

Рассмотрим строку $$$s$$$ состоящую из цифр. Рассмотрим некоторое её разбиение на $$$k$$$ непустых подстрок: $$$s = t_1 + t_2 + \ldots + t_k$$$. Никакая $$$t_j$$$ не должна содержать ведущих нулей. Красотой подстроки $$$t_j$$$ назовем максимальное натуральное $$$y$$$, такое что $$$t_j = p_i^x$$$ и $$$y = c_i \cdot x$$$, для некоторого ($$$1 \le i \le n$$$). Если нет такого $$$i$$$, что $$$t_j = p_i^x$$$, то $$$y$$$ полагается равным $$$0$$$.

Изящностью разбиения $$$t_1, t_2, \ldots, t_k$$$ назовем минимальную красоту среди всех $$$t_j$$$.

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

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