#P11413. Lucky Number Position in Permutation Construction
Lucky Number Position in Permutation Construction
Lucky Number Position in Permutation Construction
Given a positive integer n and a lucky number k, you are to construct a permutation A1,A2,…,An by placing the numbers from 1 to n one by one into an initially zero-filled array of length n. The placement is performed as follows:
Step 1: If i = 1, place 1 at the leftmost position (i.e. position 1).
Step 2: If i = 2, place 2 at the rightmost position (i.e. position n).
Step 3: For each number i with i ≥ 3, consider every free position j (1-indexed) in the array and define:
- f0(j): the number of consecutive 0's ending at position j (i.e. counting from j and moving leftwards). In other words, if you start at j and count how many successive positions (including j) hold 0 until a nonzero is encountered. For indices x ≤ 0, we define f0(x) = n + 1.
- g0(j): the number of consecutive 0's starting at position j (i.e. counting from j and moving rightwards). For indices x > n, define g0(x) = n + 1.
Similarly, define:
- f1(j): the number of consecutive nonzero positions ending at j. For x ≤ 0, define f1(x) = 0.
- g1(j): the number of consecutive nonzero positions starting at j. For x > n, define g1(x) = 0.
The placement rule for i ≥ 3 is as follows:
- If there exists a free position j with \(\min(f0(j), g0(j)) > 1\), choose the one that maximizes \(\min(f0(j), g0(j))\). In case of a tie, choose the smallest j.
- If no such position exists, choose a free position j for which f0(j) = 1, and among these, select the one that minimizes \( f1(j-1) + g1(j+1) \). Again, in case of a tie, choose the smallest j.
The process is repeated for each number from 1 to n sequentially. Your task is to determine the final 1-indexed position of the lucky number k in the permutation.
inputFormat
The input consists of a single line containing two integers n and k (with 1 ≤ k ≤ n).
outputFormat
Output a single integer that is the 1-indexed position at which the lucky number k is placed.
sample
5 3
3