মান লিজিয়ে, A নামক একটি অ্যারে আছে যাতে N টি উপাদান রয়েছে। N টি বিডাল আছে যাদের ১ থেকে N পর্যন্ত নম্বর দেওয়া আছে। প্রতিটি বিডাল একটি টুপি পরেছে এবং i-তম বিডাল বলে "আমাকে বাদ দিয়ে বাকি N-1 টি বিডালের টুপির মাঝে ঠিক A[i] টি ভিন্ন রঙ আছে"। আমাদের লক্ষ্য হলো যাচাই করা যে কি টুপির রঙের এমন কোনো সিকোয়েন্স আছে যা সব বিডালের কথামতো সঠিক।
যেমন, ইনপুট হলে A = [1, 2, 2], তবে আউটপুট হবে True, কারণ যদি বিডাল ১, ২, ৩ যথাক্রমে লাল, নীল, নীল টুপি পরে, তবে সেটি সব বিডালের কথামতো সঠিক।
সমাধানের ধাপসমূহ
এই সমস্যাটি সমাধান করার জন্য নিচের ধাপগুলো অনুসরণ করব:
mn := inf, mx = 0, cnt = 0 n := A-র আকার a অ্যারে সংজ্ঞায়িত করুন আকার (n + 1) i := 1 থেকে n পর্যন্ত: a[i] := A[i - 1] mn := min(mn, a[i]) mx = max(mx, a[i]) i := 1 থেকে n পর্যন্ত: if a[i] == mn, তবে: cnt ১ বাড়িয়ে if mx == mn, তবে: if mn == n - 1 বা 2 * mn <= n, তবে: return true অন্যথায়: return false অন্যথায় যদি mx == mn + 1, তবে: if mn >= cnt এবং n - cnt >= 2 * (mx - cnt), তবে: return true অন্যথায়: return false অন্যথায়: return false
উদাহরণ
নিচের ইমপ্লিমেন্টেশনটি দেখুন আরও ভালো বুঝতে:
#include <bits/stdc++.h> using namespace std; bool solve(vector<int> A) { int mn = 99999, mx = 0, cnt = 0; int n = A.size(); vector<int> a(n + 1); for (int i = 1; i <= n; ++i) { a[i] = A[i - 1]; mn = min(mn, a[i]), mx = max(mx, a[i]); } for (int i = 1; i <= n; ++i) if (a[i] == mn) ++cnt; if (mx == mn) { if (mn == n - 1 || 2 * mn <= n) return true; else return false; } else if (mx == mn + 1) { if (mn >= cnt && n - cnt >= 2 * (mx - cnt)) return true; else return false; } else return false; } int main() { vector<int> A = { 1, 2, 2 }; cout << solve(A) << endl; } ইনপুট
{ 1, 2, 2 } আউটপুট
1
