Codeforces Round 761 (Div. 2) |
---|
Закончено |
Лунный Новый год приближается, и Льдинка только что получила коробку конфет от бабушки с дедушкой! Коробка содержит $$$n$$$ конфет. $$$i$$$-я конфета имеет вкус $$$a_i$$$.
Льдинка верит, что хорошие вещи случаются парами. К сожалению, вкусы всех конфет попарно различны (все $$$a_i$$$ различны). Льдинка хочет сделать равные вкусы хотя бы у одной пары конфет.
Поэтому она попросила бабушку с дедушкой выполнить несколько замен. Перед выполнением замен Льдинка выбирает две конфеты с номерами $$$x$$$ и $$$y$$$ ($$$1 \le x, y \le n$$$, $$$x \ne y$$$).
За одну замену дедушка и бабушка Льдинки выбирают неотрицательное целое число $$$k$$$ такое, что $$$2^k \ge a_x$$$, и заменяют вкус $$$x$$$-й конфеты с $$$a_x$$$ на $$$2^k - a_x$$$ (то есть, присваивают $$$a_x := 2^k - a_x$$$).
Замены прекратятся только при условии, что $$$a_x = a_y$$$. Заметьте, что другие пары равных по вкусу конфет не остановят процесс.
У Льдинки умные бабушка и дедушка, поэтому они выберут такую последовательность замен, которая минимизирует количество требуемых замен. Поскольку Льдинка любит доставлять неприятности, она хочет максимизировать минимальное требуемое количество замен, выбрав соответствующие $$$x$$$ и $$$y$$$. Она задаётся вопросом, как выбрать такую пару $$$(x, y)$$$, что минимальное требуемое количество замен максимально среди всех возможных пар $$$(x, y)$$$.
Так как у Льдинки не очень хорошо с математикой, она надеется, что вы поможете ей решить эту задачу.
Первая строка ввода содержит единственное целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — количество конфет.
Вторая строка ввода содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$).
Гарантируется, что все $$$a_i$$$ различны.
Выведите три целых числа $$$x$$$, $$$y$$$ и $$$m$$$.
$$$x$$$ и $$$y$$$ являются номерами оптимальных конфет для применения замен. Ваш ответ должен удовлетворять $$$1 \le x, y \le n$$$, $$$x \ne y$$$.
$$$m$$$ является минимальным количеством замен, чтобы сделать $$$a_x = a_y$$$. Можно показать, что $$$m \le 10^9$$$ для любой пары конфет.
5 5 6 7 8 9
2 5 5
2 4 8
1 2 2
В первом тесте минимальное количество замен, требуемое, чтобы заменить конфету со вкусом $$$6$$$ на конфету со вкусом $$$9$$$, является $$$5$$$. Последовательность замен следующая: $$$6 \rightarrow 2 \rightarrow 0 \rightarrow 1 \rightarrow 7 \rightarrow 9$$$.
Во втором тесте минимальное количество замен, требуемое, чтобы заменить конфету со вкусом $$$4$$$ на конфету со вкусом $$$8$$$, является $$$2$$$. Последовательность замен следующая: $$$4 \rightarrow 0 \rightarrow 8$$$.
Название |
---|