CSCB325

Задачи 2022

Задача 1. Coins2022
 Дадени са монети със стойности 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

Задача 2. Distance2022
Да се напише програма за пресмятане на разстоянието на Левенщайн между два низа, не съдържащи интервали.

Вход
За всеки тестов пример на стандартния вход на един ред са дадени два низа.
 
Ограничения
Дължините на низовете са не по-големи от 1000.

Изход

За всеки тестов пример на стандартния изход да се отпечати едно число на отделен ред - полученото от програмата разстояние.

Примерен вход:
alabala balaala
abcd xy

Решение:
2
4