eolymp
bolt
Try our new interface for solving problems
Məsələlər

Сдачи нет! 1

Сдачи нет! 1

Ваня опаздывает на автобусы, едущие в ЛКШ. К сожалению, ему недостаточно просто успеть на автобус - по дороге ему ещё нужно купить подарок девушке Кате, у которой скоро день рождения. По дороге ему встретился магазин, где он может купить подарок. Подарок стоит \textbf{c} рублей. У Вани в кошельке есть \textbf{n} купюр, но у продавца нет сдачи, и поэтому Ваня должен набрать нужную сумму без сдачи. Более того, у Вани очень мало времени, деньги нужно достать как можно быстрее, и поэтому Ваня хочет дать продавцу нужную сумму минимальным количеством купюр. Помогите ему сделать это. \InputFile Первая строка входного файла содержит три целых неотрицательных числа: \textbf{n}, \textbf{c} и \textbf{k} (\textbf{0} ≤ \textbf{n} ≤ \textbf{1000}, \textbf{0} ≤ \textbf{c} ≤ \textbf{1000}, \textbf{1} ≤ \textbf{k} ≤ \textbf{1000000000}). Далее следуют \textbf{n} чисел \textbf{a_1}, \textbf{a_2}, ..., \textbf{a_n} (\textbf{1} ≤ \textbf{a_i} ≤ \textbf{1000}) - номиналы купюр в том порядке, как они лежат у Вани в кошельке. \OutputFile В первую строку выходного файла выведите одно число \textbf{m} - минимальное количество купюр, которыми Ваня может набрать требуемую сумму. Во вторую строку выведите \textbf{m} чисел - номера купюр, которые должен дать продавцу Ваня. Ване надо будет доставать купюры последовательно из кошелька, поэтому номера должны быть выведены в возрастающем порядке. Если набрать необходимую сумму без сдачи невозможно, то выведите в выходной файл одно число \textbf{-1}. Ване безразлично, как набирать требуемую сумму. Поэтому если есть несколько решений, то можете вывести любое. Ваша программа может не обращать внимания на число \textbf{k}. \Note В первом примере все возможные варианты решения, отсортированные в лексикографическом порядке следующие: \begin{itemize} \item \textbf{1 2} (первая и вторая купюры, т.е. купюры номиналом \textbf{1} и \textbf{4}) \item \textbf{2 5} (вторая и пятая купюры, т.е. купюры номиналом \textbf{4} и \textbf{1}) \item \textbf{3 4} (третья и четвёртая купюры, т.е. купюры номиналом \textbf{2} и \textbf{3}) \end{itemize} Вы можете вывести любой из этих вариантов.
Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
5 5 2
1 4 2 3 1
Çıxış verilənləri #1
2
2 5
Giriş verilənləri #3
2 1 1
2 3
Çıxış verilənləri #3
-1