মান লিজিয়ে, আমরা একটি ভিডিও গেম খেলছি যেখানে নাযক ছুরি দিয়ে শত্রুদের পরাজয় করে। নাযক ছুরি দিয়ে শত্রুকে কাটতে পারে বা ছুরি নিক্ষেপ করতে পারে। যদি নাযক ছুরি নিক্ষেপ করে, তবে সেটি আবার ফেরত পাওয়া যায় না। ছুরি i-র ক্ষতি 'knives' অ্যারেতে দেওয়া আছে যেখানে প্রতিটি উপাদান হলো {slash, throw}। 'Slash' মানে সেটি দিয়ে শত্রু কাটলে ক্ষতি এবং 'throw' মানে সেটি নিক্ষেপ করলে ক্ষতি। কাটা অনবচ্ছিন্ন বার করা যায়, কিন্তু একটি ছুরি একবারের বেশি নিক্ষেপ করা যায় না। এখন একটি শত্রু আসে যার স্বাস্থ্য h। আমাদের লক্ষ্য হলো শত্রুকে পরাজয় করতে ন্যূনতম অপারেশন (কাটা বা নিক্ষেপ) কতটি লাগবে তা বের করা। শত্রু পরাজিত হয় যখন তার স্বাস্থ্য ০ হয়ে যায়।
যেমন, ইনপুট হলে n = 2, h = 11, knives = {{4, 5}, {3, 6}}, তবে আউটপুট হবে 2।
যদি নাযক দুটি ছুরি নিক্ষেপ করে, তবে মোট ক্ষতি = 5 + 6 = 11। শত্রুর স্বাস্থ্য ০ হয়ে যায়, তাই সে পরাজিত হয়।
সমাধানের ধাপসমূহ
এই সমস্যাটি সমাধান করার জন্য নিচের ধাপগুলো অনুসরণ করব:
val := 0 i := 0 থেকে n-1 পর্যন্ত: val := max(val, knives[i]-র ১ম মান) knives অ্যারে সোর্ট করুন res := 0 i := 0 থেকে n-1 পর্যন্ত: if knives[i]-র ২য় মান > val, তবে: h := h - knives[i]-র ২য় মান res ১ বাড়িয়ে if h <= 0, তবে: print(res) exit অন্যথায় লুপ থেকে বের হয়ে যান print(res + ceil(h / (double)val))
উদাহরণ
নিচের ইমপ্লিমেন্টেশনটি দেখুন আরও ভালো বুঝতে:
#include <bits/stdc++.h> using namespace std; void solve(int n, int h, vector<pair<int, int>> knives){ int val = 0; for(int i = 0; i < n; i++){ val = max(val, knives[i].first); } sort(knives.begin(), knives.end()); int res = 0; for(int i = 0; i < n; i++){ if(knives[i].second > val){ h -= knives[i].second; res++; if(h <= 0){ cout << res << endl; return; } } else break; } cout << (res + ceil(h / (double)val)) << endl; } int main() { int n = 2, h = 11; vector<pair<int, int>> knives = {{4, 5}, {3, 6}}; solve(n, h, knives); return 0; } ইনপুট
2, 11, {{4, 5}, {3, 6}} আউটপুট
2
