मान लीजिए हमारे पास N-तत्वों वाले दो ऐरे A और B हैं। अमल और बिमल 1 से N तक गिने गए सेल नंबर वाले बोर्ड पर एक खेल खेल रहे हैं। और N-1 सड़कें हैं। सड़कें दो सेल को जोड़ती हैं। इसलिए iवीं सड़क A[i] को B[i] से जोड़ती है। प्रत्येक सेल को बार-बार आसन्न सेल की यात्रा करके हर दूसरे सेल से पहुंचा जा सकता है। प्रारंभ में सेल 1 को काले रंग से चिह्नित किया गया है, और सेल N सफेद। अन्य सेल रंगीन नहीं हैं। अमल पहले खेलता है, और वे बारी-बारी से खेलते हैं। अमल एक अकलर्ड सेल चुनता है जो काले सेल से आसन्न है और उसे काला रंगता है। बिमल एक अकलर्ड सेल चुनता है जो सफेद सेल से आसन्न है और उसे सफेद रंगता है। जब कोई खिलाड़ी सेल को रंग नहीं सकता, तो वह हार जाता है। हमें विजेता ढूंढना है।
उदाहरण के लिए, यदि इनपुट A = [3, 1, 3, 7, 5, 1]; B = [6, 2, 1, 4, 7, 4] है, तो आउटपुट अमल होगा, क्योंकि यदि अमल पहले सेल 2 को काला रंगता है, तो वह बिमल की चालों की परवाह किए बिना जीत जाएगा।
चरण
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
N := 99999 एक आसन्नता सूची adjList परिभाषित करें तीन बड़े ऐरे p, d, और ssz परिभाषित करें एक फ़ंक्शन dfs() परिभाषित करें, जो nd, par, dep लेता है, p[nd] := par d[nd] := dep ssz[nd] := 1 adjList[nd] में प्रत्येक नोड i के लिए, करें यदि i XOR par शून्येतर है, तो: dfs(i, nd, dep + 1) ssz[nd] := ssz[nd] + ssz[i] मुख्य विधि से, निम्नलिखित करें: n := A का आकार i := 1 से n-1 तक, करें: u := A[i - 1], v := B[i - 1] v को adjList[u] के अंत में डालें u को adjList[v] के अंत में डालें dfs(1, 1, 0) nd := n i := 0 से (d[n] - 1) / 2 - 1 तक, करें: nd := p[nd] यदि 2 * ssz[nd] >= n, तो "बिमल" वापस करें, अन्यथा "अमल" वापस करें
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; int N = 99999; vector<vector<int>> adjList(N); vector<int> p(N), d(N), ssz(N); void dfs(int nd, int par, int dep){ p[nd] = par; d[nd] = dep; ssz[nd] = 1; for (int i : adjList[nd]){ if (i ^ par){ dfs(i, nd, dep + 1); ssz[nd] += ssz[i]; } } } string solve(vector<int> A, vector<int> B){ int n = A.size(); for (int i = 1; i < n; i++){ int u = A[i - 1], v = B[i - 1]; adjList[u].push_back(v); adjList[v].push_back(u); } dfs(1, 1, 0); int nd = n; for (int i = 0; i < (d[n] - 1) / 2; i++) nd = p[nd]; return (2 * ssz[nd] >= n ? "Bimal" : "Amal"); } int main(){ vector<int> A = { 3, 1, 3, 7, 5, 1 }; vector<int> B = { 6, 2, 1, 4, 7, 4 }; cout << solve(A, B) << endl; } इनपुट
{ 3, 1, 3, 7, 5, 1 }, { 6, 2, 1, 4, 7, 4 } आउटपुट
Amal
