#111227

Ордынское войско

Темы: [Перебор] [Динамическое программирование: последовательности]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Заключительный этап, 2012, Задача H ]

Готовясь к бою, хан Гирей пронумеровал всех воинов своего войска натуральными числами от 1 до N. Поскольку воины умеют сражаться, но не умеют считать, при любом построении в шеренгу они выстраиваются в произвольном порядке. Одного или несколько воинов, стоящих в шеренге, будем называть отрядом. Отряд назовем правильным, если номера этих воинов в том порядке, в котором они стоят в шеренге, образуют упорядоченную по возрастанию последовательность чисел. Среди всех правильных отрядов хан Гирей выбирает ударный отряд – самый большой по количеству воинов. Так, в шеренге 1 3 2 4 из четырех воинов ударными являются отряды 1 3 4 и 1 2 4, а отряд 1 4 – один из правильных, но не ударный. Некоторые воины являются личными телохранителями хана Гирея. Требуется составить программу, определяющую количество таких шеренг, в которых телохранители хана образуют ударный отряд.

Входные данные

В первой строке входного файла задано натуральное число N – общее количество воинов (1 ≤ N ≤ 15). Во второй строке задано натуральное число K – количество телохранителей хана (1 ≤ K ≤ N). В третьей строке через пробел указаны K различных натуральных чисел, не превосходящих N, – номера телохранителей хана в порядке возрастания.

Выходные данные

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

Примечание

В первом примере войско состоит из пяти воинов. Ударный отряд должен состоять из трех воинов с номерами 1, 3 и 4. Этому условию удовлетворяют следующие 11 шеренг: (1, 3, 2, 5, 4), (1, 3, 5, 2, 4), (1, 3, 5, 4, 2), (1, 5, 3, 2, 4), (1, 5, 3, 4, 2), (2, 1, 3, 5, 4), (2, 1, 5, 3, 4), (2, 5, 1, 3, 4), (5, 1, 3, 2, 4), (5, 1, 3, 4, 2), (5, 2, 1, 3, 4).

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

(оценивается в 40 баллов) 1 ≤ N ≤ 8.
(оценивается в 10 баллов) 9 ≤ N ≤ 10.
(оценивается в 10 баллов) N = 11.
(оценивается в 10 баллов) N = 12.
(оценивается в 10 баллов) N = 13.
(оценивается в 10 баллов) N = 14.
(оценивается в 10 баллов) N = 15.

Примеры

Входные данные

5
3
1 3 4

Выходные данные

Входные данные

3
3
1 2 3

Выходные данные

Входные данные

1
1
1

Выходные данные

#111858

Простой квадрат

Темы: [Перебор] [Простые задачи на перебор]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Муниципальный этап, Москва, 2012, Задача E ]

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

Входные данные

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

Выходные данные

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

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

Пример

Ввод	Вывод
1 2 3 4 5 6 7 8 9	987456321

#111991

Волшебный квадрат

Темы: [Простые задачи на перебор]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Муниципальный этап, Московская область, Интернет этап, 2013, Волшебный квадрат ]

На день рождения Егору подарили волшебный квадрат.

Волшебный квадрат — это таблица 3 × 3, в каждой из ячеек которой находятся числа от 0 до 9. Егор придумал следующую игру с волшебным квадратом: он загадывает число N и пытается так поставить числа в каждую ячейку квадрата, чтобы сумма чисел в каждой строке и каждом столбце была равна в точности N.

Пусть расстановка — это волшебный квадрат, заполненный числами. Тогда расстановки A и B считаются различными, если хотя бы для каких-то строки x и столбца y выполняется неравенство A_x, y ≠ B_x, y, где A_x, y и B_x, y — это числа, находящиеся в строке x и столбце y в расстановках A и B соответственно.

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

Напишите программу, которая поможет ответить на вопрос Егора.

Входные данные

Единственная строка входных данных содержит целое число N (0 ≤ N ≤ 10⁹).

Выходные данные

Требуется вывести одно число — искомое количество расстановок.

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

Входные данные

Выходные данные

Примечание

В примере из условия существует всего одна допустимая расстановка — это таблица 3 × 3, состоящая из нулей. Очевидно, что сумма элементов в любой строке или столбце в такой расстановке равна 0.

#113101

Счет в гипершашках

Темы: [Сортировка подсчетом] [Перестановки]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2016, 2 день, Задача B ]

Андрей работает судьей на чемпионате по гипершашкам. В каждой игре в гипершашки участвует три игрока. По ходу игры каждый из игроков набирает некоторое положительное целое число баллов. Если после окончания игры первый игрок набрал \(a\) баллов, второй — \(b\), а третий \(c\), то говорят, что игра закончилась со счетом \(a:b:c\).

Андрей знает, что правила игры гипершашек устроены таким образом, что в результате игры баллы любых двух игроков различаются не более чем в \(k\) раз.

После матча Андрей показывает его результат, размещая три карточки с очками игроков на специальном табло. Для этого у него есть набор из n карточек, на которых написаны числа \(x_1, x_2, …, x_n\). Чтобы выяснить, насколько он готов к чемпионату, Андрей хочет понять, сколько различных вариантов счета он сможет показать на табло, используя имеющиеся карточки.

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

Входные данные

Первая строка входного файла содержит два целых числа: \(n\) и \(k (3 \le n \le 100 000, 1 \le k \le 10^9\) ).

Вторая строка входного файла содержит \(n\) целых чисел \(x_1, x_2, …, x_n (1 \le x_i \le 10^9 )\).

Выходные данные

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

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

В приведенном примере Андрей сможет показать следующие варианты счета: 1:1:2, 1:2:1, 2:1:1, 1:2:2, 2:1:2, 2:2:1, 2:2:3, 2:3:2, 3:2:2. Другие тройки чисел, которые можно составить с использованием имеющихся карточек, не удовлетворяют заданному условию, что баллы любых двух игроков различаются не более чем в \(k\) = 2 раза.

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

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

Подзадача 1 (15 баллов)

\(3 \le n \le 100 000, k = 1, 1 \le x_i \le 100 000\)

Подзадача 2 (23 балла)

\(3 \le n \le 100, k \le 100, 1 \le x_i \le 100\)

Подзадача 3 (30 баллов)

\(3 \le n \le 100 000, k \le 10^9 \le x_i \le 10^9\), все \(x_i\) различны

Подзадача 4 (32 балла)

\(3 \le n \le 100 000, k \le 10^9 \le x_i \le 10^9\)

Примеры

Входные данные

5 2
1 1 2 2 3

Выходные данные