मान लीजिए हमारे पास D संख्या के तत्वों वाले दो ऐरे p और c हैं, और एक अन्य संख्या G है। एक कोडिंग प्रतियोगिता पर विचार करें, प्रत्येक समस्या का कठिनाई के आधार पर अपना स्कोर होता है। समस्या p[i] का स्कोर 100i है। ये p[1] + ... + p[D] समस्याएं प्रतियोगिता में मौजूद सभी समस्याएं हैं। कोडिंग साइट पर एक उपयोगकर्ता का एक नंबर total_score है। उपयोगकर्ता का total_score निम्नलिखित दो तत्वों का योग है।
- बेस स्कोर: हल की गई सभी समस्याओं के स्कोर का योग
- बोनस: जब कोई उपयोगकर्ता 100i स्कोर वाली सभी समस्याओं को हल करता है, तो वह बेस स्कोर के अलावा परफेक्ट बोनस c[i] अर्जित करता है।
अमल प्रतियोगिता में नया है और उसने कोई समस्या हल नहीं की है। उसका उद्देश्य G या अधिक अंकों का कुल स्कोर प्राप्त करना है। हमें इस उद्देश्य के लिए उसे कम से कम कितनी समस्याएं हल करने की आवश्यकता है, यह ढूंढना है।
उदाहरण के लिए, यदि इनपुट G = 500; P = [3, 5]; C = [500, 800] है, तो आउटपुट 3 होगा।
चरण
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
D := p का आकार mi := 10000 i := 0 से 1 << D - 1 तक, करें: sum := 0 count := 0 at := 0 i के बिट मान से प्रारंभ 10 बिट्स संग्रहीत करने के लिए एक ऐरे b j := 0 से D-1 तक, करें: यदि b में jवां बिट 1 है, तो: count := p[j] sum := sum + ((j + 1) * 100 * p[j] + c[j] अन्यथा at := j यदि sum < G, तो: d := (G - sum + (at + 1) * 100 - 1) / ((at + 1) * 100) यदि d <= p[at], तो: sum := sum + (at + 1) count := count + d यदि sum >= G, तो: mi := mi और count का न्यूनतम mi वापस करें
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; int solve(int G, vector<int> p, vector<int> c){ int D = p.size(); int mi = 10000; for (int i = 0; i < 1 << D; i++){ int sum = 0; int count = 0; int at = 0; bitset<10> b(i); for (int j = 0; j < D; j++){ if (b.test(j)){ count += p.at(j); sum += (j + 1) * 100 * p.at(j) + c.at(j); } else { at = j; } } if (sum < G){ int d = (G - sum + (at + 1) * 100 - 1) / ((at + 1) * 100); if (d <= p.at(at)){ sum += (at + 1) * 100 * d; count += d; } } if (sum >= G) { mi = min(mi, count); } } return mi; } int main() { int G = 500; vector<int> P = { 3, 5 }; vector<int> C = { 500, 800 }; cout << solve(G, P, C) << endl; } इनपुट
500, { 3, 5 }, { 500, 800 } आउटपुट
3
