Задание 26 ЕГЭ по информатике

Группа исследователей отправляется на экспедицию в горы, где им нужно распределить свои припасы по нескольким хранилищам. У них есть $N$ разновесных пакетов с продуктами, которые им нужно разместить в $K$ пещерах, каждая из которых может вместить до $M$ кг продуктов. Исследователи начинают последовательно заполнять пещеры по возрастанию их номеров: они помещают в каждую следующую пещеру сначала самый тяжелый из оставшихся пакетов, затем самый легкий, а потом снова самый тяжелый – и так поочередно до тех пор, пока в пещеру влезает следующий подходящий пакет.

Определите наибольший номер неполной пещеры (в которой еще осталось свободное место) с наименьшим остатком свободного места в ней, а также общий остаток свободного места (в кг) во всех непустых пещерах.

Входные данные

В первой строке входного файла находится число $N$ – количество пакетов с продуктами (натуральное число, не превышающее 10000). Во второй строке находятся два числа: $K$ – количество пещер и $M$ - вместимость (в кг) каждой из пещер ($K < M < 1 000 000$). В третьей же строке находятся $K$ чисел (каждое из них не превышает 10000000), характеризующих номера пещер. В следующих $N$ строках находятся натуральные числа (каждое из них не превышает 100000) – веса пакетов с продуктами (в кг).

Запишите в ответе два числа: сначала наибольший номер неполной пещеры с наименьшим остатком свободного места, а затем количество оставшегося свободного места во всех непустых пещерах (в кг).

Типовой пример организации данных во входном файле

5

3 7

7 9 4

6

4

1

5

2

При таких исходных данных пещеры с номерами 4 и 7 будут заполнены до отвала (6 + 1) и (5 + 2), а в последней пещере с номером 9 останется 3 кг свободного места (в неё погрузят последний пакет с весом 4 кг). Ответ: 9 3.

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

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/14626_26.txt