Задача E. Загадочная последовательность ≡

Условие

Данная задача является интерактивной.

Долгое время мальчик Петя коллекционировал целые числа. Сейчас в его коллекции уже N чисел. Разумеется, Петя бережно относится к своей коллекции: не разбрасывает по квартире, и, более того, хранит её отсортированной по неубыванию.

Сегодня Петя решил, что хранить числа в отсортированном виде не так интересно, поэтому он хочет перемешать их и получить новую последовательность.

Неровностью последовательности называется сумма модулей разности почти соседних элементов. Два элемента последовательности являются почти соседними, если их номера отличаются ровно на K. Например, если K = 2, тогда почти соседними элементами являются числа на позициях 1 и 3, 2 и 4, 3 и 5 и т.д.

Петя уже очень хорошо знает математику, поэтому он смог написать формулу для подсчета неровности: ∑N − Ki = 1|a_i − a_i + K|. Теперь Петя хочет узнать минимальное значение неровности, которое можно получить для его коллекции после перестановки элементов. Вы должны ему с этим помочь.

Петя не готов просто так показывать свою коллекцию первому встречному, потому что боится, что её могут украсть. Но чтобы вы всё таки смогли ему помочь, он готов ответить на несколько вопросов касательно своей коллекции. А именно — он может назвать модуль разности между двумя любыми элементами последовательности. Петя может ответить лишь на Q вопросов, после этого он начнёт подозревать вас в попытке скопировать коллекцию.

Пояснение

Протокол взаимодействия

Сначала на вход программе-решению подаётся два целых числа N и K — количество чисел в последовательности и расстояние между почти соседними элементами.

Для каждого теста жюри зафиксировало число Q — максимальное количество вопросов, которые можно задать. Гарантируется, что Q вопросов достаточно, чтобы решить задачу. Это число не сообщается программе-решению. Если решение делает более Q вопросов, то на этом тесте оно получает в качестве результата тестирования "Wrong answer".

Чтобы задать вопрос программа-решение должна вывести строку вида "? i j", где i и j (1 ≤ i, j ≤ N) — целые числа, номера чисел в последовательности. В ответ на вопрос программа жюри подаёт на вход программе-решению значение |a_i − a_j| — модуль разности соответствующих элементов последовательности.

Если программа-решение определила ответ на задачу, она должна вывести строку "! ans", где ans — ответ на задачу. После этого программа-решение должна завершиться.

Гарантируется, что в каждом тесте числа в последовательности не изменяются в зависимости от вопросов программы-решения.

Каждый вопрос и вывод ответа должен заканчиваться символом перевода строки \n, а также необходимо выполнить сброс буфера:

Ограничения

1 ≤ N ≤ 10⁶

1 ≤ K ≤ 10³

1 ≤ a_i ≤ 10⁹

a₁ ≤ a₂ ≤ ...  ≤ a_N − 1 ≤ a_N

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.

По запросу сообщается результат окончательной проверки на каждом тесте.

Пояснение к примерам

Примеры из условия представлены таким образом, чтобы продемонстрировать взаимодействие программы-решения и программы жюри.

Обратите внимание, что первый и второй примеры относятся к первой подзадаче, а третий и четвёртый — ко второй.

В первом примере можно расположить первые четыре числа на четных позициях, а остальные числа — на нечетных.

Во втором примере выгоднее всего не менять расположение чисел.

В третьем примере исходная последовательность может быть следующей: 1 4 5 7 13. Расположить эти числа так, чтобы неровность была минимальна, можно несколькими способами. Например, 1 7 13 4 5. Тогда разница между почти соседними элементами равна: |1 − 4| + |7 − 5| = 3 + 2 = 5.

В четвёртом примере нет ни одной пары почти соседних элементов.

Примеры тестов

8 2

3

0

1

2

Ok

? 1 4

? 4 4

? 5 6

? 6 8

! 6

10 1

8

991

999

Ok

? 1 9

? 9 10

? 1 10

! 999

5 3

3

1

2

6

Ok

? 1 2

? 2 3

? 3 4

? 4 5

! 5

2 3

999999

999999

Ok

? 1 2

? 2 1

! 0

Разбор

Сразу отметим, что если N ≤ K, то ответ ноль, так как в последовательности нет ни одной пары почти соседних элементов.

Если K = 1, то выгоднее всего оставить последовательность отсортированной, так как в таком случае неровность будет равна разнице последнего и первого элементов.

Подход к решению

Рассмотрим случай, когда K = 2.

В таком случае требуется разбить исходную последовательность на два множества. Одно из них будет расположено на четных позициях итоговой последовательности, а другое — на нечетных. Размер первого множества равен M = N / 2 округленное вниз, а размер второго — N − M. В каждом множестве посчитаем разницу между максимальным и минимальным элементами. Можно заметить, что эта разница — минимально возможное значение неровности этого множества. Достичь такой неровности можно, если расположить все элементы множества по невозрастанию или неубыванию. Выходит, задача сводится к оптимальному выбору этих двух множеств.

