Дадено е множество от M цели положителни стойности и неограничен брой монети за всяка от зададените стойности. Една от стойностите е 1. Да разгледаме следната задача: Зададена сума S да бъде платена с минимален брой от зададените монети.
Известно е, че в някои случаи задачата се решава от следният “лаком” алгоритъм: да намерим най-голямата стойност на монета, която е по-малка или равна на S и да я извадим S. Продължаваме така, докато S стане нула. Броят на монетите, използвани за нулирането на S по описания алгоритъм, изглежда минимален.
В много случаи горното твърдение е в сила, но за някои множества от стойности на монетите и за някои S лакомият алгоритъм не намира оптималния брой. Например, за множеството от стойности {1, 2, 5, 7, 10} и S = 14, лакомият алгоритъм намира решение с 3 монети (14=10+2+2), докато очевидното минимално решение е с 2 монети (14 = 7 + 7).
Възниква въпросът – за какви множества от стойности на монетите лакомият алгоритъм не намира оптимално решение. Напишете програма COINS, която по зададено множество от стойности на монетите проверява дали има стойност S, която може да бъде платена с по-малък брой монети, отколкото показва лакомият алгоритъм.
Програмата трябва да чете данните от стандартния вход. На първия ред ще е зададен броят M на различните стойности на монетите (1 < M < 100). На втория ред, разделени с по един интервал, ще бъдат зададени M-те стойности a1, a2, … , aM (1=a1 < a2 < … < aM £7000000). На третия ред ще бъдат зададени две цели числа x и y (0 < x < y £ 7000000), разделени с един интервал.
Програмата трябва да изведе на първия ред на стандартния изход стойност S, x £ S £ y, за която лакомият алгоритъм не успява да намери оптималното решение. На втория ред програмата трябва да изведе числата b1, b2, … , bM, разделени с интервали. Числата показват по колко броя монети от съответната стойност са използвани за представянето на S. Подреждането е според реда, по които са зададени стойностите на входа, т.е. S = a1b1 + a2b2 + … + aM bM. Общият брой използвани монети b1+b2+…+bM трябва да бъде по-малък от броя на монетите, намерен от лакомия алгоритъм.
Входните данни гарантират съществуването на поне едно S, за което лакомия алгоритъм не дава най-доброто решение.
Вход5 1 2 5 7 10 1 100 |
Изход14 0 0 0 2 0 |