Подразделы

Другие разделы

Дата и время

09/04/2025 23:56:49

Авторизация

Лето 6

A. Метрополитен B. Очень легкая задача C. Шахматная доска D. Интересный треугольник E. Galaxy F. Robot G. Schedule H. Ancestor I. Grid J. Hosting K. BitSort

K. 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 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

Sample Input 2

-5 -2 2

Sample Output 2

-5

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