Перебор

Рассмотрим все представления числа \(n\) в виде суммы различных целых возрастающих слагаемых: \(n = a_1 + a_2 + \ldots + a_k\), \(a_1 < a_2 < \ldots < a_k\).

Будем называть такое разбиение хаотическим, если для него выполнено следующее условие: для любых трех подряд идущих слагаемых среднее не равно среднему арифметическому крайних. Иначе говоря, для всех \(i\) от 1 до \(k - 2\) выполнено \(a_{i+1} \ne (a_i + a_{i+2}) / 2\).

Задано число \(n\). Выведите все его хаотические разбиения на слагаемые.

На ввод подается целое число \(n\) (\(1 \le n \le 80\)).

Выведите все хаотические разбиения на слагаемые числа \(n\). Разбиения можно выводить в любом порядке. Выводите слагаемые в каждом разбиении, разделяя их знаком <<+>> без пробелов.

В этой задаче 25 тестов, каждый оценивается независимо в 4 балла.

Задача в разработке

Его Величество Король Бубей Второй пожелал объехать свои владения. При этом к маршруту есть следующие пожелания:

1) маршрут должен занимать наименьшее возможное время (королевское время – вещь очень ценная и его надо беречь);

2) маршрут должен включать все населенные пункты ровно по одному разу (если король пропустит какой-то населенный пункт, то его жители будут возмущены королевским невниманием и перестанут платить налоги; если король посетит какой-то населенный пункт больше одного раза, то жители остальных населенных пунктов также возмутятся)

3) маршрут должен начинаться и заканчиваться в столице государства (объехав свои владения, король должен сразу приступить к делам). Столица входит в маршрут ровно 2 раза: как пункт отбытия и как пункт назначения, она не может являться промежуточным населенным пунктом маршрута.

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

Входные данные
Сначала вводится число N (натуральное, не превышает 10) – количество населенных пунктов королевства. Затем следует N строк по N чисел в каждой – время пути между населенными пунктами (время – целое неотрицательное число, не превышает 500; если время = 0, то это означает, что пути между какими-то населенными пунктами нет). Населенный пункт №1 является столицей государства.

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

 

Дано число n. Вам необходимо сгенерировать все правильные скобочные последовательности, содержащие n пар скобок.

Входные данные
В первой строке дано натуральное число n (1 <= n <= 8).

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

 

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

Душ — дело не быстрое, поэтому во время ожидания студенты общаются. В каждый момент времени студенты общаются парами: (2*i - 1)-й человек в очереди (на текущий момент) общается с (2*i)-м.
Рассмотрим этот процесс подробнее. Обозначим людей цифрами от 1 до 5. Пусть изначально очередь имеет вид 23154 (человек 2 стоит в начале очереди). Тогда перед открытием душа 2 общается с 3, 1 общается с 5, 4 ни с кем не общается. Затем 2 заходит в душ. Пока 2 принимает душ, 3 и 1 общаются, а также 5 и 4 общаются. Затем 3 заходит в душ. Пока 3 принимает душ, 1 и 5 общаются, 4 ни с кем не общается. Затем 1 заходит в душ, а пока он принимает душ, 5 и 4 общаются. Затем 5 заходит в душ, а затем 4 заходит в душ.

Известно, что если студенты i и j общаются, то радость студента i увеличивается на gi,j, а радость студента j увеличивается на gj,i.  Вам надо найти такой изначальный порядок студентов в очереди, чтобы суммарная радость всех студентов в итоге была максимальной. Стоит заметить, что некоторые студенты могут общаться несколько раз. В приведенном выше примере студенты 1 и 5 общаются пока ждут открытия душа, а также пока 3 принимает душ.

Сегодня возле душа выстроилась очередь ровно из 5 студентов. Найдите максимально возможную суммарную радость этих студентов.

Входные данные
Входные данные состоят из пяти строк, в каждой строке записано пять целых чисел разделенных пробелом: j-е число в i-й строке обозначает gi,j (0 ≤ gi,j≤ 10⁵). Гарантируется, что gi,i = 0 для всех i.
Считайте, что студенты пронумерованы от 1 до 5.

Выходные данные
Выведите единственное целое число — максимально возможную суммарную радость студентов.
 

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

Входные данные
В первой строке вам дано положительное число n (1 <= n <= 8) - количество работ и рабочих.
В следующих n строках дано по n положительных чисел, разделенных пробелами - матрица А, где A_i,j показывает за сколько долларов рабочий под номером i выполнит работу под номером j. Для всех A_i,j выполнено 1 <= A_i,j <= 10⁵.

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


Пояснение к примеру
Первый рабочий выполнит вторую работу, второй рабочий третью работу и третий рабочий первую работу. Итоговая стоимость 1 + 4 + 7 = 12.

Вам дано натуральное число n. Выведите все перестановки размера n в лексикографическом порядке.

Входные данные
В первой строке дано натуральное число n (1 <= n <= 7).

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

 

В каком-то другом мире сегодня 31 декабря. Дед Кокованя решил приготовить многомерный бургер, который так любит Дарёна. Бургер уровня L (L - целое число, большее или равное 0) готовится следующим образом:

• Бургер нулевого уровня - это котлета.
• Бургер с уровнем L (L >= 1) - это булочка, бургер с уровнем (L-1), котлета, бургер с другим уровнем (L-1) и еще одна булочка, уложенные вертикально в указанном порядке, считая снизу.

