মান লক্ষ্য করুন একটি n এলিমেন্টের অ্যারে A। n টি গ্রুপ ছিল ছাত্রদের। একটি গ্রুপ হয় একজনের যিনি কেউ যেকোনো সাথে কোড লিখতে পারেন, বা দুজনের যারা একই টিমে কোড লিখতে চান। কিন্তু মেন্টর ঠিক তিনজনের টিম বানাতে সিদ্ধান্ত নিয়েছে। আমাদের মেন্টর যে সর্বাধিক কতগুলো তিনজনের টিম বানাতে পারবে তা বের করতে হবে। দুজনের গ্রুপের জন্য, হয় উভয়ই কোড লিখবে, বা উভয়ই লিখবে না। যদি দুজনের গ্রুপ থেকে দুজন কোড লিখে, তবে তারা একই টিমে থাকতে হবে।
তাই, যদি ইনপুট হয় A = [2, 2, 2, 1, 1, 1, 1], তবে আউটপুট হবে ৩, কারণ মেন্টর টিম বানাতে পারে: [প্রথম দুজনের গ্রুপ এবং সপ্তম একজনের গ্রুপ], [দ্বিতীয় দুজনের গ্রুপ এবং ষষ্ঠ একজনের গ্রুপ], [তৃতীয় দুজনের গ্রুপ এবং চতুর্থ একজনের গ্রুপ]।
ধাপসমূহ
এটি সমাধান করার জন্য, আমরা এই ধাপগুলো অনুসরণ করব −
p := 0
q := 0
x := size of A
for initialize i := 0, when i < x, update (increase i by 1), do:
a := A[i]
if a is same as 1, then:
p := p + 1
Otherwise
q := q + 1
if p > q, then:
return q + (p - q)
otherwise when p < q, then:
return p
Otherwise
return p
উদাহরণ
বेहतर বোঝার জন্য ইমপ্লিমেন্টেশন দেখি −
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A){
int p = 0, q = 0;
int x = A.size();
for (int i = 0; i < x; i++){
int a = A[i];
if (a == 1){
p = p + 1;
}
else{
q = q + 1;
}
}
if (p > q){
return q + (p - q) / 3;
}
else if (p < q){
return p;
}
else{
return p;
}
}
int main(){
vector<int> A = { 2, 2, 2, 1, 1, 1, 1 };
cout << solve(A) << endl;
}
ইনপুট
{ 2, 2, 2, 1, 1, 1, 1 }
আউটপুট
3
