C++ প্রোগ্রাম: G স্কোর পেতে ন্যূনতম সমস্যা সমাধান করা

মান লিখুন: আমাদের কাছে D উপাদান বিশিষ্ট দুটি অ্যারে p এবং c, এবং আরেকটি সংখ্যা G রয়েছে। একটি কোডিং কনটেস্টে প্রতিটি সমস্যার স্কোর তার دشوয়ারির উপর ভিত্তি করে। p[i] সংখ্যক সমস্যা আছে যাদের স্কোর 100*i। এই সব সমস্যাই কনটেস্টে আছে। একজন ইউজারের total_score হল নিচের দুটির যোগফল:

• বেস স্কোর: সমাধান করা সব সমস্যার স্কোরের যোগফল
• বোনাস: যখন একজন ইউজার ১০০*i স্কোর वाले সব সমস্যা সমাধান করে, তবে বেস স্কোরের পাশাপাশি পারফেক্ট বোনাস c[i] পায়

আমল নতুন, সে কোনো সমস্যা সমাধান করেনি। তার লক্ষ্য G বা তার চেয়ে বেশি পয়েন্ট পাওয়া। সেটি পেতে সে ন্যূনতম কতটি সমস্যা সমাধান করতে হবে তা বের করতে হবে।

উদাহরণ

যদি ইনপুট হয় G = 500; P = [3, 5]; C = [500, 800], তবে আউটপুট হবে 3।

সমাধানের ধাপসমূহ

D := p এর আকার
mi := 10000
for i := 0 থেকে (1<= G: mi := min(mi, count)
mi রিটার্ন করুন

C++ বাস্তবায়ন

#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, count = 0, 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