UVa 166

From Algorithmist
Jump to navigation Jump to search

এই প্রবলেম হল কয়েনচেঞ্জএর দুইটা ভারিয়েন্টের মিক্সার । জেইখানে একসাথে লিমিটেড কয়েন এবং আনলিমিটেড কয়েনের কাজ একসাথে করা হয়েছে । এইখানে খেয়াল করলে দেখা যাবে যে দোকানদারের কাছে আনলিমিটেড কয়েন আছে । কিন্তু ক্রেতার কাছে লিমিটেড কয়েন আছে । আমাদের কাজ হল মিনিমাম এক্সচেঞ্জ বের করা । মানে হাত বদলের সংখ্যা কমানো । এক্সাম্পলটা থেকেই ব্যাখ্যা করি । যদি আমি ৫৫ পয়সা বানাইতে চাই কিন্তু আমার কাছে যদি ৫০ পয়সার কয়েন না থাকে তাহলে আমাকে ২০+২০+১০+৫ = ৪টা কয়েনের হেল্প নিতে হবে । কিন্তু যদি আমি দোকানদারকে ১.০৫ টাকা দেই । তাহলে সে আমাকে ৫০ পয়সার একটা কয়েন ফেরত দিলেই কেল্লা ফতে । তাহলে ১.০৫ - .৫= .৫৫ টাকা । হয়ে গেল । আর আমারো এক্সচেঞ্জ হল দুই হাত । মানে আমি দুইবার হাত বদল করেই আমার বিল পরিশোধ করে ফেললাম । খেয়াল করে দেখ আমি কিন্তু বেশি টাকা দিতে পারি । আর তখন দোকানদারও আমাকে টাকা ফেরত দিয়ে দিবে । তাহলে আমাদের যা করতে হবে তা হল আনলিমিটেড কয়েনের জন্য দোকানদার ক্যামনে টাকা শোধ করবে তা বের করব । তারপর সেই আনলিমিটেড কয়েন থেকে আমকে লিমিটেড কয়েনের জন্য হিসেব বের করতে হবে ।

লিমিটেড কয়েনের জন্য আল্গো হবেঃ আমি( ইনডেক্স , টাকা) যদি ইনডেক্স == ৬ && টাকা > ০ // টাকা এখনও ০ হয় নাই মানে আমি টাকা ফর্ম করতে পারতেসি না । তাহলে এই টাকা নিব না । যদি ইনডেক্স == ৬ && টাকা <=০ // হয় আমি বেশি টাকা দিয়ে ফেলসি অথবা আমি ০ টাকা বানায় ফেলসি । এখন আমি দেখব দোকানদার আমার বেশি টাকা অথবা //সমান টাকার জন্য কিভাবে আমার টাকা শোধ করে । বের করব এইভাবে দোকানদারের_টাকা[-টাকা] ; -টাকা কিন্তু হল আমার অতিরিক্ত দাওয়া টাকা । একটু হিসেব কর। যদি টাকা < -৫ || টাকা > ৫ হলে আমরা নিব না //কারণ মাক্সিমাম টাকা হল ৫ টাকা ফর্ম করতে হবে ।

// বেস কেস শেষ । যদি আমার কয়েনের সংখ্যা < এখন যত কয়েন লাগবে ,তাহলে আমরা পরের কয়েনে চলে যাব । যদি আমার কয়েনের সংখ্যা > এখন যত কয়েন লাগবে আমার কয়েন সংখ্যা -- কয়েন নিয়ে আমার কাজ আমার কয়েন সংখ্যা ++ কয়েন ছাড়া আমার কাজ


আমার ইমপ্লিমেন্টেশনঃ http://paste.ubuntu.com/10595057/

  1. হতাশ_কোডার