ধরুন আমাদের দুটি অ্যারে A এবং B উভয়ই N উপাদানের সাথে রয়েছে। বিবেচনা করুন অমল এবং বিমল একটি বোর্ডে একটি গেম খেলছেন যার সেল নম্বরগুলি 1 থেকে এন এবং এন-1 রাস্তাগুলি সংখ্যাযুক্ত। রাস্তা দুটি সেলকে সংযুক্ত করছে। তাই রাস্তা A[i] কে B[i] এর সাথে সংযুক্ত করছে। প্রতি কোষে বারবার সংলগ্ন কোষে ভ্রমণ করে প্রতিটি কোষ থেকে অন্য কোষে পৌঁছানো যায়। প্রাথমিকভাবে ঘর 1 কালো রঙ হিসাবে চিহ্নিত করা হয়, এবং কোষ N সাদা। অন্যান্য কোষ রঙিন হয় না। অমল প্রথমে খেলে, বিকল্পভাবে তারা খেলছে। আমাল কালো কোষের সংলগ্ন একটি বর্ণহীন কোষ নির্বাচন করে এবং কালো রঙ করে। বিমল একটি বর্ণহীন কোষ নির্বাচন করে যা একটি সাদা কোষের সংলগ্ন এবং সাদা রঙ করে। যখন একজন খেলোয়াড় একটি সেল আঁকতে পারে না, তখন সে হারায়। আমাদের বিজয়ী খুঁজে বের করতে হবে।
সুতরাং, যদি ইনপুটটি A =[3, 1, 3, 7, 5, 1] এর মত হয়; B =[6, 2, 1, 4, 7, 4], তাহলে আউটপুট হবে Amal, কারণ Amal যদি প্রথমে সেল 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
