প্রদত্ত সীমাবদ্ধতার সাথে ম্যাট্রিক্সের শেষ মান খুঁজে পেতে C++ প্রোগ্রাম

ধরুন আমাদের কাছে N উপাদান সহ A সংখ্যাগুলির একটি তালিকা রয়েছে। উপাদানগুলি হল 1, 2 বা 3, একটি সংখ্যা বিবেচনা করুন X[1][j] =A[j] যেখানে j 1 থেকে N এর মধ্যে রয়েছে। এবং X[i][j] =|X[i-1][ j] - X[i-1][j+1]| যেখানে i রেঞ্জ 2 থেকে N এবং j রেঞ্জ 1 থেকে 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
So the answer is 1

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

Define a function calc(), this will take N, M,
cnt := 0
for initialize k := N, when k is non-zero, update k >>= 1, do:
   cnt := floor of (cnt + k)/2
for initialize k := M, when k is non-zero, update k >>= 1, do:
   cnt := floor of (cnt - k)/2
for initialize k := N - M, when k is non-zero, update k >>= 1, do:
   cnt := floor of (cnt - k)/2
return invert of cnt
From the main method, do the following
n := size of A
Define an array arr of size (n + 1)
for initialize i := 1, when i < n, update (increase i by 1), do:
   arr[i - 1] = |A[i] - A[i - 1]|
(decrease n by 1)
hh := 1, pd := 0, ck := 0
for initialize i := 0, when i < n, update (increase i by 1), do:
   if arr[i] is non-zero, then:
      if arr[i] is same as 1, then:
         hh := 0
         pd := pd XOR calc(n - 1, i)
      Otherwise
         ck := ck XOR calc(n - 1, i)
ck := ck AND hh
if pd XOR ck is non-zero, then:
   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 }