প্রথম স্তূপে সর্বাধিক খড়-বেল গণনা করতে C++ কোড

ধরুন আমাদের একটি অ্যারে আছে n উপাদান সহ এবং আরেকটি মান d। একজন কৃষক ফার্মে এন হেবলপিলসের ব্যবস্থা করেছেন। ith পাইলে A[i] খড়-বেল থাকে। প্রতিদিন একটি গাভী পাশের স্তূপে যেকোন স্তূপে খড়-বেল সরানো বেছে নিতে পারে। গরু একদিনে এটি করতে পারে অন্যথায় কিছুই করবেন না। গরুটি d দিনের মধ্যে প্রথম স্তূপে খড়-বেলগুলি সর্বাধিক করতে চায়। আমাদের প্রথম স্তূপে সর্বোচ্চ সংখ্যক খড়-বেল গণনা করতে হবে।

সুতরাং, যদি ইনপুটটি d =5 এর মত হয়; A =[1, 0, 3, 2], তাহলে আউটপুট 3 হবে, কারণ প্রথম দিনে 3য় থেকে 2য় সরে যান, দ্বিতীয় দিনে আবার 3য় থেকে দ্বিতীয়ে যান, তারপরের দুই দিনে, 2য় থেকে প্রথম যান।

পদক্ষেপ

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

a0 := A[0]
n := size of A
for initialize i := 1, when i < n, update (increase i by 1), do:
   ai := A[i]
   w := minimum of ai and d / i
   a0 := a0 + w
   d := d - w * i
return a0

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

#include <bits/stdc++.h>
using namespace std;
int solve(int d, vector<int> A){
   int a0 = A[0];
   int n = A.size();
   for (int i = 1; i < n; i++){
      int ai = A[i];
      int w = min(ai, d / i);
      a0 += w;
      d -= w * i;
   }
   return a0;
}
int main(){
   int d = 5;
   vector<int> A = { 1, 0, 3, 2 };
   cout << solve(d, A) << endl;
}

ইনপুট

5, { 1, 0, 3, 2 }