Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb. Question by Halil Karimis.
Sultan's Game
Question:
One day, the sultan's most trusted vizier died in battle.
Sultan wants to choose a vizier from his soldiers.
But it was hard choice for Sultan to select just
one man from available n. So Sultan decides to
prepare such a game that will help him to choose
new vizier.
First of all, Sultan asks to his
soldiers to take a unique number (from 1 to n).
The rules of Sultan`s game is simple: he arrange
soldiers by their numbers in increasing order.
Then he eliminates all soldiers whom were standing
in 1, 3, 5… positions. After last soldier
eliminated Sultan rearrange soldiers by using
same rule and starts elimination game again.
Sultan`s game continues until just one
soldier left. So Sultan promotes this soldier
to vizier position.
Input specification
The number of soldiers (n ≤ 10.000)
Soldiers' name and the unique numbers
(from 1 to n) selected by those soldiers.
Output specification
Print the name of the soldier to be vizier.
Sample Input I |
Sample Input II |
3
Besnik 3
Dorjan 1
Alban 2
|
8
Jurgen 7
Ermir 5
Ardit 2
Irdi 6
Ervis 1
Gerald 4
Ditmir 3
Ideal 8
|
Sample Output I |
Sample Output II |
Alban
|
Ideal
|
Для отправки решений необходимо выполнить вход.
|