codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

513B1.md (1414B)


      1 Source: https://codeforces.com/problemset/problem/513/B1
      2 
      3 B1. Permutations
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 You are given a permutation *p* of numbers 1, 2, ..., *n*. Let's define *f*(*p*) as the following sum:
     22 
     23 ![](https://espresso.codeforces.com/e12229ecd64f361940afe4756d3f3d51ca05a329.png)
     24 
     25 Find the lexicographically *m*-th permutation of length *n* in the set of permutations having the maximum possible value of *f*(*p*).
     26 
     27 Input
     28 
     29 The single line of input contains two integers *n* and *m* (1 ≤ *m* ≤ *cnt**n*), where *cnt**n* is the number of permutations of length *n* with maximum possible value of *f*(*p*).
     30 
     31 The problem consists of two subproblems. The subproblems have different constraints on the input. You will get some score for the correct submission of the subproblem. The description of the subproblems follows.
     32 
     33 * In subproblem B1 (3 points), the constraint 1 ≤ *n* ≤ 8 will hold.
     34 * In subproblem B2 (4 points), the constraint 1 ≤ *n* ≤ 50 will hold.
     35 
     36 Output
     37 
     38 Output *n* number forming the required permutation.
     39 
     40 Examples
     41 
     42 Input
     43 
     44 ```
     45 2 2
     46 ```
     47 
     48 Output
     49 
     50 ```
     51 2 1
     52 ```
     53 
     54 Input
     55 
     56 ```
     57 3 2
     58 ```
     59 
     60 Output
     61 
     62 ```
     63 1 3 2
     64 ```
     65 
     66 Note
     67 
     68 In the first example, both permutations of numbers {1, 2} yield maximum possible *f*(*p*) which is equal to 4. Among them, (2, 1) comes second in lexicographical order.