मान लीजिए हमारे पास पांच संख्याएं N, A, B, C, D हैं। हम संख्या 0 से शुरू करते हैं और N पर समाप्त करते हैं। हम निम्नलिखित ऑपरेशनों द्वारा एक संख्या को कुछ सिक्कों का भुगतान करके बदल सकते हैं:
- संख्या को 2 से गुणा करें, A सिक्कों का भुगतान करके
- संख्या को 3 से गुणा करें, B सिक्कों का भुगतान करके
- संख्या को 5 से गुणा करें, C सिक्कों का भुगतान करके
- संख्या को 1 से बढ़ाएं या घटाएं, D सिक्कों का भुगतान करके।
हम इन ऑपरेशनों को किसी भी क्रम में कितनी भी बार कर सकते हैं। हमें N तक पहुंचने के लिए आवश्यक न्यूनतम सिक्कों की संख्या ढूंढनी है।
उदाहरण के लिए, यदि इनपुट N = 11; A = 1; B = 2; C = 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)।
चरण
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
पूर्णांक कुंजी और मान के लिए एक मैप f परिभाषित करें पूर्णांक कुंजी और बूलियन मान के लिए एक मैप vis परिभाषित करें एक फ़ंक्शन calc परिभाषित करें, जो n लेता है यदि n शून्य है, तो: 0 वापस करें यदि n vis में है, तो: f[n] वापस करें vis[n] := 1 res := calc(n / 2) + n mod 2 * d + a यदि n mod 2 शून्येतर है, तो: res := res और calc((n / 2 + 1) + (2 - n mod 2)) * d + a का न्यूनतम res := res और calc(n / 3) + n mod 3 * d + b का न्यूनतम यदि n mod 3 शून्येतर है, तो: res := res और calc((n / 3 + 1) + (3 - n mod 3)) * d + b का न्यूनतम res := res और calc(n / 5) + n mod 5 * d + c का न्यूनतम यदि n mod 5 शून्येतर है, तो: res := res और calc((n / 5 + 1) + (5 - n mod 5)) का न्यूनतम यदि (res - 1) / n + 1 > d, तो: res := n * d f[n] = res वापस करें मुख्य विधि से, a, b, c और d सेट करें, और 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