#P11413. Lucky Number Position in Permutation Construction

    ID: 13491 Type: Default 1000ms 256MiB

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:

  1. 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.
  2. 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