printЛето 6

printK. BitSort

Ограничения: время – 1s/2s, память – 16MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Let's consider the 32 bit representation of all integers `i` from `m` up to `n` inclusive (`m\ ≤\ i\ ≤\ n`; `m*n\ ≥\ 0`, `-2^31\ ≤\ m\ <\ n\ ≤\ 2^31-1`). Note that a negative number is represented in 32 bit Additional Code.
That is the 32 bit sequence, the binary sum of which and the 32 bit representation of the corresponding positive number is `2^32`. For example, the 32 bit representation of 6 is `0000\ 0000\ 0000\ 0000\ 0000\ 0000\ 0000\ 0110` and the 32 bit representation of –6 is `1111\ 1111\ 1111\ 1111\ 1111\ 1111\ 1111\ 1010`.
Let's sort the 32 bit representations of these numbers in increasing order of the number of bit 1. If two representations have the same numbers of bit 1, they are sorted in lexicographical order.
For example, with `m\ =\ 0` and `n\ =\ 5`, the result of the sorting will be
No.Decimal numberBinary 32 bit representation
10`0000\ 0000\ 0000\ 0000\ 0000\ 0000\ 0000\ 0000`
21`0000\ 0000\ 0000\ 0000\ 0000\ 0000\ 0000\ 0001`
32`0000\ 0000\ 0000\ 0000\ 0000\ 0000\ 0000\ 0010`
44`0000\ 0000\ 0000\ 0000\ 0000\ 0000\ 0000\ 0100`
53`0000\ 0000\ 0000\ 0000\ 0000\ 0000\ 0000\ 0011`
65`0000\ 0000\ 0000\ 0000\ 0000\ 0000\ 0000\ 0101`
with `m\ =\ -5` and `n\ =\ -2`, the result of the sorting will be
No.Decimal numberBinary 32 bit representation
1`-4``1111\ 1111\ 1111\ 1111\ 1111\ 1111\ 1111\ 1100`
2`-5``1111\ 1111\ 1111\ 1111\ 1111\ 1111\ 1111\ 1011`
3`-3``1111\ 1111\ 1111\ 1111\ 1111\ 1111\ 1111\ 1101`
4`-2``1111\ 1111\ 1111\ 1111\ 1111\ 1111\ 1111\ 1110`
Given `m`, `n` and `k` (`1\ ≤\ k\ ≤\ min(n-m+1,\ 2\ 147\ 473\ 547)`), your task is to write a program to find a number corresponding to `k`-th representation in the sorted sequence.
Input
The only line contains 3 integers `m`, `n` and `k`.
Output
Write the `k`-th number of the sorted numbers.

Sample Input 1

0 5 3

Sample Output 1

2

Sample Input 2

-5 -2 2

Sample Output 2

-5
Источник: РГУ им. И.Канта, осенний командный турнир, 2007
loading