কনসেপ্ট
দেওয়া অ্যারে arr[]-এর nটি ধনাত্মক পূর্ণসংখ্যা থেকে arr[i] এবং arr[j] বের করুন যাতে arr[i]Carr[j] সর্বোচ্চ হয়। একাধিক валиড জোড়া থাকলে যেকোনো একটি প্রিন্ট করুন।
ইনপুট
arr[] = {4, 1, 2} আউটপুট
4 2 ⁴C₁ = 4 ⁴C₂ = 4 ²C₁ = 4 (4, 2) একমাত্র জোড়া যেটার সর্বোচ্চ nCr।
পদ্ধতি
ⁿCᵣ একটি মনোটোনিক ক্রমবর্ধমান ফাংশন, অর্থাৎ ⁿ⁺¹Cᵣ > ⁿCᵣ। এই ফ্যাক্ট ব্যবহার করে উত্তরের কাছে যেতে পারি: সব ইন্টিজার থেকে ম্যাক্স n বেছে নিন। এভাবে n ফিক্সড হয়ে যায়।
এখন r-র জন্য ফোকাস করুন। ⁿCᵣ = ⁿCₙ₋ᵣ, অর্থাৎ nCr প্রথম বাড়বে তারপর কমবে।
- n বিজোড় হলে ম্যাক্সিমা হবে n/2 এবং n/2+1-এ।
- n=11 হলে ম্যাক্সিমা ¹¹C₅ এবং ¹¹C₆-এ।
- n জোড় হলে ম্যাক্সিমা হবে n/2-এ।
- n=4 হলে ম্যাক্সিমা ⁴C₂-এ।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
void printMaxValPair1(vector<long long>& v1, int n1){
sort(v1.begin(), v1.end());
long long N1 = v1[n1 - 1];
if (N1 % 2 == 1) {
long long first_maxima1 = N1 / 2;
long long second_maxima1 = first_maxima1 + 1;
long long ans1 = 3e18, ans2 = 3e18;
long long from_left1 = -1, from_right1 = -1;
long long from = -1;
for (long long i = 0; i < n1; ++i) {
if (v1[i] > first_maxima1) {
from = i;
break;
}
else {
long long diff = first_maxima1 - v1[i];
if (diff < ans1) {
ans1 = diff;
from_left1 = v1[i];
}
}
}
from_right1 = v1[from];
long long diff1 = first_maxima1 - from_left1;
long long diff2 = from_right1 - second_maxima1;
if (diff1 < diff2)
cout << N1 << " " << from_left1;
else
cout << N1 << " " << from_right1;
}
else {
long long maxima = N1 / 2;
long long ans1 = 3e18;
long long R = -1;
for (long long i = 0; i < n1 - 1; ++i) {
long long diff = abs(v1[i] - maxima);
if (diff < ans1) {
ans1 = diff;
R = v1[i];
}
}
cout << N1 << " " << R;
}
}
int main(){
vector<long long> v1 = { 1, 1, 2, 3, 6, 1 };
int n1 = v1.size();
printMaxValPair1(v1, n1);
return 0;
} আউটপুট
6 3
