CSCB325
Задачи 2023
Задача 1. Coins23
Дадени са монети със стойности 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. Distance23
Да се напише програма за пресмятане на разстоянието на Левенщайн
между два низа, не съдържащи интервали.
Вход
За всеки тестов пример на стандартния вход на един ред са дадени два
низа.
Ограничения
Дължините на низовете са не по-големи от 1000.
Изход
За всеки тестов пример на стандартния изход да се отпечати едно
число на отделен ред - полученото от програмата разстояние.
Примерен вход:
alabala balaala
abcd xy
Решение:
2
4