UVa 10819

From Algorithmist
Jump to navigation Jump to search

এই প্রবলেমটা নরমার ন্যাপসাক প্রবলেম । কিন্তু এইটু প্যাঁচ আছে । সল্ভ করার জন্য কয়েকটা জিনিস খেয়াল রাখতে হবে । বেস কেস গুলা হবে এইরকমঃ যদি আমার সবগুলা জিনিসের টাকা আমার দেওয়া টাকা থেকে বেশি হয় এবং আমার দেওয়া টাকা যদি ১৮০০ এর সমান বা কম হয় তাহলে সেটা নিব না । মানে যদি আমার টাকার পরিমাণ ১৮০০ টাকা থাকে এবং আমার জিনিস গুলার মোট দাম ২০০১ টাকা হয় তাহলে আমি নিব না । কারণ আমাকে এই ১৮০০ টাকা থেকে সরবোচ্চ ২০০ টাকা বেশি দিবে । যা আমার জিনিসের দাম থেকে কম ।

এইবার দেখব যদি আমার জিনিসের দাম দেওয়া টাকা থেকে বেশি হয় এবং দেওয়া টাকা যদি ১৮০০ থেকে বেশি হয় তাহলে সেই টাকার সাথে ২০০ টাকা যোগ করব । যদি দেখি আমার জিনিসের দাম তাও অনেক বেশি তাহলে সেই জিনিসও নিব না ।

যদি দেখি আমার জিনিসের দাম উপরের সব গুলা কেসএর কুনুটাই না । কিন্তু আমার জিনিসের দামের সাথে ২০০০ টাকার সমান বা কম তাহলেও নিব না । এই শর্ত গুলা মানলে বেস কেস হয় এইরকমঃ

if(cost > given_money && given_money <=1800) not take; if(cost > given_money+200)not take; if(index == n) { if(cost > given_money && cost <=2000)not take; else take; }

input 1900 3 2000 5 1950 2 101 1

output : 3 (not 5) কারণ ১৯০০ + ২০০=২১০০ টাকা । কিন্তু যদি আমি ২০০০ টাকার জিনিস কিনি তাহলে কোনো ভাবেই অন্য কিছু কিনতে পারব না । ফলে আমার খরচ হবে ২০০০ টাকা । আর তাহলে বাংক আমাকে কোনো টাকা দিবে না । কারণ ২০০০ এর চেয়ে বেশি টাকা খরচ করলেই কেবল বাংক আমাকে টাকা দিবে । ফলে আমার টাকার পরিমাণ থাকবে ১৯০০ টাকা । ফলে আমি ২০০০ এর জিনিস কিনতে পারব না ।

আমার কোডঃ http://paste.ubuntu.com/10572761/

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