মান লিন একটি অ্যারে A N এলিমেন্টসহ এবং একটি বাইনারি স্ট্রিং S। দুজন খেলোয়ার একটা গেম খেলছে। তাদের নম্বর ০ এবং ১। একটি ভেরিয়েবল x আছে যার প্রাথমিক মান ০। গেমে N রাউন্ড আছে। i-তম রাউন্ডে S[i] ব্যক্তি নিচের কাজগুলোর একটা করবে: x কে x XOR A[i] দিয়ে রিপ্লেস করবে, অন্যথায় কিছুই করবে না। পার্সন ০ চায় গেমের শেষে x ০ হোক, পার্সন ১ চায় নন-জিরো। আমরা চেক করব শেষে x ০ হয় কিনা।
ইনপুট A = [1, 2], S = "10" হলে আউটপুট ১, কারণ পার্সন ১ x কে 0 XOR 1 = 1 করে দেয়, তাই পার্সন ০ যেটা করুক কেনো x ১ ही থাকবে।
পদ্ধতি (Steps)
N := A-এর সাইজ
judge নামক অ্যারে সাইজ ৬০ দিয়ে ডিক্লেয়ার
z := 0
judge ০ দিয়ে ফিল করুন
n := N-1 থেকে ০ পর্যন্ত লুপ (নাম কমাতে), প্রতিটি n এর জন্য:
x := A[n]
무기한 লুপ (while 1):
যদি x == 0 হয়, তবে ব্রেক
y := x
I := -1
i = 0 থেকে ৫৯ পর্যন্ত লুপ:
যদি y % 2 == 1 হয়, তবে I := i
y := y / 2
যদি judge[I] == 0 হয়, তবে
judge[I] := x
ব্রেক
x := x XOR judge[I]
যদি S[n] != '0' হয়, তবে
যদি x != 0 হয়, তবে z := 1
রিটার্ন z
উদাহরণ কোড (C++)
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A, string S) {
int N = A.size();
int judge[60];
int z = 0;
fill(judge, judge + 60, 0);
for (int n = N - 1; n >= 0; n--) {
int x = A[n];
while (1) {
if (x == 0) break;
int y = x;
int I = -1;
for (int i = 0; i < 60; i++) {
if (y % 2 == 1) I = i;
y /= 2;
}
if (judge[I] == 0) {
judge[I] = x;
break;
}
x ^= judge[I];
}
if (S[n] != '0') {
if (x != 0) z = 1;
}
}
return z;
}
int main() {
vector<int> A = {1, 2};
string S = "10";
cout << solve(A, S) << endl;
}
ইনপুট
{1, 2}, "10"
আউটপুট
1
