আমাদের তিনটি রেখায় কিছু পয়েন্ট দেওয়া আছে। এখন আমাদের বের করতে হবে এই পয়েন্টগুলো থেকে কতগুলো ত্রিভুজ তৈরি করা সম্ভব। উদাহরণ −
ইনপুট: m = 3, n = 4, k = 5 আউটপুট: 205 ইনপুট: m = 2, n = 2, k = 1 আউটপুট: 10
এই সমস্যাটি সমাধানের জন্য কৌম্বিনেট্রিক্স (Combinatorics) প্রয়োগ করে একটি সূত্র তৈরি করব।
এই পদ্ধতিতে, আমরা বর্তমান পরিস্থিতিতে কৌম্বিনেট্রিক্স প্রয়োগ করে একটি সূত্র তৈরি করব যা আমাদের ফলাফল দেবে।
নিচে দিয়ে गयी C++ সিনট্যাক্স ব্যবহার করে এই সমস্যা সমাধান করা যায় −
#include <bits/stdc++.h> #define MOD 1000000007 using namespace std; long long fact(long long n) { if(n <= 1) return 1; return ((n % MOD) * (fact(n-1) % MOD)) % MOD; } long long comb(int n, int r) { return (((fact(n)) % MOD) / ((fact(r) % MOD) * (fact(n-r) % MOD)) % MOD); } int main() { int n = 3; int m = 4; int r = 5; long long linen = comb(n, 3); // n-র ৩ দিয়ে কম্বিনেশন long long linem = comb(m, 3); // m-র ৩ দিয়ে কম্বিনেশন long long liner = comb(r, 3); // r-র ৩ দিয়ে কম্বিনেশন long long answer = comb(n + m + r, 3); // সব পয়েন্টের ৩ দিয়ে কম্বিনেশন answer -= (linen + linem + liner); cout << answer << "\n"; return 0; }
205
এই পদ্ধতিতে, আমরা সব পয়েন্ট (n+m+r) নিয়ে ৩-টির কম্বিনেশন বের করি, অর্থাৎ comb(n+m+r, ৩)। যেহেতু তিনটি পয়েন্ট ত্রিভুজ বানাবে না যদি তারা কলিনিয়ার (collinear) হয়, তাই আমরা প্রতিটি রেখার পয়েন্টগুলোর মধ্যে ৩-টির কম্বিনেশন বের করি (linen, linem, liner) এবং সেগুলোর যোগফল মোট কম্বিনেশন থেকে বিয়োগ করি। বাকি ফলাফলটিই আমাদের উত্তর।
এই আর্টিকেলে আলোচনা করা হয়েছে তিনটি রেখার পয়েন্ট থেকে কতগুলো ত্রিভুজ তৈরি করা যায়, কৌম্বিনেট্রিক্স প্রয়োগ করে। আমরা এই সমস্যার C++ প্রোগ্রাম ও সম্পূর্ণ পদ্ধতি দেখেছি। একই প্রোগ্রাম C, Java, Python ইত্যাদি ভাষায়ও লিখা যায়। আশা করি আপনি এই আর্টিকেলটি সহায়ক পাবেন।