Условие

В аукционном доме прошли торги в формате закрытого аукциона первой цены. Но он оказался настолько закрытым, что не разглашались даже победители, лишь победившая ставка за каждый лот (в у.е.). Но путём социальной инженерии (в виде непринуждённого разговора) журналист-обозреватель Кеша Митин смог разузнать, сколько у.е. у каждого из участников осталось на счёте. Предполагая, что торги все участники начинали с одной и той же суммы (60 000 у.е.), предположите, какие лоты выкупил каждый участник.

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

Первая строка – два целых числа через пробел, количество участников N и количество лотов M. Вторая строка – M целых чисел через пробел, выигрышные ставки на лоты (в у.е.). Третья строка – N целых чисел через пробел, итоговые остатки на счетах участников (в у.е.).

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

N строк, в каждой произвольное количество целых чисел через пробел – номера выкупленных лотов. Если участник ничего не купил, в строке должно быть единственное слово `pass`.

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

Видео-разбор

 

Разбор

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

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

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

Последнее изменение: пятница, 15 мая 2026, 04:09