ধরুন আমাদের একটি অ্যারে রয়েছে যার সাথে N উপাদান রয়েছে এবং আরেকটি বাইনারি স্ট্রিং S রয়েছে। বিবেচনা করুন দুটি খেলোয়াড় একটি গেম খেলছে। এগুলিকে 0 এবং 1 হিসাবে সংখ্যা করা হয়েছে৷ একটি পরিবর্তনশীল x রয়েছে যার প্রাথমিক মান 0৷ গেমগুলির N রাউন্ড রয়েছে৷ বৃত্তাকার ব্যক্তিতে S[i] নিম্নলিখিতগুলির মধ্যে একটি করে:xকে x XOR A[i] দিয়ে প্রতিস্থাপন করুন, অন্যথায় কিছুই করবেন না। ব্যক্তি 0 এই গেমের শেষে 0 চায় কিন্তু ব্যক্তি 1 নন-জিরো চায়। আমাদের পরীক্ষা করতে হবে x শেষে 0 হয় কি না।
সুতরাং, যদি ইনপুটটি A =[1, 2] এর মত হয়; S ="10", তাহলে আউটপুট হবে 1, কারণ person1 0 XOR 1 =1 দিয়ে x পরিবর্তন করে, তাই ব্যক্তি0 দ্বারা পছন্দ নির্বিশেষে এটি সর্বদা 1 হবে।
পদক্ষেপ
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
N := size of A Define an array judge of size: 60. z := 0 fill judge with 0 for initialize n := N - 1, when 0 <= n, update (decrease n by 1), do: x := A[n] loop through the following unconditionally, do: if x is same as 0, then: Come out from the loop y := x I := -1 for initialize i := 0, when i < 60, update (increase i by 1), do: if y mod 2 is same as 1, then: I := i y := y / 2 if judge[I] is same as 0, then: judge[I] := x Come out from the loop x := x XOR judge[I] if S[n] is not equal to '0', then: if x is not equal to 0, then: z := 1 return z
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#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; 0 <= n; 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
