মান লিখুন: আমাদের কাছে পাঁচটি সংখ্যা রয়েছে N, A, B, C, D। আমরা 0 থেকে শুরু করে N-এ পৌঁছাতে চাই। নিচের অপারেশনগুলো ব্যবহার করে সংখ্যাটি পরিবর্তন করা যায়:
- সংখ্যাটি ২ দিয়ে গুণ করুন, A সিক্কা খরচ করে
- সংখ্যাটি ৩ দিয়ে গুণ করুন, B সিক্কা খরচ করে
- সংখ্যাটি ৫ দিয়ে গুণ করুন, C সিক্কা খরচ করে
- সংখ্যাটি ১ বৃদ্ধি বা হ্রাস করুন, D সিক্কা খরচ করে
এই অপারেশনগুলো যেকোনো ক्रमে যেকোনো বার করা যায়। N-এ পৌঁছাতে ন্যূনতম কতটি সিক্কা দরকার তা বের করতে হবে।
উদাহরণ
যদি ইনপুট হয় N = 11; A = 1; B = 2; C = 2; D = 8, তবে আউটপুট হবে 19।
ব্যাখ্যা: শুরুতে x = 0।
8 সিক্কা দিয়ে x ১ বাড়িয়ে x=1 করুন।
1 সিক্কা দিয়ে x কে ২ দিয়ে গুণ করে x=2 করুন।
2 সিক্কা দিয়ে x কে ৫ দিয়ে গুণ করে x=10 করুন।
8 সিক্কা দিয়ে x ১ বাড়িয়ে x=11 করুন।
সমাধানের ধাপসমূহ
এই সমস্যাটি সমাধান করার জন্য আমরা ডাইনামিক প্রোগ্রামিং এবং মেমোরাইজেশন ব্যবহার করব:
f ম্যাপ (ইন্টিজার কী এবং মান)
vis ম্যাপ (ইন্টিজার কী এবং বুলিয়ান মান)
calc(n) ফাংশন:
যদি n শূন্য হয়: 0 রিটার্ন করুন
যদি n vis-এ থাকে: f[n] রিটার্ন করুন
vis[n] := 1
res := calc(n/2) + n%2*d + a
যদি n%2 শূন্য নহয়:
res := min(res, calc(n/2+1) + (2-n%2)*d + a)
res := min(res, calc(n/3) + n%3*d + b)
যদি n%3 শূন্য নহয়:
res := min(res, calc(n/3+1) + (3-n%3)*d + b)
res := min(res, calc(n/5) + n%5*d + c)
যদি n%5 শূন্য নহয়:
res := min(res, calc(n/5+1) + (5-n%5)*d + c)
যদি (res-1)/n + 1 > d হয়:
res := n*d
f[n] := res রিটার্ন করুন
মূল ফাংশন থেকে a, b, c, d সেট করে calc(n) কল করুন
C++ বাস্তবায়ন
#include <bits/stdc++.h>
using namespace std;
int a, b, c, d;
map<long, long> f;
map<long, bool> vis;
long calc(long n) {
if (!n) return 0;
if (vis.find(n) != vis.end()) return f[n];
vis[n] = 1;
long res = calc(n / 2) + n % 2 * d + a;
if (n % 2) res = min(res, calc(n / 2 + 1) + (2 - n % 2) * d + a);
res = min(res, calc(n / 3) + n % 3 * d + b);
if (n % 3) res = min(res, calc(n / 3 + 1) + (3 - n % 3) * d + b);
res = min(res, calc(n / 5) + n % 5 * d + c);
if (n % 5) res = min(res, calc(n / 5 + 1) + (5 - n % 5) * d + c);
if ((res - 1) / n + 1 > d) res = n * d;
return f[n] = res;
}
int solve(int N, int A, int B, int C, int D) {
a = A; b = B; c = C; d = D;
return calc(N);
}
int main() {
int N = 11, A = 1, B = 2, C = 2, D = 8;
cout << solve(N, A, B, C, D) << endl;
}
ইনপুট
11, 1, 2, 2, 8
আউটপুট
19
