21/11/2024 19:51:02

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

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

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

03/07/2008	Лето 2008 дорешивание ( 6K)
14/07/2008	Лето 2008 - 6 (K)