मान लीजिए हमारे पास N तत्वों वाला एक सरणी A और एक अन्य बाइनरी स्ट्रिंग S है। मान लें कि दो खिलाड़ी एक गेम खेल रहे हैं। वे 0 और 1 के रूप में संख्यांकित हैं। एक चर x है जिसका प्रारंभिक मान 0 है। गेम के N राउंड हैं। i-वें राउंड में व्यक्ति S[i] निम्नलिखित में से एक करता है: x को x XOR A[i] से बदलें, अन्यथा कुछ न करें। व्यक्ति 0 इस गेम के अंत में 0 चाहता है लेकिन व्यक्ति 1 गैर-शून्य चाहता है। हमें जांचना है कि अंत में x 0 हो जाता है या नहीं।
उदाहरण के लिए, यदि इनपुट A = [1, 2]; S = "10" है, तो आउटपुट 1 होगा, क्योंकि व्यक्ति 1 x को 0 XOR 1 = 1 से बदलता है, तो यह व्यक्ति 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
