Очередная карточная игра

Автор задачи: Антон Вдовин, разработчик: Даниил Орешников

Для начала поймем, что за $$$2n$$$ запросов такая задача решается тривиально — первые $$$n$$$ запросов потратим, чтобы по одному разу перевернуть каждую пару карточек с соседними номерами, после чего мы будем знать все их значения. И вторые $$$n$$$ запросов потратим, чтобы переворачивать уже карточки с одинаковыми значениями.

Теперь осталось соптимизировать наше решение на один запрос. Для этого нам дана дополнительная информация: для двух карточек известно, значение на какой из них меньше, чем на другой. Будем делать следующее: как и в изначальном решении, будем переворачивать подряд идущие пары карточек и запоминать их значения. При этом

Что останется после такого прохода по последовательности карточек? Во-первых, мы потратили $$$n - 1$$$ запрос на первый переворот каждой карточки, кроме $$$a$$$ и $$$b$$$. Во-вторых, ко всем карточкам, кроме $$$a$$$ и $$$b$$$, нашлась пара. Соответственно, осталось четыре карточки — $$$a$$$, $$$b$$$, $$$c$$$ и $$$d$$$, и для $$$c$$$ и $$$d$$$ мы знаем их значения.

Сделаем последние два запроса — перевернем вместе $$$a$$$ и минимальную по значению из $$$c$$$ и $$$d$$$, а затем $$$b$$$ и оставшуюся последнюю. Так как мы знаем, что все карточки разбиваются по значениям на пары одинаковых, очевидно, что за такие последние два действия мы перевернули две пары одинаковых. Всего было потрачено $$$2n - 1$$$ запросов.