मान लीजिए कि हमारे पास दो एरे हैं ए और बी दोनों एन तत्वों के साथ हैं। मान लीजिए अमल और बिमल एक बोर्ड पर एक खेल खेल रहे हैं जिसके सेल नंबर 1 से N तक और N-1 सड़कों पर अंकित हैं। सड़कें दो सेल को जोड़ रही हैं। तो ith सड़क A[i] को B[i] से जोड़ रही है। हर सेल को हर दूसरे सेल से बार-बार पास की सेल में जाकर पहुंचा जा सकता है। प्रारंभ में सेल 1 को काले रंग के रूप में चिह्नित किया गया है, और सेल एन सफेद है। अन्य कोशिकाएं रंगीन नहीं होती हैं। अमल पहले खेलता है, और वे वैकल्पिक रूप से खेल रहे हैं। अमल एक बिना रंग की कोशिकाओं का चयन करता है जो काली कोशिका से सटे होते हैं और काले रंग से पेंट करते हैं। बिमल एक बिना रंग के सेल का चयन करता है जो एक सफेद सेल से सटा होता है और सफेद रंग से पेंट करता है। जब कोई खिलाड़ी किसी सेल को पेंट नहीं कर पाता है, तो वह हार जाता है। हमें विजेता को ढूंढना है।
इसलिए, यदि इनपुट ए =[3, 1, 3, 7, 5, 1] जैसा है; बी =[6, 2, 1, 4, 7, 4], तो आउटपुट अमल होगा, क्योंकि अगर अमल पहले सेल 2 को काला रंग देता है, तो वह बिमल की चाल की परवाह किए बिना जीत जाएगा।
कदम
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
N := 99999 Define one adjacency list adjList Define three large arrays p, d, and ssz Define a function dfs(), this will take nd, par, dep, p[nd] := par d[nd] := dep ssz[nd] := 1 for each node i in adjList[nd], do if i XOR par is non-zero, then: dfs(i, nd, dep + 1) ssz[nd] := ssz[nd] + ssz[i] From the main method, do the following: n := size of A for initialize i := 1, when i < n, update (increase i by 1), do: u := A[i - 1], v := B[i - 1] insert v at the end of adjList[u] insert u at the end of adjList[v] dfs(1, 1, 0) nd := n for initialize i := 0, when i < (d[n] - 1) / 2, update (increase i by 1), do: nd := p[nd] return if 2 * ssz[nd] >= n, then "Bimal", otherwise "Amal"
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
#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