Задача A. Полные квадраты ≡

Условие

С целью поиска закономерностей иногда полезно сгенерировать длинную последовательность по определенным правилам. Известно, например, что последовательность 0, 0 + 1, 0 + 1 + 3, 0 + 1 + 3 + 5, …, 0 + 1 + 3 + …  + (2n − 1), …, составленная из сумм нескольких первых нечетных натуральных чисел, состоит из квадратов целых чисел: 0, 1, 4, 9, …, n²,….

Обобщим эту последовательность следующим образом: будем использовать вместо начального значения не ноль, а число k. Получим последовательность: k, k + 1, k + 1 + 3, k + 1 + 3 + 5, …, k + 1 + 3 + …  + (2n − 1), …. В отличие от случая k = 0, в этой последовательности могут встречаться не только полные квадраты. Необходимо найти минимальное целое неотрицательное число, квадрат которого встречается в этой последовательности.

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

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

В единственной строке содержится целое число k — начальное число в последовательности. Обратите внимание, что для считывания и хранения такого большого числа необходимо использовать 64-битный тип данных.

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

Выведите минимальное неотрицательное целое число, квадрат которого встречается в описанной последовательности. Если в последовательности не встречается квадратов целых чисел, выведите none.

Ограничения

 − 10¹² ≤ k ≤ 10¹²

Описание подзадач и системы оценивания

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

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

В первом примере каждое число последовательности является полным квадратом. Минимальный из них — 0, 0² = 0.

Во втором примере последовательность начинается так:  − 5,  − 4,  − 1, 4, 11, 20,…. Минимальное неотрицательное целое число, квадрат которого встречается в последовательности — 2, 2² = 4.

В третьем примере последовательность начинается так: 2, 3, 6, 11, 18, …. В ней нет квадратов целых чисел.

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

0

0

-5

2

2

none

Задача B. Марфа Геннадьевна ест яйца ≡

Условие

У Марфы Геннадьевны есть любимая курица, которую она назвала Марфой. В определённые дни Марфа давала по яйцу, и Марфа Геннадьевна в тот же день съедала его. Марфа Геннадьевна записывала, в какие дни Марфа давала яйцо.

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

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

Формат входного файла

Входной файл содержит целое число N.

Далее следуют N целых чисел a_i — номера дней, в которые Марфа Геннадьевна съедала яйцо.

Формат выходного файла

Требуется вывести в выходной файл слово GOOD, если Марфа Геннадьевна съедала не более двух яиц в неделю, и слово BAD, если найдётся хотя бы один промежуток из семи подряд идущих дней, в который она съедала более двух яиц.

Ограничения

1 ≤ N ≤ 100

1 ≤ a₁ < a₂ < …  < a_N ≤ 1000

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

3
1 7 8

GOOD

5
1 7 9 12 17

BAD

Задача C. Куб со спицами (курс Python) ≡

Условие

Возьмём N³ одинаковых кубиков. Раскрасим кубики в N цветов так, чтобы в каждый цвет было раскрашено ровно N² кубиков. Сложим из всех кубиков один большой куб. Начнём протыкать этот куб спицами параллельно его рёбрам. Любая спица пройдёт сквозь ровно N кубиков.

Требуется сложить куб так, чтобы любая спица проходила сквозь кубики всех N цветов.

Формат входного файла

Во входном файле содержится единственное натуральное число N.

Формат выходного файла

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

Ограничения

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

2

1 2
2 1
2 1
1 2

Задача D. Кепка ≡

Условие

Если положить α  = 0, то поверхность K будет описываться формулами в последней строке, где нужно принять z равным 0.

Вот пример кепки при R = 10, L = 20.

Формат входного файла

Входной файл содержит целые числа R L.

Формат выходного файла

Выходной файл должен содержать площадь поверхности кепки, видимой сверху, с точностью не менее 4 знаков после запятой.

Ограничения

1 ≤ R ≤ L ≤ 100

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

10 20

785.39816340

10 10

628.31853072

Задача E. Машинное обучение ≡

Условие

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

Были подготовлены обучающие наборы сложности от 0 до k. План обучения задаётся массивом целых чисел [a₁, a₂, …, a_n], где a_i задаёт сложность набора, используемого на i-й итерации обучения. Для всех i от 1 до n должно выполняться неравенство 0 ≤ a_i ≤ k.

Выяснилось, что эффективность плана обучения зависит от битовых представлений сложностей обучающих наборов. Для того, чтобы план был эффективным, необходимо, чтобы для любых двух значений i и j, где 1 ≤ i ≤ j ≤ n, выполнялось (a_i and a_j) = a_i. Напомним, что побитовое «и» (and) двух целых неотрицательных чисел устроено следующим образом: запишем оба числа в двоичной системе счисления, i-й двоичный разряд результата равен 1, если у обоих аргументов он равен 1. Например, (14 and 7) = (1110₂ and 0111₂) = 110₂ = 6. Эта операция реализована во всех современных языках программирования, в языках C++, Java и Python она записывается как "&", в Паскале как "and".