Например, бургер уровня 1 и бургер уровня 2 выглядят как БКККБ и ББКККБКБКККББ (повернутые на 90 градусов), где Б и К обозначают булочку и котлету.

Бургер, который приготовит дед Кокованя, - это бургер уровня N. Дарёна всегда съедает только Х слоев нижней части бургера (слой - это котлета или булочка). Сколько котлет она съест?


Входные данные
Программа получает на вход 2 целых числа через пробел: N и X (1 <= N <= 50, 1 <= X <= (общее количество слоев в бургере N-го уровня)).

Выходные данные
Выведите количество котлет в самых нижних X слоях, считая от нижней части бургера уровня N.
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	2 7	4	В самых нижних 7 слоях бургера второго уровня ( ББКККБКБКККББ) находятся 4 котлеты.
2	1 1	0
3	50 4321098765432109	2160549382716056	Бургер 50-го уровня довольно толстый настолько, что количество его слоев не укладывается в 32-битное целое число.

Даны два натуральных числа N и K. Требуется вывести  все цепочки x₁, x₂, ..., x_N такие, что xi - натуральное и 1 ≤ x_i ≤ K.

Входные данные
Вводятся два натуральных числа N и K (N, K ≤ 6).

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

Примеры

№	Входные данные	Выходные данные
1	2 3	1 1  1 2  1 3  2 1  2 2  2 3  3 1  3 2  3 3

В тактике футбола одним из основных понятий является схема игры. Она определяет, сколько из десяти полевых игроков будут играть в защите, сколько — в полузащите и сколько — в нападении.

Например, схема игры 5-3-2 означает, что в команде пять защитников, три полузащитника и два нападающих. В соответствии с современными представлениями на схему игры накладываются следующие ограничения: должно быть не менее одного и не более пяти защитников, не менее одного и не более пяти полузащитников и не более трех нападающих. Отметим, что нападающих может в команде и не быть совсем. Будем рассматривать только такие схемы.

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

Будем также считать, что игрок в некоторый момент времени находится в линии полузащиты, если он находится на расстоянии не более 20 метров от центральной линии. Соответственно, игрок находится в линии защиты, если он находится не более чем в 40 метрах от «своей» лицевой линии, и в линии нападения, если находится не более чем в 40 метрах от «чужой» лицевой линии.


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

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

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

Входные данные
Входной файл содержит десять строк, содержащих по два целых числа x_i и y_i каждая, — координаты каждого из игроков команды (0 ≤ x_i ≤ 120, x_i ≠ 40, x_i ≠ 80, 0 ≤ y_i ≤ 80).

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

Примеры

№	Входные данные	Выходные данные
1	97 0 13 18 2 6 119 11 42 21 72 80 75 78 106 45 22 67 28 47	9 2-5-3 3-5-2 3-4-3 4-5-1 4-4-2 4-3-3 5-4-1 5-3-2 5-2-3

У Пети имеется игровое поле размером 3x3, заполненное числами от 1 до 9. В начале игры он может поставить фишку в любую клетку поля. На каждом шаге игры разрешается перемещать фишку в любую соседнюю по стороне клетку, но не разрешается посещать одну и ту же клетку дважды. Петя внимательно ведет протокол игры, записывая в него цифры в том порядке, в котором фишка посещала клетки. Пете стало интересно, какое максимальное число он может получить в протоколе. Помогите ему ответить на этот вопрос.

Входные данные
Входной файл содержит описание поля — 3 строки по 3 целых числа, разделенных пробелами. Гарантируется, что все девять чисел различны и лежат в диапазоне от 1 до 9.

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

Ответ можно выводить не в виде числа, а в виде строки или в виде последовательности отдельных цифр (но не разделяя их пробелами).

Примеры

№	Входные данные	Выходные данные
1	1 2 3 4 5 6 7 8 9	987456321

Примеры

№	Входные данные	Выходные данные
1	2	11 10 01 00

Ввод	Вывод
7 2518 7 5 2 4 1 6 3	positumque loculum
4 1 3 2 4 1	easily
4 2 3 2 4 1	3 4 2 1

Приятного решения ♥♥
(с) Елизавета Ястреба

Ввод	Вывод
2	2
4	4

 

Дан неориентированный планарный граф на \(n\) вершинах и целое положительное число \(k\). Назовем раскраску графа красивой, если никакие две соседние его вершины не покрашены в один цвет (для лучшего понимания рекомендуем обратиться к разделу "Примечание"). Найдите количество красивых раскрасок графа в \(k\) цветов.

В первой строке ввода находится единственное целое число \(t\) — количество тестовых случаев, которые вам будет необходимо обработать \((1 \leq t \leq 100)\).

Первая строка каждого тестового случая содержит целые числа \(n\), \(m\) и \(k\) — количество вершин и рёбер графа, а также количество доступных цветов \((1 \leq n \leq 30, 1 \leq m \leq 40, 1 \leq k \leq 11)\). Обратите внимание, что с ростом \(n\) значение \(k\) в тестах убывает.

Следующие \(m\) строк содержат по два целых числа \(u, v\), задающих рёбра графа.

Для каждого тестового случая выведите единственное число — количество красивых раскрасок графа по модулю \(10^9+7\).

Планарный граф — граф, который можно изобразить на плоскости без пересечений рёбер не по вершинам.

В тесте из условия задан следующий граф: