Задача 7. Банкомат ≡

Условие

Ведётся разработка универсального банкомата, который сможет работать с любой денежной системой. Пусть в денежной системе некоторой страны используются n типов купюр, номиналы которых равны a₁, a₂, …, a_n. При этом все номиналы различны и перечислены в порядке возрастания: если i ≥ 2, то a_i − 1 < a_i, а также a₁ = 1.

Банкомат использует следующий жадный алгоритм для выдачи купюр. Пусть клиент запросил у банкомата сумму c. Изначально есть пустой набор выдаваемых купюр. На каждом шаге алгоритм добавляет в набор купюру максимально возможного номинала так, чтобы сумма номиналов купюр в наборе не превышала c. Когда сумма номиналов купюр в наборе стала равна c, алгоритм останавливается. Отметим, что, поскольку существует купюра с номиналом a₁ = 1, алгоритм всегда заканчивает работу за конечное число шагов.

Чтобы оценить эффективность данного алгоритма, требуется выяснить, какое максимальное число купюр может потребоваться выдать за один раз, если максимальная сумма, которую можно запросить, равна b. Поскольку максимальная сумма может зависеть от категории обслуживания клиента, необходимо ответить на q запросов для сумм b₁, b₂, …, b_q.

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

Формат входных данных

Первая строка содержит целое число n — количество номиналов купюр (1 ≤ n ≤ 200 000).

Вторая строка содержит n различных целых чисел a_i (1 = a₁ < a₂ < …  < a_n ≤ 10¹⁸).

Третья строка содержит целое число q — количество запросов (1 ≤ q ≤ 200 000).

Следующие q строк содержат по одному целому числу b_i (1 ≤ b_i ≤ 10¹⁸).

Формат выходных данных

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

Ограничения

1 ≤ n ≤ 200000

1 = a₁ < a₂ < …  < a_n ≤ 10¹⁸

1 ≤ q ≤ 200 000

1 ≤ b_i ≤ 10¹⁸

Система оценивания

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

Замечание

• 2 будет выдано как 1 + 1,
• 8 будет выдано как 5 + 1 + 1 + 1,
• 49 будет выдано как 10 + 10 + 10 + 10 + 5 + 1 + 1 + 1 + 1.

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

4
1 5 10 50
3
2
8
50

2 2
8 4
49 9

Разбор

Рассмотрим сначала решение первых четырех подзадач, в которых q ≤ 5. В этом случае каждый запрос можно обрабатывать независимо от других, поэтому проигнорируем факт, что у нас несколько значений b_i и будем решать задачу для одного значения b.

В первой подзадаче b ≤ 500, n ≤ 500, поэтому можно применить динамическое программирование. Обозначим как dp[i] количество купюр, которое будет выдано, если запросить сумму i. Тогда dp[0] = 0, и если m(i) — максимальный номинал купюры, которая не превосходит i, то dp[i] = dp[i − m(i)] + 1. Ответ — максимальное значение среди dp[1]… dp[b]. Решение работает за за O(nb).

Чтобы распространить описанное решение на третью подзадачу, избавимся от множителя n в времени работы. Для этого заметим, что m(i) только возрастает при возрастании i, поэтому в процессе вычисления dp[i] можно поддерживать текущее значение m(i) = a_j и при переходе к следующему значению i проверять, нельзя ли перейти к следующему номиналу a_j + 1. Время работы будет O(b + n) и третья задача решена.

Во второй подзадаче номиналы купюр являются последовательными степенями двойки. Заметим, чтобы выдать сумму c банкомат выдаст купюры с номиналами, соответствующими позициям единиц в двоичной записи числа c. Значит задача свелась к поиску числа, не превосходящего b, содержащего максимальное число единиц в двоичной записи. Пусть двоичная запись числа b содержит k разрядов. Тогда число единиц в ответе не превышает k, и число 2^k − 1 − 1 заведомо меньше b и содержит ровно k − 1 двоичную единицу. Значит ответ—либо b, либо 2^k − 1 − 1, получившееся решение работает за O(logb).

Решение четвертой подзадачи уже приближает нас к полному решению: ограничения на n, a_i и b_i в ней максимальны и только q ≤ 5. Научимся решать задачу для одного запроса b за O(n). Правильное решение основывается на жадном алгоритме.

Сделаем инверсию задачи. Пускай mn_x —минимальное число c такое, что банкомат выдаст x купюр для суммы c.

Будем по-прежнему обозначать как m(v) максимальный номинал купюры, не превышающий v. Докажем, что mn_x = mn_x − 1 + m(mn_x).

С одной стороны mn_x − 1 ≤ mn_x − m(mn_x), поскольку из набора купюр, дающего сумму mn_x, всегда можно убрать самую большую купюру (равную m(mn_x)), и получим корректный набор из x − 1 купюр, дающих в сумме mn_x − m(mn_x). С другой стороны, предположим, что мы зафиксировали x, и mn_x − 1 < mn_x − m(mn_x). Можно заметить, что в этом случае величина mn_x − 1 + m(mn_x) меньше, чем mn_x, и банкомат вернет при запросе такой величины ровно x купюр — одну купюру m(mn_x) (она максимальная, не превышающая этой суммы), и еще x − 1 купюр, на которые раскладывается сумма mn_x − 1. Противоречие, исходное утверждение доказано.

Используя это наблюдение, можно посчитать все значения mn_x за время O(n). Заметим, что для двух последовательных чисел a_i, a_i + 1 для всех значений x таких, что m(mn_x) = a_i (иными словами, самая большая купюра, если банкомат выдаёт x купюр, равна a_i), значения mn_x образуют арифметическую прогрессию с разностью a_i и значениями в промежутке [a_i;a_i + 1). Посчитав такую арифметическую прогрессию для промежутка [a_i;a_i + 1), можно перейти к промежутку для [a_i + 1;a_i + 2): если последнее значение в прогрессии равно y (y < a_i + 1), то следующая прогрессия начнется с y, и будет состоять из чисел y + k ⋅ a_i + 1, меньших a_i + 2. Чтобы найти все эти числа и их количество можно просто поделить длины соответствующих отрезков нацело на a_i + 1. Таким образом, последнее число mn_x, не превышающее b, и соответствующее значение x являются ответом на задачу.