CSCB325
Задачи 2021
Задача 1. Coins2021
Дадени са монети със стойности c1, c2,
..., ck и целева сума n. Задачата
е да се направи тази сума с минимален брой монети.
Вход
Всеки тестов пример е зададен на два реда на стандартния вход.
Първият ред съдържа броя и стойностите на монетите (естествени
числа), а втория - броя на сумите, които трябва да се формират от
зададените стойности на монетите и самите суми.
Ограничения
0 < n < 106 + 1
0 < ci < 101, i = 1, 2,
..., k
0 < k < 101
Изход
За всеки пример на отделен ред на стандартния изход се отпечатва
минималния брой за всяка сума. Ако от дадените стойности на монетите
не може да се образува съответната сума, да се отпечатва числото 0.
Примерен вход:
3 1 3 4
2 8 10
2 5 6
2 9 10
Решение:
2 3
0 2
https://www.hackerrank.com/cscb325-2021
Задача 2. Sums2021
Дадени са n типа монети със стойности съответно: c0,
c1, ..., cn-1,
и естествено число s. Да се намери броя на различните
представяния на s с монети измежду наличните типове. Всеки
тип монети може да участва в сумата неограничен брой пъти.
Вход
Всеки тестов пример е зададен на два реда на стандартния вход.
Първият ред съдържа стойностите на типовете монети, а втория -
няколко числа s, за които се търси броя на различните
представяния.
Ограничения
Стойностите c0, c1,
..., cn-1 са цели
положителни числа, по-малки от 1000.
1 < n <= 100
1 < s <= 10000
Изход
За всеки пример на отделен ред на стандартния изход се отпечатва
минималния брой за всяко от дадените числа s.
Примерен вход:
1 3 4
8 10
5 6
9 10
Решение:
6 8
0 1