Однако постоянное использование наборов одной сложности не даёт прогресса в обучении. Чтобы этого избежать, для плана обучения должны быть выполнены m требований следующего вида. Каждое требование задаётся двумя числами l_i и r_i и означает, что a_li ≠ a_ri.

Сотрудники лаборатории хотят найти количество эффективных планов, которые удовлетворяют всем требованиям. Так как это число может быть очень большим, нужно найти его остаток от деления на 10⁹ + 7.

Требуется написать программу, которая по заданным целым числам n и k, а также m требованиям вида l_i, r_i определяет количество эффективных планов, которые удовлетворяют всем требованиям, и выводит остаток от деления этого количества на число 10⁹ + 7.

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

Первая строка входных данных содержит три целых числа n, m и k — количество итераций обучения, количество требований и максимальную сложность обучающего набора.

Следующие m строк описывают требования, i-я строка содержит два целых числа l_i, r_i, которые означают, что a_li ≠ a_ri, 1 ≤ l_i < r_i ≤ n. Гарантируется, что все требования различны.

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

Выведите одно целое число — остаток от деления количества эффективных планов, удовлетворяющих всем требованиям, на число 10⁹ + 7.

Ограничения

1 ≤ n ≤ 3 ⋅ 10⁵, 0 ≤ m ≤ 3 ⋅ 10⁵, 0 ≤ k ≤ 10¹⁸, a_li ≠ a_ri, 1 ≤ l_i < r_i ≤ n

Описание подзадач и системы оценивания

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

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

Все возможные планы для первого теста: [0,0], [0,1], [0,2], [0,3], [1,1], [1,3], [2,2], [2,3], [3,3]. Для второго теста: [0,1,1], [0,2,2].

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

2 0 3

9

3 1 2
1 2

2

Задача F. Игра с числами ≡

Условие

Сегодня на уроке математики Петя и Вася изучали понятие арифметической прогрессии. Арифметической прогрессией с разностью d называется последовательность чисел a₁, a₂, …, a_k, в которой разность между любыми двумя последовательными числами равна d. Например, последовательность 2, 5, 8, 11 является арифметической прогрессией с разностью 3.

После урока Петя и Вася придумали новую игру с числами. Игра проходит следующим образом.

В корзине находятся n фишек, на которых написаны различные целые числа a₁, a₂, …, a_n. По ходу игры игроки выкладывают фишки из корзины на стол. Петя и Вася делают ходы по очереди, первым ходит Петя. Ход состоит в том, что игрок берет одну фишку из корзины и выкладывает ее на стол. Игрок может сам решить, какую фишку взять. После этого он должен назвать целое число d такое, что все числа на выбранных к данному моменту фишках являются членами некоторой арифметической прогрессии с разностью d, не обязательно последовательными. Например, если на столе выложены фишки с числами 2, 8 и 11, то можно назвать число 3, поскольку эти числа являются членами приведенной в начале условия арифметической прогрессии с разностью 3.

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

Например, если в корзине имеются числа 2, 3, 5 и 7, то Петя может выиграть. Для этого ему необходимо первым ходом выложить на стол число 3. После первого хода у него много вариантов назвать число d, например он может назвать d = 3. Теперь у Васи два варианта хода.

• Вася может вторым ходом выложить фишку с числом 5 и назвать d = 2. Тогда Петя выкладывает фишку с числом 7, называя d = 2. На столе оказываются фишки с числами 3, 5 и 7, а в корзине осталась только фишка с числом 2. Вася не может ее выложить, поскольку после этого он не сможет назвать корректное число d. В этом случае Вася проигрывает.
• Вася может вторым ходом выложить фишку с числом 7 и также назвать, например, d = 2. Тогда Петя выкладывает фишку с числом 5, называя также d = 2. Вася снова попадает в ситуацию, когда на столе оказываются фишки с числами 3, 5 и 7, а в корзине осталась только фишка с числом 2, и он также проигрывает.

Заметим, что любой другой первый ход Пети приводит к его проигрышу. Если он выкладывает число 2, то Вася отвечает числом 7, и Петя не может выложить ни одной фишки. Если Петя выкладывает фишку с числом 5 или 7, то Вася выкладывает фишку с числом 2, и у Пети также нет допустимого хода.

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

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

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

Система оценивания

Правильные решения для тестов, в которых 1 ≤ n ≤ 15, будут оцениваться из 40 баллов.

Формат входного файла

Первая строка входного файла содержит целое число n.

Вторая строка содержит n различных целых чисел a₁, a₂, …, a_n. Соседние числа разделены ровно одним пробелом.

Формат выходного файла

