🟢 Մանրադրամի վերադարձ
Գրենք ծրագիր, որը կօգնի վաճառողին վերադարձնել մանրադրամը հաճախորդներին։ Մանրադրամը վերադարձնելիս մենք ցանկանում ենք տրամադրել հնարավորինս քիչ քանակի մետաղադրամներ։ Դա մեզ թույլ կտա մի կողմից խնայել վաճառողի մոտ եղած մետաղադրամների քանակը, մյուս կողմից չզայրացնել հաճախորդներին մեծ քանակի մանրադրամներով։ Նույն սկզբունքով են մանր վերադարձնում նաև տարատեսակ վճարային տերմինալներն ու բանկոմատները։
Խնդիրը չծանրաբեռնելու համար ենթադրենք, որ հասանելի են 10, 20, 50 և 100 դրամանոց մետաղադրամներ։ Նաև ենթադրենք, որ 10 դրամից քիչ գումարը անտեսվում է։
Այս խնդիրը հնարավոր է լուծել կիրառելով այսպես կոչված ագահ ալգորիթմ (greedy algorithm), այն է ամեն քայլում մենք կարող ենք <<ագահաբար>> ընտրել ամենամեծ հնարավոր մետաղադրամը։
Օրինակ,
170 դրամ վերդարձնելու համար մենք կընտրենք ամենամեծ հնարավոր մետաղադրամը՝ 100 դրամ։ Այս քայլից հետո մեզ կմնա վերադարձնելու 70 դրամ։ Այսինքն, մեզ հարկավոր է լուծել նույն խնդիրը արդեն ավելի փոքր գումարի` 70 դրամի համար։ Երկրորդ քայլում ամենամեծ հնարավոր մետաղադրամը, որ կարող ենք ընտրել դա 50 դրամն է։ Վերջին քայլում կընտրենք 20 դրամանոց մետաղադրամը։ Արդյունքում մենք կվերադարձնենք հաճախորդին թվով 3 մետաղադրամ։ Ագահ ալգորիթմները խնդրի լուծման ամեն քայլում ընտրում են հնարավոր լավագույն միջանկյալ լուծումը։ Ոչ բոլոր դեպքերում է, որ ագահ ալգորիթմները գտնում են խնդրի գլոբալ օպտիմալ լուծումը։ Սակայն, այս խնդրի համար վերևում նկարագրած ալգորիթմի գտած լուծումը միշտ վերադարձնում է մետաղադրամների հնարավոր մինիմալ քանակը։
🤖
Դե ինչ, ժամանակն է գրել ծրագիր, որը ներմուծված գումարի համար կվերադարձնի այդ գումարը մանրելու համար հնարավոր մինիմալ մետաղադրամների քանակը։
Ծրագիրը նախ էկրանին պետք է տպի
Change: տողը, և սպասի որպեսզի օգտագործողը ներմուծի թիվ։ Ինչպես նախորդ խնդիրներում, եթե օգտագործողը ներմուծել է ոչ վալիդ տվյալ (բացասական թիվ), ապա ծրագիրը պետք է նորից խնդրի օգտագործողին ներմուծել թիվ, այնքան ժամանակ, քանի դեռ օգտագործողը չի ներմուծել վալիդ արժեք։ ./cash
Change: -1
Change: 10
1Constraints
Time limit: 0.2 seconds
Memory limit: 512 MB
Output limit: 1 MB