Permutations

Plus

Problem description Progress

ID 27024. password output

Once, at a computer science lesson, Lesha Vasilyev was given a special task with permutations for Damir.

Lesha really liked this idea, so he took the laptop from the shelf, turned it on and noticed that Anton Vitalyevich had changed his passwords.

Lesha knows that the password contains all the characters of the maximum lexicographic string S, but he does not have much time to search, the tasks must be submitted in 40 minutes!

Help Lesha and write a program that can display all password options for the string S.

Passwords are displayed in alphabetical order.

Enter	Output
lesha	ahs ash has hsa sah sha

(с) Alexander Mamaev

ID 27025. Matthew and the castle

Темы: Permutations

The world-famous burglar Matvey received an order for an innovative safe produced by British Scientists, Inc. This safe is almost entirely made of adamantite, which does not lend itself to any of Matvey's drills. Therefore, its only weak point is a patented combination lock. Fortunately, Matvey stole the blueprints of the safe during its development, so he knows exactly how the lock works.

The code is entered using a keypad with numbers from zero to nine. As soon as the required number of digits is entered, the code is checked according to the following algorithm. The first entered digit is added to zero, then the second is subtracted, then this difference is multiplied by the third, and finally, the result is completely divided by the fourth. Then this algorithm is repeated for the next four digits, and so on until they run out. If the number of digits is not divisible by four, then the extra actions are simply discarded. If a division by zero is encountered during the execution of the algorithm, then it immediately crashes, blocking the safe. If the result is the number X - a secret constant that Matvey also knows - the lock opens.

Matvey carefully studied the keyboard and realized that he could determine from the fingerprints on the buttons which numbers are used in the code, and how many times. Then he became interested - how many combinations that fit this data open the lock? Combinations are considered different if they have a different order of numbers.

But alas, Matvey is not very good at mathematics, therefore, having easily completed the order, he asked this question to the world-famous hacker - you. Help Matvey.

Input

The first line contains two numbers N (1 <= n <= 8) and X (1 <= X <= 10^9) - the number of digits in the code and a secret constant. The second contains n digits separated by spaces. Of course, numbers can be repeated.

Output

It is necessary to output a single number - the answer to Matvey's question.

Enter	Output
40 2 2 3 6	4
2 1 1 1	0

ID 27089. Binary strings of given length

Темы: Permutations

Given the number N print all strings of length N consisting of zeros and ones in lexicographic order.

Input
Given a single number N (natural, \(1 <= N <= 10\))

Imprint
It is necessary to output all strings of length N consisting of zeros and ones in lexicographic order, one per line.

Examples

#	Input	Output
1	2	00 01 10 11

ID 27088. All binary strings of length n containing exactly k ones

Темы: Permutations

Given numbers N and K print all strings of zeros and units of length N that contain exactly K units, in lexicographic order.

Input
Given 2 numbers: N and K (\(0 <= K <= N\), \(0 <= N <= 100\)).

Imprint
It is necessary to output all strings of zeros and ones of length N that contain exactly K ones, in lexicographic order.

Examples

#	Input	Output
1	4 2	0011 0101 0110 1001 1010 1100

ID 27087. smooth numbers

Темы: Permutations

Let's call a number smooth if its digits form a non-decreasing sequence starting from the most significant digit. Sort these numbers in ascending order and assign a number to each. Required by number N output N-th smooth number.

Input
The program input number N (\(1 <= N <= 2147483647\)).

Imprint
Print corresponding to the number N smooth number.

Examples

#	Input	Output
1	3	3
2	11	12

ID 38309. Rates

Темы: Permutations

Before the start of the cockroach race, all fans were asked to make two bets on the results of the race. Each bet has the form "Cockroach #A will come before cockroach #B".

The organizers of the race decided to find out if the cockroaches could come in such an order that each fan had exactly one bet out of two played (that is, exactly one of the two statements of each fan turned out to be true). It is believed that no two cockroaches can reach the finish line at the same time.

Input
The first line of the input contains two positive integers separated by a space: the number K, not exceeding 10, is the number of cockroaches, and the number N, not exceeding 100, is the number of fans. All cockroaches are numbered from 1 to K. Each of the next N lines contains 4 natural numbers A, B, C, D, not exceeding K, separated by spaces. They match the fan's bets "Cockroach #A will come before cockroach #B" and "Cockroach #C will come before cockroach #D".

Imprint
If you finish the race so that each of the fans plays exactly one of the two bets, then you should print the numbers of cockroaches in the order in which they appear in the final table of results (first the number of the cockroach that came first, then the number of the cockroach that came second etc.) into one line separated by a space. If there are several such options, print any of them.

If the desired result cannot be achieved, print a single number 0.

Examples

#	Input	Output
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

Note: Solutions to the problem in the programming language Python do not pass the time limit.

ID 38635. Cards

Темы: Permutations

For his birthday, Petya was presented with a set of cards with letters. Now Petya with great interest makes different words out of them. And so, one day, having composed another word, Petya became interested in the question: “How many different words can be made from the same cards as the given one?”. Help him answer this question.

Input
A word composed by Petya – a string of small latin letters no longer than 15 characters.

