#1618

Кодовый замок

Темы: [Разные комбинаторные структуры]

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2009, Лига А, Задача C ]

Кодовый замок состоит из $N$ рычажков, каждый из которых может быть установлен в любое из $K$ положений, обозначенных натуральными числами от 1 до $K$. Известно, что для того чтобы открыть замок, нужно, чтобы сумма положений любых трех последовательных рычажков была равна $K$.

Два рычажка уже установлены в некоторые положения, и их переключать нельзя. Рычажок с номером $p_1$ установлен в положение $v_1$, а рычажок $p_2$ – в положение $v_2$.

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

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

Вводятся натуральные числа $N$, $K$, $p_1$, $v_1$, $p_2$, $v_2$. 3 ≤ $N$ ≤ 100 000, 3 ≤ $K$ ≤ 100 000, $p_1$ ≠ $p_2$, 1 ≤ $p_1$ ≤ $N$, 1 ≤ $p_2$ ≤ $N$, 1 ≤ $v_1$ ≤ $K$, 1 ≤ $v_2$ ≤ $K$.

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

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

Примеры

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

3 3 1 1 2 1

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

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

3 3 1 1 3 2

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

#1628

Кодовый замок

Темы: [Разные комбинаторные структуры]

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2009, Лига Б, Задача C ]

Кодовый замок состоит из $N$ рычажков, каждый из которых может быть установлен в любое из $K$ положений, обозначенных натуральными числами от 1 до $K$. Известно, что для того чтобы открыть замок, нужно, чтобы сумма положений любых трех последовательных рычажков была равна $K$.

Два рычажка уже установлены в некоторые положения, и их переключать нельзя. Рычажок с номером $p_1$ установлен в положение $v_1$, а рычажок $p_2$ – в положение $v_2$.

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

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

Вводятся натуральные числа $N$, $K$, $p_1$, $v_1$, $p_2$, $v_2$. Рычажки пронумерованы числами от 1 до $N$.

3 ≤ $N$ ≤ 10000, 3 ≤ $K$ ≤ 6, $p_1$≠$p_2$, 1 ≤ $p_1$ ≤ $N$, 1 ≤ $p_2$ ≤ $N$, 1 ≤ $v_1$ ≤ $K$, 1 ≤ $v_2$ ≤ $K$.

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

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

#2762

Темы: [Разные комбинаторные структуры]

Источники: [ Командные олимпиады, Турнир Архимеда, 2010, Задача B ]

Разложение на простые множители числа $12$ можно записать тремя способами:

12=2\cdot2\cdot3=2\cdot3\cdot2=3\cdot2\cdot2.

А сколькими способами можно записать разложение на простые множители числа $N$?

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

Вводится одно натуральное число $N$ ($2\le N\le 1 000$).

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

Выведите одно число – количество различных записей разложения.

Примеры

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

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

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

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

#111295

Поезда

Темы: [Генерация по номеру] [Динамическое программирование]

Источники: [ Командные олимпиады, ВКОШП, 2011, Задача J ]

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

Любимым занятием Васи стала сортировка поездов с использованием специального сортировочного тупика. $\text{[math]}$

Справа к тупику подъезжает поезд, составленный из всех $n$ вагонов. Затем вагоны по одному загоняются в сортировочный тупик и выгоняются из него налево. Васе нравится, если ему удается отсортировать поезд с помощью сортировочного тупика — добиться того, чтобы слева от тупика вагоны были расположены по порядку от 1 до $n$.

Например, пусть в исходном поезде 4 вагона, которые следуют в порядке 3, 1, 2, 4. Его можно отсортировать следующим образом. Загоняем вагон 3 в тупик. Загоняем вагон 1 в тупик. Выгоняем вагон 1 из тупика. Загоняем вагон 2 в тупик. Выгоняем вагон 2 из тупика. Выгоняем вагон 3 из тупика. Загоняем вагон 4 в тупик. Выгоняем вагон 4 из тупика.

Не все поезда можно отсортировать таким образом. Например, поезд из 3 вагонов, следующих в порядке 2, 3, 1, отсортировать нельзя.

Вася выписал на листке в лексикографическом порядке все поезда длины $n$, которые можно отсортировать с помощью тупика. Поезд $(a_1, a_2, \ldots, a_n)$ идет раньше поезда $(b_1, b_2, \ldots, b_n)$ в лексикографическом порядке, если существует такое $i$ ($1 \le i \le n$), что для всех $j < i$ выполняется $a_j = b_j$, а $a_i < b_i$. Например, все поезда из трех вагонов, которые можно отсортировать с помощью тупика, в лексикографическом порядке выписываются следующим образом: $(1, 2, 3)$, $(1, 3, 2)$, $(2, 1, 3)$, $(3, 1, 2$), $(3, 2, 1)$.

Вася потерял свой листок, и его интересует вопрос: какой поезд был выписан на его листке под номером $k$. Помогите ему выяснить это.

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

Входной файл содержит два целых числа — $n$ и $k$ ($1 \le n \le 30$, $1 \le k \le 10^{18}$).

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

Выведите в выходной файл $n$ целых чисел: $k$-й в лексикографическом порядке поезд из $n$ вагонов, который можно отсортировать с помощью тупика.

Если с помощью тупика можно отсортировать менее $k$ поездов из $n$ вагонов, выведите $-1$.

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

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

4 1

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

1 2 3 4

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

4 3

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

1 3 2 4

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

4 15

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

-1

Страница: << 1 2 Отображать по: