--->
2 задач
<---
Источники
Страница:
1
Отображать по:
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Рассматриваются все разбиения натурального числа \(N\) на сумму \(К\) неотрицательных слагаемых (\(1 \leq N \leq 32\), \(2 \leq K \leq 32\)). Суммы, отличающиеся только порядком слагаемых, считаем различными. Упорядочим все разбиения по убыванию первого слагаемого, а при равных первых слагаемых – по убыванию второго слагаемого, а при равных первых и вторых слагаемых – по убыванию третьего слагаемого и т. д. Пронумеруем их. Например, при \(N=4\), \(К=3\) имеем:
| Номер | 1 слагаемое | 2 слагаемое | 3 слагаемое |
|---|---|---|---|
| 1 | 4 | 0 | 0 |
| 2 | 3 | 1 | 0 |
| 3 | 3 | 0 | 1 |
| 4 | 2 | 2 | 0 |
| 5 | 2 | 1 | 1 |
| 6 | 2 | 0 | 2 |
| 7 | 1 | 3 | 0 |
| 8 | 1 | 2 | 1 |
| 9 | 1 | 1 | 2 |
| 10 | 1 | 0 | 3 |
| 11 | 0 | 4 | 0 |
| 12 | 0 | 3 | 1 |
| 13 | 0 | 2 | 2 |
| 14 | 0 | 1 | 3 |
| 15 | 0 | 0 | 4 |
Входные данные
В первой строке входного файла записана последовательность чисел. Если первое число \(0\), то необходимо найти разбиение по номеру, а если \(1\), то номер по разбиению. В первом случае далее в файле записано количество слагаемых, сумма и номер разбиения. Во втором случае далее в файле записано количество слагаемых \(K\) и затем разбиение (\(K\) неотрицательных чисел, сумма которых \(N\)). Все числа разделены пробелами.
Выходные данные
Выведите в выходной файл разбиение либо номер.
Примеры
Входные данные
0 3 4 9
Выходные данные
1 1 2
Входные данные
1 3 0 1 3
Выходные данные
14
#111295
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Маленький Вася очень любит поезда. На день рождения ему подарили игрушечную железную дорогу. В комплект к железной дороге входит поезд, состоящий из \(n\) вагонов, пронумерованных числами от 1 до \(n\).
Любимым занятием Васи стала сортировка поездов с использованием специального сортировочного тупика.
Справа к тупику подъезжает поезд, составленный из всех \(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
Отображать по:
Выбрано
:
|