Imprint
Print a single integer – the desired number of words.

Examples

#	Input	Output
1	solo	12

ID 38636. By number

Темы: Permutations

Find the permutation by its number in lexicographic order.

Input
The first line of the input contains the number N (1 <= N <= 12) – the number of elements in the permutation, in the second – number K (1 <= K <= N!) – permutation number.

Imprint
Print N numbers – desired permutation.

Examples

#	Input	Output
1	3 2	1 3 2

ID 38637. Next

Темы: Permutations

You are given a permutation of the first N natural numbers. Find the next one in the lexicographic order (we will assume that the permutation N N-1 ... 3 2 1 is followed by the identical permutation, that is, 1 2 3 ... N).

Input
The first line of the input contains the number N (1 <= N <= 10000). The second line contains a permutation (a sequence of natural numbers from 1 to N separated by spaces).

Imprint
It is required to output the desired permutation.

Examples

#	Input	Output
1	3 1 3 2	2 1 3

ID 38876. No fixed points

Темы: Permutations

A permutation of n elements is an array of n different natural numbers, each of which is from 1 to n. For example, all permutations of 3 elements: [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [ 3, 2, 1].
The elements of a permutation are numbered from 1 to n, for example, for a permutation a = [3, 1, 2] we have a[1] = 3, a[2] = 1, a[3] = 2. The element with number i is called a fixed point , if a[i] = i. Thus, in the permutation [3, 1, 2] there are no fixed points, and in the permutation [1, 3, 2] the element a[1] = 1 is a fixed point.
Let's order all permutations lexicographically — first on the first element, then on the second, and so on. At the beginning of the condition, all permutations of the three elements are listed in lexicographic order. We leave only those permutations that do not contain fixed points. For n = 3, the permutations [2, 3, 1] and [3, 1, 2] will remain.
Given n and t, print the first t in the lexicographic order of permutations of n elements without fixed points. Permutations should be output in lexicographical order.

Input
The input is two integers n and t (2 ≤ n ≤ 1000, 1 ≤ t ≤ 10⁴, nt ≤ 10⁵ ). It is guaranteed that there are at least t permutations of n elements without fixed points.

Imprint
Print t lines, on the i-th of them print n numbers: the i-th lexicographical permutation of n elements without fixed points.

Examples

#	Input	Output
1	3 1	2 3 1

ID 39514. One-two-three-four-five cow change

Темы: Formula derivation Fast exponentiation Permutations

N cows (1 ≤ N ≤ 10⁵) Farmer John stand in a row. The i-th cow on the left has label i (1 ≤ i ≤ N).
FD gave the cows M pairs of integers s (L₁,R₁)…(L_M,R_M), where 1 ≤ M≤ 100. Then he told the cows to repeat exactly K (1 ≤ K ≤ 10⁹) times the process of M steps:

For every i from 1 to M:
The sequence of cows in positions Li…Ri on the left reverses their order.
Print the labels of all cows from left to right for each i, (1 ≤ i ≤ N) after the process is completed.

Input
The first line contains the numbers N, M, K. For each 1 ≤ i≤ M string i+1 contains L_i and R_i, two integers in the interval 1…N, where L_i<R_i.

Imprint
On the i-th line of the output, print the i-th element of the array after executing all instructions K times.

Examples

#	Input	Output	Explanation
1	7 2 2 25 3 7	1 2 4 3 5 7 6	Initially, the order of cows from left to right is [1,2,3,4,5,6,7] After the first step of the process, the order will be [1,5,4,3,2,6,7] After the second step of the process, the order will become [1,5,7,6,2,3,4]. Repeating both steps one more time we get the result shown in the output.

ID 39575. Dance moves

Темы: Depth walk Permutations

Farmer John's cows are dancing.
First, all N cows (2≤N≤10⁵) are in a row and cow i is in position i. The sequence of dance movements is given by K (1≤K≤2⋅10⁵) pairs of positions (a₁,b₁),(a₂,b₂),…,(a_K,b_K). Every minute i=1…K of the dance, the cows in positions a_i and b_i change places. The same K exchanges are made on minutes K+1*2K, then again on minutes 2K+1*3K, and so on. In other words,

at minute 1 the cows at positions a₁ and b₁ are swapped.
at minute 2, the cows at positions a₂ and b₂ are swapped.
...
At minute K, the cows at positions a_K and b_K swap.
At minute K+1, the cows at positions a₁ and b₁ are swapped.
At minute K+1, the cows at positions a₂ and b₂ are swapped.
etc. ...
For each cow, determine the number of unique positions it will visit during the endless dance.

Input
The first line of input contains the integers N and K. Each of the subsequent K lines contains (a₁,b₁)…(a_K, b_K) (1≤a_i<b_i≤N).
Imprint
Print N lines, where the i-th line contains the number of unique positions that cow i will visit.

Examples

#	Input	Output	Explanation
1	5 4 13 12 2 3 24	4 4 3 4 1	Cow 1 will reach positions {1,2,3,4}. Cow 2 will reach positions {1,2,3,4}. Cow 3 will reach positions {1,2,3}. Cow 4 will reach positions {1,2,3,4}. Cow 5 will not move and will not leave position 5.