মান লিখুন: আমাদের কাছে একটি অ্যারে A রয়েছে nটি ভিন্ন উপাদানের সাথে, এবং আরেকটি সংখ্যা x। nটি সোনার টুকরো আছে। i-তম সোনার ওজন হল A[i]। আমরা এই nটি সোনা ওজন স্কেলে একটা একটা করে রাখব। কিন্তু স্কেলটিতে একটি অসামান্য ত্রুটি রয়েছে: যদি এর ওপর মোট ওजन ঠিক x হয়, তবে এটি বিস্ফোরিত হবে। আমাদের যাচাই করতে হবে যে কি আমরা সব nটি সোনা কতটুকু ক্রমে স্কেলে রাখতে পারি, প্রক্রিয়ার সময় স্কেল বিস্ফোরিত না করে। যদি সম্ভব হয়, তবে সেই ক্রমটি খুঁজে বের করতে হবে। যদি সম্ভব না হয়, তবে "IMPOSSIBLE" চিহ্নিত করতে হবে।
উদাহরণ
যদি ইনপুট হয় A = [1, 2, 3, 4, 8]; x = 6, তবে আউটপুট হবে [8, 1, 2, 3, 4], অন্যান্য বৈধ ক্রমও সম্ভব।
সমাধানের ধাপসমূহ
এই সমস্যাটি সমাধান করার জন্য আমরা নিচের ধাপগুলো অনুসরণ করব:
s := 0
n := A এর আকার
for i := 0 থেকে n-1 পর্যন্ত:
s := s + A[i]
যদি s == x হয়:
"IMPOSSIBLE" রিটার্ন করুন
s := 0
for i := 0 থেকে n-1 পর্যন্ত:
s := s + A[i]
যদি s == x হয়:
A[i+1], A[i] প্রিন্ট করুন
i বাড়ান (পরবর্তী ইটারেশনে যান)
A[i] প্রিন্ট করুন
C++ বাস্তবায়ন
#include <bits/stdc++.h>
using namespace std;
void solve(vector<int> A, int x) {
int s = 0;
int n = A.size();
for (int i = 0; i < n; i++) {
s += A[i];
}
if (s == x) {
cout << "IMPOSSIBLE";
return;
}
s = 0;
for (int i = 0; i < n; i++) {
s += A[i];
if (s == x) {
cout << A[i + 1] << ", " << A[i] << ", ";
i++;
continue;
}
cout << A[i] << ", ";
}
}
int main() {
vector<int> A = { 1, 2, 3, 4, 8 };
int x = 6;
solve(A, x);
}
ইনপুট
{ 1, 2, 3, 4, 8 }, 6
আউটপুট
1, 2, 4, 3, 8,
