Имя: Пароль: Зарегистрироваться Восстановить пароль
10/12/2023 03:35:33

# Рабочее место участника

## Задачи

985. BitSort

Ограничения: время – 1s/2s, память – 16MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение 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 number Binary 32 bit representation 1 0 0000\ 0000\ 0000\ 0000\ 0000\ 0000\ 0000\ 0000 2 1 0000\ 0000\ 0000\ 0000\ 0000\ 0000\ 0000\ 0001 3 2 0000\ 0000\ 0000\ 0000\ 0000\ 0000\ 0000\ 0010 4 4 0000\ 0000\ 0000\ 0000\ 0000\ 0000\ 0000\ 0100 5 3 0000\ 0000\ 0000\ 0000\ 0000\ 0000\ 0000\ 0011 6 5 0000\ 0000\ 0000\ 0000\ 0000\ 0000\ 0000\ 0101
with m\ =\ -5 and n\ =\ -2, the result of the sorting will be
 No. Decimal number Binary 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