C++ প্রোগ্রামে G পরিমাণ স্কোর পেতে কমপক্ষে কত স্কোর প্রয়োজন তা খুঁজে বের করতে

ধরুন আমাদের দুটি অ্যারে আছে p এবং c উভয়ই উপাদানের D সংখ্যা সহ, এবং আরেকটি সংখ্যা G। একটি কোডিং প্রতিযোগিতায় বিবেচনা করুন, প্রতিটি সমস্যার অসুবিধার উপর ভিত্তি করে তার স্কোর রয়েছে। সমস্যা p[i] এর স্কোর 100i আছে। এই p[1] + ... + p[D] সমস্যাগুলি প্রতিযোগিতায় উপস্থিত সমস্ত সমস্যা। কোডিং সাইটে একজন ব্যবহারকারীর মোট_স্কোর সংখ্যা রয়েছে। একজন ব্যবহারকারীর মোট_স্কোর হল নিম্নলিখিত দুটি উপাদানের যোগফল।

বেস স্কোর :সমস্ত সমাধান করা সমস্যার স্কোরের সমষ্টি
বোনাস :যখন একজন ব্যবহারকারী 100i স্কোর দিয়ে সমস্ত সমস্যার সমাধান করেন, তখন তিনি বেস স্কোর বাদ দিয়ে নিখুঁত বোনাস c[i] অর্জন করেন।

অমল প্রতিযোগিতায় নতুন এবং কোনো সমস্যার সমাধান করেনি। তার উদ্দেশ্য হল জি বা তার বেশি পয়েন্টের মোট স্কোর। এই উদ্দেশ্যের জন্য তাকে অন্তত কত সমস্যা সমাধান করতে হবে তা আমাদের খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুট G =500 এর মত হয়; P =[3, 5]; C =[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 }