Задача A. Аргайл ≡

Условие

Аргайл — узор из ромбов или квадратов, расположенных в шахматном порядке и образующих параллельные и поперечные полосы разных цветов. Название происходит от имени шотландского клана Кампбел в графстве Аргайл. Особенную популярность этот орнамент получил в XX веке. Это случилось благодаря компании «Pringle of Scotland», которая стала выпускать элитный трикотаж с орнаментом «Аргайл», после чего он стал визитной картой аристократии. С тех пор узор не выходит из моды. Существует огромное количество цветовых решений этого орнамента. Особенно популярен этот узор на свитерах, жилетах, кардиганах, платьях, шарфах, носках и гетрах, сообщает Википедия.

Определите количество квадратов красного и зелёного цветов на ткани размером n × n.

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

Единственная строка входных данных содержит натуральное число n.

Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64-битный тип данных, например long long в C++, int64 в Free Pascal, long в Java.

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

Выведите в двух строках два неотрицательных целых числа — ответ на вопрос задачи. В первой строке выведите количество квадратов красного цвета, во второй — зелёного.

Ограничения

1 ≤ n ≤ 10⁹

Пояснение к примерам

Смотри рисунок.

Примеры тестов

3

1
1

4

1
4

Задача B. Большой куш Бендера ≡

Условие

Пти-шво (фр. маленькие лошадки) — старинная настольная азартная игра, появившаяся в Европе в XVIII веке. Игра представляла собой своеобразную имитацию скачек на ипподроме: пронумерованные рысаки, прикрепленные к спицам рулетки, вращались по кругу. На таких искусственных лошадей игроками делались ставки. Победителем становился тот из игроков, чья лошадь останавливалась на отметке «Финиш».

В организованном Остапом Бендером подпольном игровом клубе, каждый вечер собираются любители азартных развлечений. Жемчужиной заведения по праву считается копия московского ипподрома с движущимися по кругу игрушечными лошадками. Всего их n и каждая обладает своей угловой скоростью d_i, позволяющей ей за 1 секунду перемещаться по дуге d_i°.

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

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

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

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

Выведите одно натуральное число — порядковый номер лошадки, оказавшейся ближе остальных к линии старта-финиша. Гарантируется, что входные данные таковы, что ответ окажется единственным. Для определённости считайте, что если рысак остановился точно на линии, то он победил.

Ограничения

2 ≤ n ≤ 359

1 ≤ t ≤ 10⁹

1 ≤ d_i ≤ 359

Пояснение к примеру

В примере дано три лошадки. Забег длится 10 секунд, угловые скорости бегунов 25, 40 и 90 соответственно. Смотри рисунок. На момент окончания забега первой лошади до линии финиша останется пробежать дугу 360° − 10 × 25° = 110°. Вторая лошадка сделает один полный круг и остановится на расстоянии до финиша 320°. Третья сделает два полных круга и остановится точно на середине дорожки (180°). Победит первая лошадь, для неё угловое расстояние до финиша наименьшее.

Примеры тестов

3
10
25
40
90

1

Задача C. Взвешивание матрёшек ≡

Условие

У Тимофея есть набор матрёшек, пронумерованных последовательными числами от 1 до n. Вес каждой матрёшки равен её номеру и любую матрёшку с номером a можно спрятать в матрёшку с номером b, если a < b.

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

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

Первая строка входных данных содержит натуральное число n — количество матрёшек у мальчика и одновременно номер матрёшки, стоящей на левой чаше весов. Вторая строка содержит натуральное число m — номер матрёшки, стоящей на правой чаше весов.

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

Выведите True или False — ответ на вопрос, возможно ли расставить все n матрёшек описанным образом.

Ограничения

1 ≤ m < n ≤ 10⁹

Пояснения к примерам

Смотри рисунок. В первом примере на левой чаше стоит матрёшка с номером 4, на правой — с номером 3.

Если в левую матрёшку спрятать матрёшку с номером 1, а в правую — с номером 2, то все четыре матрёшки окажутся на весах и весы будут находиться в равновесии.

