Темы --> Информатика --> Алгоритмы --> Перебор --> Комбинаторные структуры --> Размещения с повторениями
---> 11 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 1 2 3 >> Отображать по:
#157
Монетки
  
Максимальное время работы на одном тесте: 1 секунда

В Волшебной стране используются монетки достоинством A1, A2,..., AM. Волшебный человечек пришел в магазин и обнаружил, что у него есть ровно по две монетки каждого достоинства. Ему нужно заплатить сумму N. Напишите программу, определяющую, сможет ли он расплатиться без сдачи.

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

На вход программы  сначала поступает число N (1 <= N <= 109), затем - число M (1 <= M <= 15) и далее M попарно различных чисел A1, A2,..., AM (1 <= Ai <= 109).

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

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

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

Примеры
Входные данные
100 6
11 20 30 40 11 99
Выходные данные
3
40 30 30
#192
По размещению!
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

По размещению найдите его номер в лексикографическом порядке.


В отличие от сочетаний, размещения учитывают порядок следования предметов. Так, например, наборы (2,1,3) и (3,2,1) являются различными, хотя состоят из одних и тех же элементов {1, 2, 3} (то есть совпадают как сочетания).

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

В первой строке входных данных находятся числа N и K (1 <= K <= N <= 12). Во второй строке записаны K чисел из диапазона от 1 до N – размещение.

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

Выведите единственное число – номер данного размещения.

Примеры
Входные данные
3 2
3 2
Выходные данные
6
#195
Обратная перестановка
  
Максимальное время работы на одном тесте: 1 секунда

По данной перестановке π требуется найти π-1.

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

В первой строке  входных данных содержится число 0 < N <= 20000 – количество элементов в перестановке π. Во второй строке записана сама перестановка π.

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

Выведите π-1

Примеры
Входные данные
3
2 3 1
Выходные данные
3 1 2
#196
Степень перестановки
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Максимальное время работы на одном тесте: 1 секунда

Найдите степень данной перестановки π.

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

В первой строке входных данных содержится число 0 < N <= 100 – количество чисел в перестановке π. Во второй строке записана сама перестановка π.

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

Требуется вывести степень данной перестановки.

Примеры
Входные данные
3
2 3 1
Выходные данные
3
#197
Восстановление перестановки
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Максимальное время работы на одном тесте: 1 секунда

Пусть дана перестановка π. Обозначим φ[i] - количество таких j, что π[j] > π[i], а j < i. φ называется таблицей инверсий перестановки π. Требуется по данной таблице инверсий восстановить перестановку.

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

В первой строке входных данных содержится число 0 < N <= 2000 - количество чисел в перестановке π. Во второй строке записана таблица инверсий φ.

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

Выведите искомую перестановку  π.

Примеры
Входные данные
3
0 0 2
Выходные данные
2 3 1
Страница: << 1 2 3 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест