मान लीजिए हमारे पास K संख्या के तत्वों वाला एक ऐरे A है। मान लें, एक खेल में N खिलाड़ी हैं और एक गेम मास्टर है। इस खेल में K राउंड हैं। iवें राउंड में गेम मास्टर 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 := A का आकार आकार 100010 का एक बड़ा ऐरे a, l, r, a परिभाषित करें। l := 2, r = 2 i := 1 से n तक, करें: a[i] := A[i - 1] i := n से 1 तक, करें: x := a[i], L := (l + x - 1) यदि L > R, तो: -1, 0 वापस करें l := L, r = R + x - 1 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