Во втором примере на левой чаше стоит матрёшка с номером 5, на правой — с номером 4.

Из восьми способов расположения остальных матрёшек на двух чашах ни один не даёт требуемого равновесия:

1) 5 + 3 + 2 + 1 ≠ 4

2) 5 + 3 + 2 ≠ 4 + 1

3) 5 + 3 + 1 ≠ 4 + 2

4) 5 + 3 ≠ 4 + 2 + 1

5) 5 + 2 + 1 ≠ 4 + 3

6) 5 + 2 ≠ 4 + 3 + 1

7) 5 + 1 ≠ 4 + 3 + 2

8) 5 ≠ 4 + 3 + 2 + 1

Примеры тестов

4
3

True

5
4

False

Задача D. Горизонтальные слои квадратов ≡

Условие

Тимофей решил нарисовать прямоугольник по следующим правилам:

Сверху идёт горизонтальный слой квадратов со стороной 1;

Под ним располагается горизонтальный слой квадратов со стороной 2;

...

Последним будет горизонтальный слой квадратов со стороной n.

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

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

Единственная строка входных данных содержит натуральное число n — сторону наибольшего квадрата.

Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64-битный тип данных, например long long в C++, int64 в Free Pascal, long в Java.

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

Выведите через пробел два натуральных числа — высоту и ширину такого прямоугольника.

Ограничения

2 ≤ n ≤ 40

Пояснение к примерам

Смотри рисунок.

Примеры тестов

2

3 2

3

6 6

4

10 12

Задача E. Дорожка из плиток ≡

Условие

Тимофею необходимо уложить на узкой парковой дорожке размером 6 × n тротуарную плитку. У него есть неограниченное количество плиток двух типов: 2 × 2 и 3 × 3. Сколько существует различных способов заполнения дорожки? Заказчик требует качественной работы, поэтому плитки нельзя ломать, каждая плитка должна плотно прилегать к соседней без наложений, дорожка должна быть заполнена полностью, края плитки не могут выходить за пределы дорожки.

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

Единственная строка входных данных содержит натуральное число n.

Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64-битный тип данных, например long long в C++, int64 в Free Pascal, long в Java.

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

Выведите одно натуральное число — ответ на вопрос задачи.

Ограничения

2 ≤ n ≤ 150

Пояснение к примеру

В примере дано n = 5. Смотри рисунок.

Примеры тестов

5

2

Задача F. Ехидный барин ≡

Условие

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

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

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

Единственная строка входных данных содержит натуральное числа n. Гарантируется четность n.

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

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

Ограничения

10 ≤ n ≤ 10⁵

Пояснение к примерам

В первом примере дано n = 10. Смотри рисунок: единственное подходящее решение — отрезать от одного угла квадрат площадью 49, а от другого площадью 1. Тогда суммарная площадь двух квадратов равна 50 и равна площади оставшейся части. Решение, при котором отрезаются квадраты площадью 25 не подходит — большой квадрат разделится на четыре части, а не на три.

Примеры тестов

10

1
1 7

50

2
5 35
17 31

Задача G. Жизнь чисел на дереве ≡

Условие

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

Возможно ли, двигаясь от корня по рёбрам, набрать в сумме число n?

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

Единственная строка входных данных содержит натуральное число n.

Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64-битный тип данных, например long long в C++, int64 в Free Pascal, long в Java.

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

Выведите в первой строке Yes или No — ответ на вопрос задачи.

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

Ограничения

1 ≤ n ≤ 10¹⁸

Пояснение к примеру

В первом примере сумму n = 5 набрать невозможно.

Во втором примере сумму n = 16 набрать можно, если сложить числа 1, 2, 4 и 9.

Примеры тестов

5

No

16

Yes
1 2 4 9

Задача H. Забавная игра ≡

Условие

Классики — старинная детская игра, популярная во всём мире. Одной из разновидностей правил являются следующие: на асфальт наносятся прямоугольники, как на рисунке ниже. Каждый участник совершает прыжки: сначала одной ногой на любое из двух полей по своему выбору, то есть на 1 или на 2, потом обеими ногами на поле с номером 3. Затем опять одной ногой на любое из двух полей по своему выбору, то есть на 4 или на 5, потом обеими ногами на поле с номером 6 и так далее. Остановиться можно в любой момент, а задача — набрать в сумме полей, на которые пришлись прыжки, ровно n.

