मान लीजिए कि हमारे पास दो सरणियाँ हैं p और c दोनों में D तत्वों की संख्या है, और दूसरी संख्या G है। एक कोडिंग प्रतियोगिता में विचार करें, प्रत्येक समस्या का कठिनाई के आधार पर अपना स्कोर होता है। समस्या p[i] का स्कोर 100i है। ये p[1] + ... + p[D] समस्याएं प्रतियोगिता में मौजूद सभी समस्याएं हैं। कोडिंग साइट में एक उपयोगकर्ता के पास एक नंबर Total_score है। किसी उपयोगकर्ता का Total_score निम्नलिखित दो तत्वों का योग होता है।
-
आधार स्कोर :सभी हल की गई समस्याओं के स्कोर का योग
-
बोनस :जब कोई उपयोगकर्ता 100i के स्कोर के साथ सभी समस्याओं को हल करता है, तो वह आधार स्कोर के अलावा सही बोनस c[i] अर्जित करता है।
अमल प्रतियोगिता में नया है और उसने कोई समस्या हल नहीं की है। उसका उद्देश्य G या अधिक अंक का कुल अंक प्राप्त करना है। हमें कम से कम यह पता लगाना होगा कि इस उद्देश्य के लिए उसे कितनी समस्याओं को हल करने की आवश्यकता है।
इसलिए, यदि इनपुट G =500 जैसा है; पी =[3, 5]; सी =[500, 800], तो आउटपुट 3 होगा
कदम
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
D := size of p
mi := 10000
for initialize i := 0, when i < 1 << D, update (increase i by 1), do:
sum := 0
count := 0
at := 0
an array to store 10 bits b, initialize from bit value of i
for initialize j := 0, when j < D, update (increase j by 1), do:
if jth bit in b is 1, then:
count := p[j]
sum := sum + ((j + 1) * 100 * p[j] + c[j]
Otherwise
at := j
if sum < G, then:
d := (G - sum + (at + 1) * 100 - 1) / ((at + 1) * 100)
if d <= p[at], then:
sum := sum + (at + 1)
count := count + d
if sum >= G, then:
mi := minimum of mi and count
return 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