C++ প্রোগ্রাম খেলা শুরুর আগে সবচেয়ে ছোট এবং সবচেয়ে বেশি সংখ্যক বাচ্চাদের খুঁজে বের করতে

ধরুন আমাদের কাছে K সংখ্যার উপাদান সহ একটি অ্যারে রয়েছে। বিবেচনা করুন, একটি খেলায় এন খেলোয়াড় থাকে এবং একটি গেম মাস্টার থাকে। এই গেমের কে রাউন্ড আছে। ইথ রাউন্ডে গেম মাস্টার A[i] সংখ্যক শিশুদের নিয়ে দল গঠন করার ঘোষণা দেয়। তারপর অবশিষ্ট শিশুরা যতটা সম্ভব A[i] শিশুদের দল গঠন করে। একটি শিশু একাধিক দলে অংশ নিতে পারে না। যারা দল ছাড়া বাকি থাকে তারা খেলা ছেড়ে দেয়। বাকিরা পরের রাউন্ডে যায়। একটি রাউন্ড কোন প্লেয়ার হার না হতে পারে. শেষ পর্যন্ত, K-তম রাউন্ডের পরে, ঠিক দুটি শিশু বাকি আছে, এবং তাদের বিজয়ী ঘোষণা করা হয়। খেলা শুরুর আগে আমাদের সবচেয়ে ছোট এবং সবচেয়ে বড় সম্ভাব্য সংখ্যক শিশু খুঁজে বের করতে হবে, অথবা N-এর কোনো বৈধ মান নেই তা নির্ধারণ করতে হবে।

সুতরাং, যদি ইনপুটটি A =[3, 4, 3, 2] এর মত হয়, তাহলে আউটপুট হবে [6, 8], কারণ গেমটি যদি 6টি বাচ্চা দিয়ে শুরু হয়, তাহলে এটি এগিয়ে যায়

• রাউন্ড 1 এ, তাদের মধ্যে 6 জন 3 জনের দুটি গ্রুপ গঠন করে

• তারা 4 এবং 2 সন্তান নিয়ে দুটি দল গঠন করছে

• তারপর একটি দল 1 সন্তানের সাথে এবং অন্যটি 3 জনের সাথে, এবং সেই 1টি খেলা ছেড়ে যাবে

• তাদের মধ্যে তিনটি 1 এবং 2 এর একটি দল গঠন করে। এবং 1 চলে যাবে।

শেষ 2 শিশুকে বিজয়ী ঘোষণা করা হয়।

পদক্ষেপ

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

n := size of A
Define a large array a, l, r, a of size: 100010.
l := 2, r = 2
for initialize i := 1, when i <= n, update (increase i by 1), do:
   a[i] := A[i - 1]
for initialize i := n, when i >= 1, update (decrease i by 1), do:
   x := a[i], L := (l + x - 1)
   if L > R, then:
      return -1, 0
   l := L, r = R + x - 1
return l, r

উদাহরণ

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

#include <bits/stdc++.h>
using namespace std;

void solve(vector<int> A){
   int n = A.size();
   int l, r, a[100010];
   l = 2, r = 2;
   for (int i = 1; i <= n; i++)
      a[i] = A[i - 1];
   for (int i = n; i >= 1; i--){
      int x = a[i], L = (l + x - 1) / x * x, R = r / x * x;
      if (L > R){
         cout << "-1, 0";
      }
      l = L, r = R + x - 1;
   }
   cout << l << ", " << r << endl;
   return;
}
int main(){
   vector<int> A = { 3, 4, 3, 2 };
   solve(A);
}

ইনপুট

{ 3, 4, 3, 2 }

আউটপুট

6, 8