Плюсануть
Поделиться
Класснуть
Запинить


Условие задачи Прогресс
ID 27024. Вывод паролей
Темы: Перестановки   

Однажды, на уроке информатики Леше Васильеву дали придумать специальную задачу с перестановками для Дамира. 
Леше очень понравилась эта затея, поэтому он взял ноутбук с полки, включил и заметил, что Антон Витальевич сменил пароли.
Леше известно, что пароль содержит в себе все символы максимальной лексикографической строки S, однако у него не так много времени на перебор, задачи необходимо сдать через 40 минут!
Помогите Леше и напишите программу, которая способна вывести все варианты паролей для строки S.
Пароли выводятся в алфавитном порядке.

Ввод Вывод
lesha
ahs
ash
has
hsa
sah
sha


(с) Александр Мамаев

ID 27025. Матвей и замок
Темы: Перестановки   

Всемирно известному взломщику Матвею поступил заказ на инновационный сейф, выпущенный компанией "British Scientists, Inc". Этот сейф почти целиком сделан из адамантита, не поддающемуся ни одной из дрелей Матвея. Поэтому его единственным уязвимым местом является патентованный кодовый замок. К счастью, Матвей похитил чертежи сейфа ещё во время его разработки, поэтому точно знает принцип работы замка.

Код вводится с помощью клавиатуры с числами от нуля до девяти. Как только введено необходимое количество цифр, код проверяется по следующему алгоритму. К нулю прибавляется первая введённая цифра, затем отнимается вторая, потом эта разность умножается на третью, и наконец, результат нацело делится на четвёртую. Потом этот алгоритм повторяется для следующих четырёх цифр, и так, пока они не кончатся. Если количество цифр не делится на четыре, то лишние действия просто отбрасываются.  Если при выполнении алгоритма встречается деление на ноль, то он тут же аварийно завершает работу, блокируя сейф. Если в результате получилось число X - секретная константа, которую Матвей тоже знает - замок открывается. 
Матвей внимательно изучил клавиатуру и понял, что по отпечаткам пальцев на кнопкам он может определить, какие цифры используются в коде, и сколько раз. Тут ему стало интересно - а сколько всего комбинаций, подходящих под эти данные, открывают замок? Комбинации считаются различными, если в них отличается порядок следования цифр. 
Но увы, с математикой у Матвея не очень, поэтому, без труда выполнив заказ, он задал этот вопрос всемирно известному хакеру - Вам. Помогите Матвею. 
 
Входные данные
В первой строке на вход подаются два числа N (1 <= n <= 8) и Х (1 <= X <= 10^9) - количество цифр в коде и секретная константа. Во второй находится n цифр, разделённых пробелами. Разумеется, цифры могут повторяться. 
 
Выходные данные
Вывести необходимо единственное число - ответ на вопрос Матвея.

Ввод Вывод
4 0
2 2 3 6
4
2 1
1 1
0

(с) Данииил Кирионенко

ID 27089. Двоичные строки заданной длины
Темы: Перестановки   

По данному числу N выведите все строки длины N из нулей и единиц в лексикографическом порядке.

Входные данные
Задано единственное число N (натуральное, \(1 <= N <= 10\))

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


Примеры
Входные данные Выходные данные
1 2 00
01
10
11

ID 27088. Все двоичные строки длины n, содержащие ровно k единиц
Темы: Перестановки   

По данным числам N и K выведите все строки из нулей и единиц длины N, содержащие ровно K единиц, в лексикографическом порядке.

Входные данные
Заданы 2 числа: N и (\(0 <= K <= N\), \(0 <= N <= 100\)).

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


Примеры
Входные данные Выходные данные
1 4 2 0011
0101
0110
1001
1010
1100

ID 27087. Гладкие числа
Темы: Перестановки   

Назовем число гладким, если его цифры, начиная со старшего разряда, образуют неубывающую последовательность. Упорядочим такие числа в возрастающем порядке и присвоим каждому номер. Требуется по номеру N вывести N-ое гладкое число.

Входные данные
На вход программы поступает номер N (\(1 <= N <= 2147483647\)).

Выходные данные
Выведите соответствующее номеру N гладкое число.



