Хамгийн Бага Зоос

2s

512MB

1114

0%

Dynamic Programming

$n$ зоосоос бүрдсэн мөнгөний систем өгөгдөнө. Зоос бүр эерэг бүхэл утгатай. Боломжит зоосуудыг ашиглан $x$ дүнг үүсгэхдээ зоосын тоог хамгийн бага болго.

Жишээ нь зоосууд $\{1,5,7\}$ , дүнг $11$ бол $5+5+1$ оновчтой шийд бөгөөд $3$ зоос шаардана.

https://cses.fi/problemset/task/1634

Оролтын формат

Эхний мөрөнд хоёр бүхэл тоо $n$ , $x$ байна: зоосын тоо, хүссэн мөнгөний дүн.

Хоёр дахь мөрөнд зоос бүрийн утгууд $c_1,c_2,\dots,c_n$ хоорондоо ялгаатай $n$ бүхэл тоо байна.

Гаралтын формат

Нэг бүхэл тоо хэвлэ: зоосын хамгийн бага тоо. Хүссэн дүнг үүсгэх боломжгүй бол $-1$ хэвлэ.

Хязгаарлалт

$1 \le n \le 100$
$1 \le x \le 10^6$
$1 \le c_i \le 10^6$

Жишээ

Оролт1

3 11
1 5 7

Гаралт1

0.1 / 64 KiB

Редактор уншиж байна...