ধরুন আমাদের পাঁচটি সংখ্যা আছে, N, A, B, C, D। আমরা একটি সংখ্যা 0 দিয়ে শুরু করি এবং N-তে শেষ করি। আমরা নিম্নলিখিত ক্রিয়াকলাপগুলির সাথে নির্দিষ্ট সংখ্যক মুদ্রা দ্বারা একটি সংখ্যা পরিবর্তন করতে পারি -
- A কয়েন পরিশোধ করে সংখ্যাটিকে 2 দ্বারা গুণ করুন
- বি কয়েন পরিশোধ করে সংখ্যাটিকে 3 দিয়ে গুণ করুন
- C কয়েন পরিশোধ করে সংখ্যাটিকে 5 দ্বারা গুণ করুন
- ডি কয়েন পরিশোধ করে, সংখ্যাটি 1 দ্বারা বাড়ান বা হ্রাস করুন।
আমরা যেকোন ক্রমে এই অপারেশনগুলো যেকোন সংখ্যক বার করতে পারি। N
-এ পৌঁছানোর জন্য আমাদের সর্বনিম্ন কয়েনগুলির সংখ্যা খুঁজে বের করতে হবেসুতরাং, যদি ইনপুটটি N =11 এর মত হয়; A =1; B =2; গ =2; D =8, তারপর আউটপুট হবে 19, কারণ শুরুতে x হল 0।
8টি কয়েনের জন্য x কে 1 দ্বারা বাড়ানোর জন্য (x=1)।
1 মুদ্রার জন্য, x কে 2 দিয়ে গুণ করুন (x=2)।
2 কয়েনের জন্য, x কে 5 (x=10) দিয়ে গুণ করুন।
8টি কয়েনের জন্য, এটি 1 (x=11) দ্বারা বাড়ান।
পদক্ষেপ
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
Define one map f for integer type key and value Define one map vis for integer type key and Boolean type value Define a function calc, this will take n if n is zero, then: return 0 if n is in vis, then: return f[n] vis[n] := 1 res := calc(n / 2) + n mod 2 * d + a if n mod 2 is non-zero, then: res := minimum of res and calc((n / 2 + 1) + (2 - n mod 2)) * d + a) res := minimum of res and calc(n / 3) + n mod 3 * d + b if n mod 3 is non-zero, then: res := minimum of res and calc((n / 3 + 1) + (3 - n mod 3)) * d + b) res := minimum of res and calc(n / 5) + n mod 5 * d + c if n mod 5 is non-zero, then: res := minimum of res and calc((n / 5 + 1) + (5 - n mod 5)) if (res - 1) / n + 1 > d, then: res := n * d return f[n] = res From the main method, set a, b, c and d, and call calc(n)
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#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; int A = 1; int B = 2; int C = 2; int D = 8; cout << solve(N, A, B, C, D) << endl; }
ইনপুট
11, 1, 2, 2, 8
আউটপুট
19