মান লিজিয়ে, A নামক একটি তালিকা আছে যাতে N টি উপাদান রয়েছে। উপাদানগুলো ১, ২ বা ৩। বিবেচনা করুন X[1][j] = A[j] যেখানে j হলো ১ থেকে N পর্যন্ত। এবং X[i][j] = |X[i-1][j] - X[i-1][j+1]| যেখানে i হলো ২ থেকে N পর্যন্ত এবং j হলো ১ থেকে N+1-i পর্যন্ত। আমাদের লক্ষ্য হলো X[i][j]-র মান বের করা।
যেমন, ইনপুট হলে A = [1,2,3,1], তবে আউটপুট হবে 1, কারণ
X[1][1] to X[1][4] are 1, 2, 3, 1 X[2][1], X[2][2], X[2][3] are |1-2| = 1, |2 - 3| = 1 and |3 - 1| = 2 X[3][1], X[3][2] are | 1 - 1| = 0, | 1 - 2| = 1. X[4][1] = |0 - 1| = 1 তাই উত্তর হলো 1
সমাধানের ধাপসমূহ
এই সমস্যাটি সমাধান করার জন্য নিচের ধাপগুলো অনুসরণ করব:
calc() ফাংশন সংজ্ঞায়িত করুন, যা N, M গ্রহণ করবে: cnt := 0 k := N থেকে k নন-জিরো পর্যন্ত, k >>= 1: cnt := floor((cnt + k)/2) k := M থেকে k নন-জিরো পর্যন্ত, k >>= 1: cnt := floor((cnt - k)/2) k := N - M থেকে k নন-জিরো পর্যন্ত, k >>= 1: cnt := floor((cnt - k)/2) return cnt-র ইনভার্ট মূল ফাংশন থেকে: n := A-র আকার arr অ্যারে সংজ্ঞায়িত করুন আকার (n + 1) i := 1 থেকে n-1 পর্যন্ত: arr[i - 1] = |A[i] - A[i - 1]| n ১ কমিয়ে hh := 1, pd := 0, ck := 0 i := 0 থেকে n-1 পর্যন্ত: if arr[i] নন-জিরো, তবে: if arr[i] == 1, তবে: hh := 0 pd := pd XOR calc(n - 1, i) অন্যথায়: ck := ck XOR calc(n - 1, i) ck := ck AND hh if pd XOR ck নন-জিরো, তবে: return "1" + hh return "0"
উদাহরণ
নিচের ইমপ্লিমেন্টেশনটি দেখুন আরও ভালো বুঝতে:
#include <bits/stdc++.h> using namespace std; int calc(int N, int M) { int cnt = 0; for (int k = N; k; k >>= 1) cnt += k >> 1; for (int k = M; k; k >>= 1) cnt -= k >> 1; for (int k = N - M; k; k >>= 1) cnt -= k >> 1; return !cnt; } string solve(vector<int> A) { int n = A.size(); vector<int> arr(n + 1); for (int i = 1; i < n; i++) { arr[i - 1] = abs(A[i] - A[i - 1]); } --n; bool hh = 1, pd = 0, ck = 0; for (int i = 0; i < n; i++) if (arr[i]) { if (arr[i] == 1) hh = 0, pd ^= calc(n - 1, i); else ck ^= calc(n - 1, i); } ck &= hh; if (pd ^ ck) return "1" + hh; return "0"; } int main(){ vector<int> A = { 1, 2, 3, 1 }; cout << solve(A) << endl; } ইনপুট
{ 1, 2, 3, 1 } আউটপুট
1
