Задача №3140. Феодальные отношения
Во Флатландии с некоторых пор процветают феодальные отношения – у каждого порядочного феодала есть ровно два вассала, у непорядочных – вассалов нет совсем. Каждый феодал строит свой замок в городе на прямой, при этом:
- высота замка (всегда целое положительное число) должна быть строго больше высот замков его вассалов (для соблюдения субординации).
- замки первого из двух вассалов и всех вассалов этого вассала должны быть построены слева, второго вассала и его вассалов – справа (для пресечения междоусобиц). Это правило должно выполняться для всех
- высота замка должна быть минимально возможной (для экономии ресурсов)
- число всех подчиненных (непосредственно или через промежуточных) у правого и левого вассалов одинаково (для баланса сил).
Для удобства замки феодалов занумерованы натуральными числами по порядку слева направо, начиная с единицы, и разбиты на улицы. Улица (i, j) представляет собой последовательность подряд идущих замков, начиная с замка под номером i и заканчивая замком с номером j (i ≤ j)
Однажды в город приехал новый феодал и пожелал выкупить там замок у одного из жителей. Также ему стало интересно узнать социальный статус соседей по улице, однако, город к тому времени так разросся, что феодал уже не мог сделать этого самостоятельно. Напишите программу, которая поможет ему!
Первая строка входного файла содержит число N (1 ≤ N ≤ 30000) — высота замка единственного главного феодала в городе, который никому не подчиняется. Далее, в следующих двух строках идут числа i и j (\(0 \leq i, j < 10^{10000}\)), задающие улицу (i, j), на которой хочет приобрести замок новый феодал (гарантируется, что замки с номерами i и j находятся в черте города, i ≤ j, j – i ≤ 105).
В выходной файл требуется вывести высоты всех замков на указанной улице слева направо через пробел.
Будут оцениваться и частичные решения задачи при малых N. Частичные решения для N<20 набирают до 40 баллов, а для N<50 набирают не более 70 баллов.
Ввод | Вывод |
|
|
|
|
|
|