মান লিখুন: আমাদের কাছে K উপাদান বিশিষ্ট একটি অ্যারে A রয়েছে। একটি গেম বিবেচনা করুন যেখানে Nটি খেলোয়াড় এবং একটি গেম মাস্টার আছে। গেমে Kটি রাউন্ড আছে। i-তম রাউন্ডে গেম মাস্টার A[i] সংখ্যক বাচ্চা দিয়ে গ্রুপ বানানোর ঘোষণা করেন। তারপর বাকি বাচ্চারা A[i] সংখ্যা করে যতটুকু গ্রুপ বানাতে পারে বানায়। এক বাচ্চা একাধিক গ্রুপে থাকতে পারবে না। গ্রুপ ছাড়া যারা থাকে তারা গেম ছেড়ে দেয়। বাকি পরবর্তী রাউন্ডে যায়। একটি রাউন্ডে কেউ বাদ পড়তে পারে না। শেষে K-তম রাউন্ডের পর ঠিক দুজন বাচ্চা বাঁচে এবং তারা বিজয়ী ঘোষিত হয়। খেলা শুরু হওয়ার আগে বাচ্চাদের ন্যূনতম ও সর্বোচ্চ সম্ভাব্য সংখ্যা বের করতে হবে, অথবা বলতে হবে কোনো বৈধ N নেই।
উদাহরণ
যদি ইনপুট হয় A = [3, 4, 3, 2], তবে আউটপুট হবে [6, 8]। কারণ ৬ বাচ্চা দিয়ে শুরু করলে:
- রাউন্ড ১: ৬ জন ৩-জন করে ২ গ্রুপ বানায়
- রাউন্ড ২: ৪ ও ২ জন করে ২ গ্রুপ
- রাউন্ড ৩: ১ ও ৩ জন, ১ জন বাদ পড়ে
- রাউন্ড ৪: ১ ও ২ জন, ১ জন বাদ পড়ে
শেষে ২ জন বাঁচে।
সমাধানের ধাপসমূহ
n := A এর আকার
a, l, r অ্যারে (আকার ১০০০১০)
l := 2, r := 2
for i := 1 থেকে n: a[i] := A[i-1]
for i := n থেকে ১ পর্যন্ত (হ্রাসমান):
x := a[i]
L := ceil(l/x) * x
R := floor(r/x) * x
যদি L > R: -1, 0 রিটার্ন করুন
l := L, r := R + x - 1
l, r রিটার্ন করুন
C++ বাস্তবায়ন
#include <bits/stdc++.h>
using namespace std;
void solve(vector<int> A) {
int n = A.size();
int l, r, a[100010];
l = 2, r = 2;
for (int i = 1; i <= n; i++) a[i] = A[i - 1];
for (int i = n; i >= 1; i--) {
int x = a[i], L = (l + x - 1) / x * x, R = r / x * x;
if (L > R) {
cout << "-1, 0";
}
l = L, r = R + x - 1;
}
cout << l << ", " << r << endl;
}
int main() {
vector<int> A = { 3, 4, 3, 2 };
solve(A);
}
ইনপুট
{ 3, 4, 3, 2 }
আউটপুট
6, 8
