Карти
Карти
Колода складається з парної кількості карт. Карти занумеровано послідовними натуральними числами від 1 до 2n (для певного натурального n) включно. З колодою роблять таке:
1. Спочатку колоду ділять на дві рівні частини. В першу частину потрапляють карти, що стояли на непарних місцях, в другу — ті карти, що були на парних місцях:
(1, 2, … , 2n) (1, 3, 5, … , 2n – 1) + (2, 4, … , 2n)
2. З обох утворених частин викидають карту, що розташована у відповідній частині на місці 1 + [an/b] при 0 ≤ a < b ≤ 1000. Наприклад, якщо a = 0, b = 1, то буде викинуто першу карту:
(1, 3, 5, … , 2n – 1) (3, 5, 7, ... , 2n – 1)
(2, 4, 6, … , 2n) (4, 6, 8, … , 2n)
3. Другу частину кладуть поверх першої:
(3, 5, 7, ... , 2n – 1) + (4, 6, 8, … , 2n) (3, 5, 7, … , 2n – 1, 4, 6, 8, … , 2n)
Дії 1–3 повторюють доти, поки в колоді не залишиться лише 2 карти. Наприклад, якщо a = 1, b = 2, а початкова кількість карт - 5, маємо:
(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) (1, 3, 5, 7, 9) + (2, 4, 6, 8, 10)
(1, 3, 7, 9) + (2, 4, 8, 10) (1, 3, 7, 9, 2, 4, 8, 10) (1, 7, 2, 8) + (3, 9, 4, 10)
(1, 7, 8) + (3, 9, 10) (1, 7, 8, 3, 9, 10) (1, 8, 9) + (7, 3, 10)
(1, 9) + (7, 10) (1, 9, 7, 10) (1, 7) + (9, 10) (1) + (9) (1, 9),
бо 1 + [5∙1/2] = 3, 1 + [4∙1/2] = 3, 1 + [3∙1/2 ] = 2, 1 +[2∙1/2] = 2.
Визначте кінцевий стан колоди.
Вхідні дані
Містить 3 невід’ємні цілі числа n, a, b (2 ≤ n ≤ 500000).
Вихідні дані
Вивести два натуральних числа: номери карт, що залишаться. Номер нижньої карти потрібно вказати першим.
Приклад
5 1 2
1 9