Baby Goat Lineup
Time limit2sMemory limit128 MB
Given binary labels A through B, find the X-th label when ordered first by popcount then by numeric value.
- Level
Medium6 of 10
- Topics
- Combinatorics, Bit manipulation, Binary search
- Solved
- No attempts yet
Problem
Baby goats are standing in line for dinner. Each goat wears a binary label made only of 0 and 1, and every label has length at most 31 bits.
They do not line up in the usual increasing binary order 0, 1, 10, 11, 100, .... Instead, they use the following priority rules.
- A goat whose label contains fewer
1bits stands earlier. - If two labels contain the same number of
1bits, the smaller binary value stands earlier.
For instance, 1000 comes before 110 because 1000 has one 1 bit and 110 has two. If all labels from 100 through 1111 are ordered by this rule, the order is as follows.
100, 1000, 101, 110, 1001, 1010, 1100, 111, 1011, 1101, 1110, 1111
Except for the label exactly equal to 0, no label may start with 0.
Given all goats with labels from A through B, find the label of the X-th goat after sorting by the priority rules above.
Input
The first line contains A.
The second line contains B.
The third line contains the position X of the goat to find. The first goat has position 1.
Output
Print the label of the goat at that position.