Для указанного n определите количество различных подходящих маршрутов.

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

Единственная строка входных данных содержит натуральное число n.

Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64-битный тип данных, например long long в C++, int64 в Free Pascal, long в Java.

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

Выведите одно неотрицательное целое число — ответ на вопрос задачи.

Ограничения

1 ≤ n ≤ 10000

Пояснения к примерам

Сумму 22 в первом примере можно набрать тремя способами:

1. 1 + 3 + 4 + 6 + 8;
2. 1 + 3 + 5 + 6 + 7;
3. 2 + 3 + 4 + 6 + 7.

Сумму 3 во втором примере набрать не получится: после первого прыжка можно набрать только 1 или 2, а после второго — только 4 или 5.

Примеры тестов

22

3

3

0

Задача I. Избыточная коллекция ≡

Условие

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

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

Сейчас в коллекции Пети ровно 7 четных и 3 нечетных числа. Пете не очень нравятся нечетные числа, поэтому он готов отдать их вам, но только если вы угадаете на каких позициях они находятся. Чтобы вы смогли это сделать, Петя согласен ответить на несколько вопросов касательно своей коллекции. А именно — он может сказать, имеют ли два числа на каких-то позициях одинаковую четность.

Петя готов ответить лишь на 7 вопросов, и при этом не более 2-х вопросов про одно и тоже число. Если вы попытаетесь нарушить эти правила, Петя заподозрит вас в попытке украсть коллекцию, и обратится в СКПЦЧ (служба по контролю за перемещением целых чисел).

Протокол взаимодействия

Чтобы задать вопрос, ваша программа должна вывести "? X Y", где X, Y — целые числа, номера позиций в коллекции Пети, про которые вы хотите узнать. В ответ на вопрос программа жюри подаёт на вход вашей программе строку "Yes" или "No" — имеют ли числа на соответствующих позициях одинаковую четность.

Ваша программа может задать только 7 вопросов, и не более 2-х вопросов про одно и тоже число. Если ваша программа превысит количество вопросов, то она получит вердикт "Wrong answer".

Когда ваша программа определила ответ на задачу, она должна вывести "! X Y Z", где X, Y, Z — целые числа, номера позиций в коллекции Пети, на которых находятся нечетные числа. После вывода ответа программа должна завершиться.

Каждый вопрос и вывод окончательного результата должен быть одиночной строкой заканчивающейся одиночным переводом строки (\n). Буфер вывода необходимо сбрасывать после каждой строки:

Если ваша программа сделает недопустимый вывод, то она получит вердикт "Presentation error". Если ваша программа получила от программы жюри строку "-1" в качестве ответа, то она должна немедленно завершиться. Такое возможно, если ваша программа нарушила протокол взаимодействия. Если ваша программа не завершится в таком случае, то вердикт может отличаться от описанных выше (например, может быть вердикт "Runtime error").

Ограничения

1 ≤ X, Y, Z ≤ 10

Примеры тестов

No

No

No

Yes

Yes

Yes

No

? 1 2

? 2 3

? 3 4

? 4 5

? 5 6

? 6 7

? 7 8

! 1 3 8

Задача J. Кнопочный квест ≡

Условие

Тимофей с друзьями разрабатывает компьютерную игру "Свитки древних". Первой загадкой для игрока, очнувшегося в тюремной камере, будет автомат, который блокирует дверь. У автомата есть экран, на котором написано шестизначное число n с ведущими нулями и три кнопки. Нажатие на первую кнопку увеличивает число на 1 (если в результате получается 1000000, то на экране будет отображаться число 0 в виде 000000). Нажатие на вторую кнопку уменьшает число на 1 (если в результате получается -1, то на экране будет отображаться число 999999). Нажатие на третью кнопку упорядочивает цифры на экране в порядке возрастания. Например, если на экране было число 000618, то станет 000168, если было 500002, то станет 000025, если было 777777, то число не изменится. Дверь откроется, если на экране появится число m. При этом требуется наименьшее количество нажатий на кнопки.

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

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

