মান লক্ষ্য করুন একটি n এলিমেন্টের অ্যারে A এবং আরেকটি সংখ্যা s। একটি খালি জলের মগ এবং n টি নন-এমপ্টি জলের মগ টেবিলে আছে। একটি গেমে কিছু খেলাড়ী আছে। প্রতিটি মুভে, একজন খেলাড়ী একটি নন-এমপ্টি মগ নেয় এবং সেটার সारा জল কাপে ঢেলে দেয়। যদি ওভারফ্লো হয়, তবে খেলাড়ীটি হারাবে। আমাদের চেক করতে হবে সবাই কি বিজয়ী হবে (কাপ ওভারফ্লো করবে না)। যদি এক কাপ ইতিমধ্যে পুরোপুরি ভরা থাকে, তবে পরবর্তী খেলাড়ী তার মুভ খেলবে না। এখানে s হলো খালি কাপের ক্যাপাসিটি এবং A[i] হলো i-তম কাপে থাকা জলের পরিমাণ।
তাই, যদি ইনপুট হয় A = [3, 1, 3]; s = 4, তবে আউটপুট হবে True, কারণ প্রথম এবং দ্বিতীয় খেলাড়ীর দ্বারা কাপটি ভরা হবে। শেষটির জন্য, খেলাড়ী সে মুভ খেলবে না।
ধাপসমূহ
এটি সমাধান করার জন্য, আমরা এই ধাপগুলো অনুসরণ করব −
k := 0
n := size of A
sort the array A
for initialize i := 0, when i < n - 1, update (increase i by 1), do:
k := k + A[i]
if k > s, then:
return false
Otherwise
return true
উদাহরণ
বेहतर বোঝার জন্য ইমপ্লিমেন্টেশন দেখি −
#include <bits/stdc++.h>
using namespace std;
bool solve(vector<int> A, int s){
int k = 0;
int n = A.size();
sort(A.begin(), A.end());
for (int i = 0; i < n - 1; i++)
k += A[i];
if (k > s)
return false;
else
return true;
}
int main(){
vector<int> A = { 3, 1, 3 };
int s = 4;
cout << solve(A, s) << endl;
}
ইনপুট
{ 3, 1, 3 }, 4
আউটপুট
1
