मान लीजिए Dota2 की दुनिया में, दो पार्टियां हैं - द रेडिएंट और द डायर। Dota2 सीनेट में दो पार्टियों से आने वाले सीनेटर होते हैं। अब सीनेट Dota2 गेम में कुछ बदलाव पर निर्णय लेना चाहती है। इस परिवर्तन के लिए मतदान एक राउंड-आधारित प्रक्रिया है। प्रत्येक राउंड में, प्रत्येक सीनेटर दो अधिकारों में से एक का प्रयोग कर सकता है:
- एक सीनेटर के अधिकार पर प्रतिबंध लगाएं - एक सीनेटर किसी अन्य सीनेटर को इस और सभी बाद के राउंड में अपने सभी अधिकार खोने के लिए मजबूर कर सकता है।
- विजय की घोषणा करें - यदि यह सीनेटर पाता है कि मतदान का अधिकार रखने वाले सभी सीनेटर एक ही पार्टी से हैं, तो वह विजय की घोषणा कर सकता है और गेम में बदलाव के बारे में निर्णय ले सकता है।
एक स्ट्रिंग दी गई है जो प्रत्येक सीनेटर की पार्टी संबंधित को दर्शाती है। वर्ण 'R' और 'D' क्रमशः रेडिएंट पार्टी और डायर पार्टी का प्रतिनिधित्व करते हैं। यदि n सीनेटर हैं, तो दी गई स्ट्रिंग का आकार n होगा।
राउंड-आधारित प्रक्रिया दी गई क्रम में पहले सीनेटर से अंतिम सीनेटर तक शुरू होती है। यह प्रक्रिया मतदान के अंत तक चलेगी। जिन सीनेटरों ने अपने अधिकार खो दिए हैं, उन्हें प्रक्रिया के दौरान छोड़ दिया जाएगा।
मान लीजिए हर सीनेटर काफी समझदार है और अपनी पार्टी के लिए सर्वोत्तम रणनीति खेलेगा, आप भविष्यवाणी करना चाहते हैं कि कौन सी पार्टी अंततः विजय की घोषणा करेगी और Dota2 गेम में बदलाव करेगी। आउटपुट रेडिएंट या डायर होना चाहिए।
उदाहरण के लिए, यदि इनपुट "RDD" जैसा है, तो यह डायर होगा। ऐसा इसलिए है क्योंकि पहला सीनेटर रेडिएंट से आता है और वह राउंड 1 में अगले सीनेटर के अधिकार पर प्रतिबंध लगा सकता है। और दूसरा सीनेटर अब कोई अधिकार नहीं प्रयोग कर सकता क्योंकि उसका अधिकार प्रतिबंधित कर दिया गया है। उसके बाद तीसरा सीनेटर डायर से आता है और वह राउंड 1 में पहले सीनेटर के अधिकार पर प्रतिबंध लगा सकता है। अब राउंड 2 में, तीसरा सीनेटर बस विजय की घोषणा कर सकता है क्योंकि वह सीनेट में एकमात्र व्यक्ति है जो मतदान कर सकता है।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
- एक क्यू
q1,q2बनाएं,n := स्ट्रिंग का आकार। सभी R के लिएq1में डालें, और सभी D के लिए,q2में डालें। - जब तक दोनों क्यू खाली नहीं हैं
- यदि
q1 का फ्रंट तत्व < q2 का फ्रंट तत्व, तोn को q1 में डालें,q2औरq1से हटाएं
- अन्यथा
n को q2 में डालें,q2औरq1से हटाएं nको 1 से बढ़ाएं
- यदि
- यदि क्यू खाली है, तो डायर लौटाएं, अन्यथा, रेडिएंट लौटाएं
उदाहरण (C++)
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; class Solution { public: string predictPartyVictory(string s) { queue <int> q1, q2; int n = s.size(); for(int i = 0; i < s.size(); i++){ if(s[i] == 'R'){ q1.push(i); } else { q2.push(i); } } while(q1.size() && q2.size()){ if(q1.front() < q2.front()){ q1.push(n); q2.pop(); q1.pop(); } else { q2.push(n); q2.pop(); q1.pop(); } n++; } return q1.empty()? "Dire" : "Radiant"; } }; main(){ Solution ob; cout <<(ob.predictPartyVictory("RDD")); }इनपुट
"RDD"
आउटपुट
Dire