Элементами первого множества могут быть либо первые M элементов последовательности, либо последние M, остальные числа — элементы второго множества.

Доказательство

Расположим все числа исходной последовательности на прямой. Заметим, что в описанных способах разделения на множества отрезки, соединяющие минимальные и максимальные элементы множеств, не пересекаются. Теперь поменяем местами два каких-нибудь элемента в множествах. Отрезки на прямой начнут пересекаться. Следовательно, этот способ разделения на множества не может давать меньшее значение неровности, чем исходный.

Выходит, что есть всего два способа выбрать множества. Например, если N = 5, то элементы отсортированной последовательности можно расположить так: 3 1 4 2 5 или 1 4 2 5 3. Следует отметить, что если N — четное, то неровность для этих способов будет совпадать, так как совпадают размеры множеств.

Обобщение подхода

Для произвольного значения K разбивать исходную последовательность требуется уже на K множеств. Причем они будут представлять из себя непересекающиеся отрезки исходной последовательности. Каждый отрезок может иметь длину либо M₁ = N / K округлённое вниз, либо M₂ = M₁ + 1 элементов.

В дальнейшем будем говорить, что разбиваем исходную последовательность не на множества, а на отрезки. За (L − R) обозначим отрезок, начинающийся в L и заканчивающийся в R.

Варианты реализации подсчета ответа

Возможны два варианта реализации: с помощью рекурсии или с помощью метода динамического программирования.

Решение рекурсивным методом рассчитано на 1-7 подзадачи. Метод заключается в следующем. Начнём с первой позиции и попробуем отложить отрезок длины M₁. Если получилось — перейдём в новую позицию и попробуем повторить процесс. Если не получилось, то попробуем отложить отрезок длины M₂. Если вновь не получилось — вернёмся к предыдущей позиции. Такой вариант реализации требует много времени для своего выполнения. Обосновано это тем, что из каждой позиции есть два варианта дальнейшего действия.

Решение методом динамического программирования рассчитано на 1-12 подзадачи. Метод заключается в следующем. Изначально только первая позиция отмечена как посещенная. Будем идти по массиву слева направо. От каждой отмеченной позиции попытаемся отложить отрезки длины M₁ и M₂. Отметим соответствующие позиции и пересчитаем для них ответ. Важной особенность такого решения является то, что нужно четко фиксировать количество отложенных отрезков для каждой отмеченной позиции. Проще всего это сделать с помощью двумерного массива: dp[позиция][количествоотрезков] = ответ. Финальное значение неровности будет хранится в dp[N][K].

Варианты реализации подачи запросов

Первый и самый простой вариант: будем спрашивать обо всех отрезках, которые необходимы, без запоминания ответов. То есть возможен вариант, когда один и тот же запрос будет сделан несколько раз.

Второй вариант: заметим, что отрезков длины M₂ должно быть ровно cnt₂ = N mod K штук. Следовательно, отрезков длины M₁ должно быть cnt₁ = K − cnt₂. Начнём для каждой позиции фиксировать количество отрезков каждого вида, которые еще требуется отложить от данной позиции.

Третий и четвёртый варианты получаются из первого и второго соответственно путём добавления функции запоминания ответов.

Пятый вариант: можно заметить, что делать некоторые запросы необязательно. Ответ на них можно получить путём вычисления. Например, если известны ответы для отрезков (1 − 5) и (1 − 3), то их разница будет ответом для отрезка (3 − 5). Реализовать такой вариант можно следующим образом: начнём приводить все запросы к виду (1 −  * ). Тогда, если известны ответы для двух концов очередного запроса, ответ на него может быть легко вычислен.

Шестой вариант — самый эффективный с точки зрения количества запросов. Предположим, что нам необходимо посчитать неровность при N = 7 и K = 2. Любой другой вариант будет подразумевать подсчет сумм (1 − 3) + (4 − 7) и (1 − 4) + (5 − 7). Количество запросов в таком случае будет равно четырём. Но можно обойтись и тремя. Для этого достаточно посчитать две разности: (1 − 7) − (3 − 4) и (1 − 7) − (4 − 5). То есть, вместо того, чтобы складывать итоговый ответ из суммы ответов на отрезках, следует отнять от общего ответа те единичные отрезки, которые не входят в текущий вариант разделения последовательности.

Частичные решения

Можно заметить связь между 4 и 9, 5 и 10, 6 и 11, 7 и 12 подзадачами. Связь заключается в том, что эти пары подзадач рассчитаны на разный подход к подсчету ответа, но на одинаковую реализацию подачи запросов.

Первую подзадачу можно решить разбором возможных вариантов разделения последовательности на отрезки.

В восьмой подзадаче ограничение на Q позволяет узнать значение всех чисел в коллекции Васи. Но ограничение на K требует реализацию подсчета ответа на основе динамики. Подзадача рассчитана на то, чтобы у участников была возможность проверить правильность реализации подсчета ответа.

Тринадцатая подзадача является частным случаем. Раз N mod K = 0, то все отрезки имеют одинаковую длину. Следовательно, есть только один вариант разбить исходную последовательность.