Единственная строка входного файла содержит натуральное число n (без ведущих нулей).

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

Выведите в первой строке натуральное число m — ответ на вопрос задачи. Если таких чисел несколько, выведите их через пробел в порядке возрастания. Во второй строке выведите одно натуральное число — наименьшее количество нажатий на кнопки для получения m из n.

Ограничения

1 ≤ n ≤ 999999

Пояснение к примерам

В первом примере дано начальное n = 12. Наиболее длинная последовательность нажатий потребуется для достижения числа 949998, чтобы до него добраться потребуется 50006 нажатий на кнопки — больше, чем до любого другого числа.

Во втором примере дано начальное n = 949998. Искомых чисел оказалось сразу два.

Примеры тестов

12

949998
50006

949998

844447 844448
44461

Задача K. Лишнее ребро ≡

Условие

Дано полное k-арное дерево глубины h. k-арным называется корневое дерево где у каждой вершины не более k детей. Полным k-арным деревом глубины h называется k-арное дерево у которого все листы находятся на глубине h и у всех вершин k или 0 детей. Глубиной вершины в корневом дереве называется количество рёбер в простом пути от вершины до корня дерева.

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

Пусть edge  — некоторое ребро в дереве. Обозначим f(edge) =  количеству треугольников в двух деревьях которые получатся при удалении ребра edge в исходном дереве.

Авторы задачи ещё не решили, какое именно ребро является лишним. Пока они спорят, вычислите ∑_{edge − ребро дерева} f(edge), то есть сумму количества треугольников в двух деревьях по всем деревьям равным исходному с одним удалённым ребром.

Так как ответ может быть слишком большим, выведите его по модулю 998244353.

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

Единственная строка входных данных содержит два целых числа k и h.

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

Выведите одно число  — ответ на задачу по модулю 998244353.

Ограничения

2 ≤ k < 998244353, 2 ≤ h ≤ 10³

Примеры тестов

2 2

54

Задача L. Минимальная мощность ≡

Условие

Все любят фильмы про Годзиллу. Прямо как в этих фильмах, Годзилла внезапно появился и уже уничтожил Японию! Чтобы предотвратить дальнейшие разрушения, лидеры мировых держав собрали команду элитных исследователей. Они выяснили, что у Годзиллы есть сердце, работающее как атомный генератор. Чтобы победить Годзиллу, необходимо заморозить его сердце.

Для этого необходимо перед этим пробить его грудь. Это место на Годзилле можно представить как прямоугольную сетку: есть n + 1 горизонтальных линий с y-координатами a₀ = 0,a₁,...,a_n и m + 1 вертикальных линий с x-координатами b₀ = 0,b₁,b₂,...,b_m. Они вместе образуют сеточное поле n × m с клетками разного размера. Исследователи собираются разработать специальные анти-Годзилла снаряды мощности p, чтобы расстрелять ими каждую клетку на груди Годзиллы. Клетка размера h × w будет разрушена снарядом мощности p, если h ⋅ w ≤ p, иначе клетка выдержит удар и не разрушится.

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

К сожалению, в команде не оказалось способных программистов, чтобы вычислить оптимальную мощность p (целое число) снаряда. Сможете ли вы это сделать, чтобы спасти мир (точнее, то, что от него осталось)?

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

Первой строкой даны три целых числа: n,m,k. Во второй строке даны n целых чисел a_i. В третьей строке даны m целых чисел b_i.

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

Выведите единственное целое число p — минимальная мощность снарядов, нужное для победы над Годзиллой.

Ограничения

1 ≤ n,m ≤ 10⁵, 1 ≤ k ≤ n ⋅ m

0 ≤ a₁ < …  < a_n ≤ 10⁹

0 ≤ b₁ < …  < b_m ≤ 10⁹

Примеры тестов

4 5 7
2 5 6 8
3 5 6 10 12

3

3 5 14
1 4 5
4 6 8 10 13

9