Примеры
Входные данные Выходные данные
1 3 3
2 11 12

ID 38309. Ставки
Темы: Перестановки   

Перед началом тараканьих бегов всем болельщикам было предложено сделать по две ставки на результаты бегов. Каждая ставка имеет вид "Таракан №A придет раньше, чем таракан №B".

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

Входные данные
В первой строке входных данных содержатся два разделенных пробелом натуральных числа: число K, не превосходящее 10, - количество тараканов и число N, не превосходящее 100, - количество болельщиков. Все тараканы пронумерованы числами от 1 до K. Каждая из следующих N строк содержит 4 натуральных числа A, B, C, D, не превосходящих K, разделенных пробелами. Они соответствуют ставкам болельщика "Таракан №A придет раньше, чем таракан №B" и "Таракан №C придет раньше, чем таракан №D".

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

Если требуемого результата добиться нельзя, выведите одно число 0.

Примеры
Входные данные Выходные данные
1 3 2
2 1 2 3
1 2 3 2
3 2 1
2 3 4
1 2 1 3
1 2 3 1
1 2 2 3
1 2 3 2
0


Примечание: Решения задачи на языке программирования Python не проходят ограничения по времени.

ID 38635. Карточки
Темы: Перестановки   

На день рождения Пете подарили набор карточек с буквами. Теперь Петя с большим интересом составляет из них разные слова. И вот, однажды, составив очередное слово, Петя заинтересовался вопросом: "А сколько различных слов можно составить из тех же карточек, что и данное?". Помогите ему ответить на этот вопрос.

Входные данные
Вводится слово, составленное Петей – строка из маленьких латинских букв не длиннее 15 символов.

Выходные данные
Выведите одно целое число – искомое количество слов.
 

Примеры
Входные данные Выходные данные
1 solo 12

ID 38636. По номеру
Темы: Перестановки   

Найдите перестановку по её номеру в лексикографическом порядке.

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

Выходные данные
Выведите N чисел – искомую перестановку.

Примеры
Входные данные Выходные данные
1 3
2
1 3 2

ID 38637. Следующая
Темы: Перестановки   

Вам дана перестановка из первых N натуральных чисел. Найдите по ней следующую в лексикографическом порядке (будем считать, что за перестановкой N N-1 ... 3 2 1 следует тождественная перестановка, то есть, 1 2 3 ... N).

Входные данные
В первой строке входных данных содержится число N (1 <= N <= 10000). Во второй строке находится перестановка (последовательность натуральных чисел от 1 до N, разделенных пробелами).

Выходные данные
Требуется вывести искомую перестановку.

Примеры
Входные данные Выходные данные
1 3
1 3 2
2 1 3

ID 38876. Без неподвижных точек
Темы: Перестановки   

Перестановкой n элементов называется массив из различных натуральных n чисел, каждое из которых от 1 до n. Например, все перестановки 3 элементов: [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1].
Элементы перестановки пронумерованы от 1 до n, например для перестановки a = [3, 1, 2] выполнено a[1] = 3, a[2] = 1, a[3] = 2. Элемент с номером i называется неподвижной точкой, если a[i] = i. Так, в перестановке [3, 1, 2] нет неподвижный точек, а в перестановке [1, 3, 2] элемент a[1] = 1 является неподвижной точкой.
Упорядочим все перестановки лексикографически — сначала по первому элементу, потом по второму, и так далее. В начале условия все перестановки трех элементов приведены в лексикографическом порядке. Оставим только те перестановки, которые не содержат неподвижных точек. Для n = 3 останутся перестановки [2, 3, 1] и [3, 1, 2].
По заданным n и t требуется вывести первые t в лексикографическом порядке перестановок n элементов без неподвижных точек. Перестановки следует выводить в лексикографическом порядке.

Входные данные
На ввод подаются два целых числа n и t (2 ≤ n ≤ 1000, 1 ≤ t ≤ 104, nt ≤ 105 ). Гарантируется, что существует хотя бы t перестановок n элементов без неподвижных точек.

Выходные данные
Выведите t строк, на i-й из них выведите n чисел: i-ю в лексикографическом порядке перестановку n элементов без неподвижных точек.

Примеры
Входные данные Выходные данные
1 3 1 2 3 1