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

7. Банкомат

Один отдаленный от центрального офиса банкомат пользовался большой популярностью у клиентов за возможность получать нужную сумму с точностью до рубля. Со временем некоторые кнопки в этом банкомате перестали нажиматься. Как результат, некоторые граждане вообще не могут использовать на нем свою карту, так как не имеют возможности ввести пин-код. Другим же пользователям для получения денег приходится набирать сумму, нажимая только на работающие кнопки с цифрами. После каждой выдачи денег карточка из банкомата извлекается. Поэтому для снятия желаемой суммы денег нужно запастись терпением и несколько раз вставлять карту в банкомат. Определите, за какое минимальное количество использований карты можно снять всю нужную сумму.

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

В первой строке входного файла через пробел записано K цифр, соответствующих кнопкам, которые не работают (6 <= K <= 10).
Во второй строке записаны два целых числа P и S, P — это пин-код, состоящий из четырех цифр, а S — сумма, которую нужно снять с карточки (1 <= S < 106).

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

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

Примеры

input.txt
1 2 3 4 6 5
9889 78

output.txt
1 78

input.txt
1 2 3 4 5 6
9988 12

output.txt
NO


Соревнование: XI Открытая Всесибирская олимпиада по программированию имени И.В. Поттосина 2010
Источник: http://olimpic.nsu.ru


Оставьте свою оценку: Интересность: Сложность: