মান লিজিয়ে, A নামক একটি অ্যারে আছে যাতে N টি উপাদান রয়েছে। N টি বক্স আছে এবং সেগুলো বৃত্তাকারভাবে সাজানো আছে। i-তম বক্সে A[i] টি পাথর আছে। আমাদের লক্ষ্য হলো যাচাই করা যে কি আমরা বারবার নিচের অপারেশন করলে সব পাথর বক্স থেকে সরিয়ে ফেলতে পারি: একটি বক্স নির্বাচন করুন, মনে করুন i-তম বক্স। ১ থেকে N পর্যন্ত প্রতিটি j এর জন্য, (i+j)-তম বক্স থেকে ঠিক j টি পাথর সরিয়ে ফেলুন। এখানে (N+k)-তম বক্স কে k-তম বক্স বলা হয়। এই অপারেশনটি করা যাবে না যদি কোনো বক্সে পর্যাপ্ত পাথর না থাকে।
যেমন, ইনপুট হলে A = [4, 5, 1, 2, 3], তবে আউটপুট হবে True, কারণ দ্বিতীয় বক্স থেকে শুরু করে সব পাথর সরানো সম্ভব।
সমাধানের ধাপসমূহ
এই সমস্যাটি সমাধান করার জন্য নিচের ধাপগুলো অনুসরণ করব:
n := A-র আকার a অ্যারে সংজ্ঞায়িত করুন আকার (n + 1) b অ্যারে সংজ্ঞায়িত করুন আকার (n + 1) sum := 0, p := n * (n + 1) / 2 i := 1 থেকে n পর্যন্ত: a[i] := A[i - 1] sum := sum + a[i] if sum mod p != 0, তবে: return false k := sum / p i := 1 থেকে n পর্যন্ত: b[i] := a[i] - a[(i mod n) + 1] sum := 0 i := 1 থেকে n পর্যন্ত: a[i] := b[i] sum := sum + a[i] if sum != 0, তবে: return false i := 1 থেকে n পর্যন্ত: if (a[i] + k) mod n != 0 বা a[i] + k < 0, তবে: return false return true
উদাহরণ
নিচের ইমপ্লিমেন্টেশনটি দেখুন আরও ভালো বুঝতে:
#include <bits/stdc++.h> using namespace std; bool solve(vector<int> A) { int n = A.size(); vector<int> a(n + 1); vector<int> b(n + 1); int sum = 0, p = n * (n + 1) / 2; for (int i = 1; i <= n; i++) { a[i] = A[i - 1]; sum += a[i]; } if (sum % p != 0) { return false; } int k = sum / p; for (int i = 1; i <= n; i++) { b[i] = a[i] - a[i % n + 1]; } sum = 0; for (int i = 1; i <= n; i++) { a[i] = b[i]; sum += a[i]; } if (sum != 0) { return false; } for (int i = 1; i <= n; i++) { if ((a[i] + k) % n != 0 || a[i] + k < 0) { return false; } } return true; } int main(){ vector<int> A = { 4, 5, 1, 2, 3 }; cout << solve(A) << endl; } ইনপুট
{ 4, 5, 1, 2, 3 } আউটপুট
1
