ভূমিকা
রহস্যময় Coinholt গ্রামে আপনি আপনার বেকারির কাউন্টারের পিছনে দাঁড়িয়ে আছেন, সদ্য তৈরি এক ব্যাচ পেস্ট্রি সাজাচ্ছেন।
দরজা ক্যাঁচ করে খুলে যায়, আর ভিতরে ঢোকেন Denara, মানসম্পন্ন পণ্য চেনার তীক্ষ্ণ দৃষ্টিসম্পন্ন এক দক্ষ ব্যবসায়ী।
দ্রুত একবেলা খাওয়ার পর সে কাউন্টারের ওপর দিয়ে আপনার দিকে একটি ঝিকমিকে মুদ্রা এগিয়ে দেয়, যার মান ১০০ ইউনিট।
আপনি হাসিমুখে মুদ্রাটি নিয়ে খাবারের মোট খরচের দিকে তাকান: ৮৮ ইউনিট।
তার মানে আপনাকে খুচরা হিসেবে ১২ ইউনিট ফেরত দিতে হবে।
Denara প্রত্যাশাভরে হাত বাড়িয়ে দেয়।
হাসিমুখে সে বলে, "আমাকে শুধু সবচেয়ে কম সংখ্যক মুদ্রা দিন।
আমার থলি তো আগেই ভরা, আর পথে সেগুলো হারানোর ঝুঁকি নিতে চাই না।"
আপনি জানেন, আপনার হাতে কয়েকটি বিকল্প আছে।
"খুচরার জন্য আমাদের কাছে Lumis (১০ ইউনিট মূল্যের), Viras (৫ ইউনিট মূল্যের) আর Zenth (২ ইউনিট মূল্যের) আছে।"
আপনি মনের মধ্যে দ্রুত সম্ভাবনাগুলো হিসাব করে ফেলেন:
- একটি Lumis (১ × ১০ ইউনিট) + একটি Zenth (১ × ২ ইউনিট) = মোট ২টি মুদ্রা
- দুটি Viras (২ × ৫ ইউনিট) + একটি Zenth (১ × ২ ইউনিট) = মোট ৩টি মুদ্রা
- ছয়টি Zenth (৬ × ২ ইউনিট) = মোট ৬টি মুদ্রা
"সবচেয়ে ভালো পছন্দ দুটি মুদ্রা: একটি Lumis আর একটি Zenth," বলে আপনি তাকে খুচরা দিয়ে দেন।
Denara হাসে, স্পষ্টই মুগ্ধ।
"সবসময়ের মতোই আপনি ঠিক ধরেছেন।"
নির্দেশনা
গ্রাহককে সবচেয়ে কম কয়টি মুদ্রা দিলে সেগুলোর মানের যোগফল সঠিক খুচরার পরিমাণের সমান হবে, তা নির্ধারণ করুন।
উদাহরণ
- 15 পরিমাণের জন্য উপলব্ধ মুদ্রার মান [1, 5, 10, 25, 100] হলে, ফলাফলে 5 মানের একটি মুদ্রা ও 10 মানের একটি মুদ্রা, অর্থাৎ [5, 10] আসা উচিত।
- 40 পরিমাণের জন্য উপলব্ধ মুদ্রার মান [1, 5, 10, 25, 100] হলে, ফলাফলে 5 মানের একটি মুদ্রা, 10 মানের একটি মুদ্রা এবং 25 মানের একটি মুদ্রা, অর্থাৎ [5, 10, 25] আসা উচিত।
ওয়ার্ড
find-fewest-coins ( coins target -- result ) কয়েন ডিনোমিনেশনের একটি অ্যারে রিটার্ন করে, যেগুলোর যোগফল target। coins হলো একটি হ্যাশ সেট (যেমন HS{ 1 5 10 25 }); এটি নিয়ে কাজ করতে sets ভোকাবুলারির ওয়ার্ডগুলো (members, in?, …) ব্যবহার করুন।
যখন coins-এর কোনও কম্বিনেশন দিয়ে target তৈরি করা যায় না, তখন একটি cannot-make-change এরর থ্রো করুন।
