Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

कंप्यूटर्स को जोड़ने के लिए केबल लंबाई को न्यूनतम करने के तरीकों की संख्या गिनने के लिए C++ प्रोग्राम


मान लीजिए हमारे पास N-तत्वों वाले दो ऐरे A और B हैं। मान लें N कंप्यूटर और N सॉकेट हैं। iवें कंप्यूटर का निर्देशांक A[i] है और iवें सॉकेट का निर्देशांक B[i] है। ये 2N निर्देशांक युग्मवार विशिष्ट हैं। हम प्रत्येक कंप्यूटर को केबल द्वारा एक सॉकेट से जोड़ना चाहते हैं। प्रत्येक सॉकेट को अधिकतम एक कंप्यूटर से जोड़ा जा सकता है। हमें उन तरीकों की संख्या गिननी है जिनसे हम केबल की लंबाई को न्यूनतम कर सकते हैं। यदि उत्तर बहुत बड़ा है, तो परिणाम को 10^9 + 7 मॉड्यूलो वापस करें।

उदाहरण के लिए, यदि इनपुट A = [0, 10]; B = [20, 30] है, तो आउटपुट 2 होगा, क्योंकि दो इष्टतम कनेक्शन हैं, (0 से 20, 10 से 30) और (0 से 30, 10 से 20)। दोनों मामलों में, केबल की कुल लंबाई 40 है।

चरण

इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:

maxn := 200005 p := 10^9 + 7 पूर्णांक प्रकार के तत्वों के लिए जोड़ी का एक ऐरे परिभाषित करें n := A का आकार i := 0 से n-1 तक, करें: a[i] का पहला तत्व := A[i] a[i] का दूसरा तत्व := 1 i := n से 2*n-1 तक, करें: a[i] का पहला तत्व := B[i - n] a[i] का दूसरा तत्व := -1 ऐरे a को सॉर्ट करें ways := 1, val = 0 i := 0 से 2*n-1 तक, करें: यदि val * a[i] का दूसरा तत्व < 0, तो: ways := ways * |val| val := val + a[i] का दूसरा तत्व ways वापस करें

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

#include <bits/stdc++.h> using namespace std; int solve(vector<int> A, vector<int> B){    long maxn = 200005;    long p = 1000000007;    pair<int, int> a[maxn];    int n = A.size();    for (int i = 0; i < n; i++){       a[i].first = A[i];       a[i].second = 1;    }    for (int i = n; i < 2 * n; i++){       a[i].first = B[i - n];       a[i].second = -1;    }    sort(a, a + 2 * n);    long long ways = 1, val = 0;    for (int i = 0; i < 2 * n; i++){       if (val * a[i].second < 0){          ways = ways * abs(val) % p;       }       val += a[i].second;    }    return ways; } int main(){    vector<int> A = { 0, 10 };    vector<int> B = { 20, 30 };    cout << solve(A, B) << endl; }

इनपुट

{ 0, 10 }, { 20, 30 }

आउटपुट

2

  1. आकार d के डोडेकागन बनाने के तरीकों की संख्या गिनने के लिए C++ प्रोग्राम आकार d के डोडेकागन बनाने के तरीकों की संख्या गिनने के लिए C++ प्रोग्राम

    मान लीजिए हमारे पास एक संख्या d है। मान लें कि भुजा लंबाई 1 के अनंत वर्गाकार टाइल्स और नियमित त्रिकोणीय टाइल्स हैं। हमें उन तरीकों की संख्या ढूंढनी है जिनसे हम इन टाइल्स का उपयोग करके भुजा d के साथ नियमित डोडेकागन (12-भुज बहुभुज) बना सकते हैं। यदि उत्तर बहुत बड़ा है, तो परिणाम को 998244353 मॉड्यूलो

  1. Python में मैट्रिक्स के खाली सेल चुनने के कितने तरीके हैं, इसकी जांच करने का प्रोग्राम Python में मैट्रिक्स के खाली सेल चुनने के कितने तरीके हैं, इसकी जांच करने का प्रोग्राम

    मान लीजिए हमारे पास एक N x N बाइनरी मैट्रिक्स है जहां 0 खाली सेल के लिए है और 1 ब्लॉक्ड सेल है, हमें N खाली सेल चुनने के तरीकों की संख्या ढूंढनी है ताकि हर पंक्ति और हर कॉलम में कम से कम एक चुना हुआ सेल हो। यदि उत्तर बहुत बड़ा है तो परिणाम mod 10^9 + 7 लौटाएंइसलिए, यदि इनपुट इस तरह है000000010तो आउट

  1. पायथन में ट्री को दो ट्री में विभाजित करने के तरीकों की गिनती का प्रोग्राम पायथन में ट्री को दो ट्री में विभाजित करने के तरीकों की गिनती का प्रोग्राम

    मान लीजिए हमारे पास एक बाइनरी ट्री है जिसमें 0, 1 और 2 मान हैं। रूट में कम से कम एक 0 नोड और एक 1 नोड है। अब मान लीजिए एक ऑपरेशन है जहां हम ट्री में एक किनारा हटाते हैं और ट्री दो अलग-अलग ट्री बन जाता है। हमें उन तरीकों की संख्या ढूंढनी है जिनसे हम एक किनारा हटा सकते हैं जैसे कि दोनों ट्री में से को