Первая строка выходного файла должна содержать число k — количество различных первых ходов, которые может сделать Петя, чтобы выиграть. Если Вася может выиграть вне зависимости от действий Пети, строка должна содержать цифру 0. Во второй строке должно содержаться k различных целых чисел — все выигрышные числа. Будем называть число выигрышным, если, выложив в качестве первого хода фишку, содержащую это число, Петя может выиграть вне зависимости от действий Васи. Соседние числа в строке должны быть разделены ровно одним пробелом.

Ограничения

1 ≤ n ≤ 200

d ≥ 2

1 ≤ a_i ≤ 10⁵

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

4
2 3 5 7

1
3

2
2 4

0

Задача G. Обработка больших данных ≡

Условие

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

Суперкомпьютер имеет 2^k ячеек памяти, пронумерованных от 0 до 2^k – 1. Отрезком [L, R] называется последовательность подряд идущих ячеек памяти с номерами от L до R, включительно.

Некоторые отрезки памяти являются корректными. Отрезок памяти [L, R] является корректным, если его длина (R − L + 1) равна 2ⁱ для некоторого i, а число L делится на 2ⁱ. Например, если k = 3, то ячейки памяти пронумерованы от 0 до 7, а корректными являются отрезки [0, 7], [0, 3], [4, 7], [0, 1], [2, 3], [4, 5], [6, 7], [0, 0], [1, 1], [2, 2], [3, 3], [4, 4], [5, 5], [6, 6] и [7, 7].

Ключевой операцией в новой архитектуре является операция STORE, которая за одно действие присваивает одно и то же значение всем ячейкам памяти некоторого корректного отрезка.

Исходно все ячейки памяти содержат значение 0. В лаборатории планируют запустить на суперкомпьютере программу обработки данных, но перед её запуском необходимо инициализировать память определенным образом. А именно: первые c₁ ячеек памяти необходимо заполнить значениями v₁, следующие c₂ ячеек — значениями v₂, и так далее, последние c_n ячеек памяти необходимо заполнить значениями v_n, где 1 ≤ v_i ≤ m.

Ученым надо выяснить, какое минимальное количество операций STORE необходимо выполнить, чтобы проинициализировать память требуемым образом.

Например, если k = 3, n = 3, m = 2, c₁ = 1, v₁ = 1, c₂ = 2, v₂ = 2, c₃ = 5, v₃ = 1, то итоговое содержимое памяти должно быть следующим: [1, 2, 2, 1, 1, 1, 1, 1]. В этом случае для инициализации памяти достаточно трех операций STORE:

1. STORE([0, 7], 1), после этой операции все ячейки памяти содержат значение 1;
2. STORE([1, 1], 2), после этой операции содержимое памяти [1, 2, 1, 1, 1, 1, 1, 1];
3. STORE([2, 2], 2) , после этой операции содержимое памяти [1, 2, 2, 1, 1, 1, 1, 1],

Заметим, что операцию STORE([1, 2], 2) выполнить нельзя, потому что [1, 2] не является корректным отрезком памяти.

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

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

Первая строка входных данных содержит три целых числа: k, n и m.

Следующие n строк содержат по два целых числа, i-я из этих строк содержит числа c_i и v_i.

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

Требуется вывести одно целое число – минимальное количество операций STORE, которое необходимо выполнить для инициализации памяти заданным образом.

Ограничения

0 ≤ k ≤ 30, 1 ≤ n ≤ 10⁵, 1 ≤ m ≤ 10⁹

1 ≤ c_i ≤ 2^k, 1 ≤ v_i ≤ m, c₁ + c₂ + …  + c_n = 2^k

Описание подзадач и системы оценивания

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

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

3 3 2
1 1
2 2
5 1

3

Задача H. Столицы ≡

Условие

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

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

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

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

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

В первом примере существует единственный способ выбрать три столицы: города с номерами 2, 3 и 4. Рисунок, соответствующий первому примеру, приведен ниже.

Во втором примере существует четыре варианта выбора трёх столиц из четверки городов: 2, 3, 4 и 5. Можно также выбрать столицами города с номерами 1, 6 и 7. Рисунок, соответствующий второму примеру, приведен ниже.

Система оценивания

• Правильные решения для тестов, в которых 3 ≤ n ≤ 50, будут оцениваться из 20 баллов.
• Правильные решения для тестов, в которых 3 ≤ n ≤ 500, будут оцениваться из 40 баллов.
• Правильные решения для тестов, в которых 3 ≤ n ≤ 5000, будут оцениваться из 60 баллов.

Формат входного файла

Формат выходного файла

Ограничения

3 ≤ n ≤ 10⁵, 1 ≤ d < n

1 ≤ a_i ≤ n, 1 ≤ b_i ≤ n, a_i ≠ b_i

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

4 2
1 2
1 3
1 4

1

7 2
1 2
1 3
1 4
5 1
5 6
5 7

5