Baltic OI '16 P6 - Swap - DMOJ: Modern Online Judge

Baltic OI '16 P6 - Swap

View as PDF

Submit solution

All submissions

Best submissions

Points: 15 (partial)

Time limit: 1.0s

Memory limit: 256M

Problem type

Baltic Olympiad in Informatics: 2016 Day 2, Problem 3

You are given a sequence of $n$ ~n~ numbers $x_1, x_2, \dots, x_n$ ~x_1, x_2, \dots, x_n~. Each number $1, 2, \dots, n$ ~1, 2, \dots, n~ appears exactly once in the sequence.

You can modify the sequence using swaps. There are $n-1$ ~n-1~ consecutive turns numbered $k = 2, 3, \dots, n$ ~k = 2, 3, \dots, n~. On turn $k$ ~k~ you can either swap values $x_k$ ~x_k~ and $x_{\lfloor k/2 \rfloor}$ ~x_{\lfloor k/2 \rfloor}~ in the sequence or do nothing.

Sequence $a_1, a_2, \dots, a_n$ ~a_1, a_2, \dots, a_n~ is lexicographically smaller than sequence $b_1, b_2, \dots, b_n$ ~b_1, b_2, \dots, b_n~ if there exists an index $j$ ~j~ $(1 \le j \le n)$ ~(1 \le j \le n)~ such that $a_k = b_k$ ~a_k = b_k~ for all $k < j$ ~k < j~ and $a_j < b_j$ ~a_j < b_j~.