सी++ प्रोग्राम शुरू होने से पहले खेल में बच्चों की सबसे छोटी और सबसे बड़ी संख्या खोजने के लिए

मान लीजिए कि हमारे पास तत्वों की K संख्या के साथ एक सरणी A है। विचार करें, एक खेल में N खिलाड़ी होते हैं और एक गेम मास्टर होता है। इस गेम में K राउंड हैं। नौवें दौर के खेल में मास्टर ए [i] बच्चों की संख्या के साथ समूह बनाने की घोषणा करता है। फिर शेष बच्चे A[i] बच्चों के जितने संभव हो उतने समूह बनाते हैं। एक बच्चा कई समूहों में भाग नहीं ले सकता। जो बिना समूह के रह जाते हैं वे खेल छोड़ देते हैं। अन्य अगले दौर के लिए आगे बढ़ते हैं। एक दौर में कोई खिलाड़ी नुकसान नहीं हो सकता है। अंत में, के-वें दौर के बाद, ठीक दो बच्चे बचे हैं, और उन्हें विजेता घोषित किया जाता है। हमें खेल शुरू होने से पहले सबसे छोटी और सबसे बड़ी संभव संख्या में बच्चों का पता लगाना होगा, या यह निर्धारित करना होगा कि N का कोई मान्य मान मौजूद नहीं है।

इसलिए, यदि इनपुट ए =[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