Автор: | Центральная предметно-методическая комиссия | Ограничение времени: | 1 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 512 Мб | |
Выходной файл: | Стандартный выход | |||
Максимальный балл: | 100 |
Ведётся разработка универсального банкомата, который сможет работать с любой денежной системой. Пусть в денежной системе некоторой страны используются n типов купюр, номиналы которых равны a1,a2,…,an. При этом все номиналы различны и перечислены в порядке возрастания: если i≥2, то ai−1<ai, а также a1=1.
Банкомат использует следующий жадный алгоритм для выдачи купюр. Пусть клиент запросил у банкомата сумму c. Изначально есть пустой набор выдаваемых купюр. На каждом шаге алгоритм добавляет в набор купюру максимально возможного номинала так, чтобы сумма номиналов купюр в наборе не превышала c. Когда сумма номиналов купюр в наборе стала равна c, алгоритм останавливается. Отметим, что, поскольку существует купюра с номиналом a1=1, алгоритм всегда заканчивает работу за конечное число шагов.
Чтобы оценить эффективность данного алгоритма, требуется выяснить, какое максимальное число купюр может потребоваться выдать за один раз, если максимальная сумма, которую можно запросить, равна b. Поскольку максимальная сумма может зависеть от категории обслуживания клиента, необходимо ответить на q запросов для сумм b1,b2,…,bq.
Требуется написать программу, которая по списку номиналов купюр денежной системы и максимальной сумме, которую можно запросить, определяет сумму, которую необходимо запросить в банкомате, чтобы получить максимальное число купюр, и искомое число купюр.
Первая строка содержит целое число n — количество номиналов купюр (1≤n≤200000).
Вторая строка содержит n различных целых чисел ai (1=a1<a2<…<an≤1018).
Третья строка содержит целое число q — количество запросов (1≤q≤200000).
Следующие q строк содержат по одному целому числу bi (1≤bi≤1018).
Для каждого запроса выведите два числа — сумму, которую необходимо запросить в банкомате, чтобы получить максимальное число купюр, и искомое число купюр. Если существует несколько сумм, не превышающих максимального значения, для которых будет выдано максимальное число купюр, требуется вывести любую из них.
1≤n≤200000
1=a1<a2<…<an≤1018
1≤q≤200000
1≤bi≤1018
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
---|---|---|---|---|
1 | 13 | n≤500, q≤5, ai≤500, bi≤500 | первая ошибка | |
2 | 18 | n=60, q≤5, ai=2i−1 | первая ошибка | |
3 | 20 | q≤5, bi≤2⋅105 | 1 | первая ошибка |
4 | 21 | q≤5 | 1,2,3 | первая ошибка |
5 | 28 | 1,2,3,4 | первая ошибка |
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|