n এবং k দেওয়া আছে। ১ থেকে n সংখ্যা দিয়ে একটি পারমুটেশন বানাতে হবে যাতে ঠিক kটি পিক (peak) থাকে। পিক = A[i] > A[i-1] এবং A[i] > A[i+1]। অসম্ভব হলে -1।
সমাধানের ধাপসমূহ
সর্বোচ্চ পিক = (n-1)/2। এর চেয়ে বড় k হলে -1। ১ থেকে n পর্যন্ত অ্যারে বানান। i=2 থেকে 2k পর্যন্ত ২ ধাপে i এবং i+1 স왪 করুন। এতে kটি পিক তৈরি হবে।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
void solve(int n, int k) {
if (k > (n - 1) / 2) { cout << "-1"; return; }
int a[101];
for (int i = 1; i <= n; i++) a[i] = i;
for (int i = 2; i <= 2 * k; i += 2)
swap(a[i], a[i + 1]);
for (int i = 1; i <= n; i++)
cout << a[i] << ", ";
}
int main() {
int n = 5, k = 2;
solve(n, k);
return 0;
}
ইনপুট
5, 2
আউটপুট
1, 3, 2, 5, 4,
ব্যাখ্যা
পারমুটেশন: [1, 3, 2, 5, 4]। পিকগুলো: i=2 (3>1 এবং 3>2), i=4 (5>2 এবং 5>4)। মোট ২টি পিক।
