ধরুন Dota2 এর জগতে, দুটি পক্ষ রয়েছে - দ্য রেডিয়েন্ট এবং ডায়ারও৷ Dota2 সিনেট দুটি দল থেকে আসা সিনেটর নিয়ে গঠিত। এখন সেনেট Dota2 গেমের মধ্যে কয়েকটি পরিবর্তনের একটি পছন্দ গঠন করতে চায়। এই পরিবর্তনের জন্য ভোটদান একটি রাউন্ড-ভিত্তিক পদ্ধতি হতে পারে। প্রতিটি রাউন্ডে, প্রতিটি সিনেটর দুটি অধিকারের মধ্যে একটি ব্যবহার করতে পারেন -
-
একজন সিনেটরের অধিকার নিষিদ্ধ করুন − একজন সিনেটর অন্য সিনেটরকে এই এবং পরবর্তী রাউন্ডের সময় তার সমস্ত অধিকার হারাতে পারেন৷
-
বিজয় ঘোষণা করুন − যদি এই সিনেটর দেখতে পান যে সিনেটরদের এখনও ভোট দেওয়ার অধিকার আছে তারা সবাই সমতুল্য দলের, তিনি বিজয় ঘোষণা করতে পারেন এবং খেলার মধ্যে পরিবর্তনের বিষয়ে পছন্দ করতে পারেন৷
প্রতিটি সিনেটরের দলের প্রতিনিধিত্বকারী একটি স্ট্রিং দেওয়া হয়েছে৷ 'R' এবং 'D' চরিত্রটি যথাক্রমে রেডিয়েন্ট পার্টি এবং ডায়ার পার্টির প্রতিনিধিত্ব করে। তারপর n সেনেটর থাকলে, প্রদত্ত স্ট্রিংটির মাত্রা n হবে।
প্রদত্ত আদেশের মধ্যে প্রাথমিক সিনেটর থেকে শেষ সিনেটর পর্যন্ত রাউন্ড-ভিত্তিক পদ্ধতি শুরু হয়। এই পদ্ধতি চলবে ভোটের শীর্ষ পর্যন্ত। সমস্ত সিনেটর যারা তাদের অধিকার হারিয়েছেন তারা প্রক্রিয়া চলাকালীন এড়িয়ে যাবেন৷
৷ধরুন প্রতিটি সিনেটর যথেষ্ট বুদ্ধিমান এবং তার নিজের দলের জন্য সবচেয়ে সহজ কৌশলটি খেলতে পারেন, আপনি ভবিষ্যদ্বাণী করতে চান কোন দল শেষ পর্যন্ত বিজয় ঘোষণা করবে এবং Dota2 গেমের মধ্যে পরিবর্তন করবে। আউটপুট রেডিয়েন্ট বা ডায়ার হওয়া উচিত।
সুতরাং যদি ইনপুটটি "RDD" এর মতো হয় তবে এটি ডায়ার হবে। এর কারণ হল প্রথম সিনেটর রেডিয়েন্ট থেকে এসেছেন এবং তিনি শুধুমাত্র রাউন্ড 1-এ পরবর্তী সিনেটরের অধিকার নিষিদ্ধ করতে পারেন। এবং দ্বিতীয় সিনেটর আর কোনো অধিকার প্রয়োগ করতে পারবেন না যেহেতু তার অধিকার নিষিদ্ধ করা হয়েছে। এর পরে তৃতীয় সিনেটর ডায়ার থেকে আসে এবং তিনি রাউন্ড 1-এ প্রথম সিনেটরের অধিকার নিষিদ্ধ করতে পারেন। এখন রাউন্ড 2-এ, তৃতীয় সিনেটর কেবল বিজয় ঘোষণা করতে পারেন কারণ তিনিই সিনেটের একমাত্র লোক যিনি ভোট দিতে পারেন।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি কিউ q1, q2, n :=স্ট্রিংয়ের আকার তৈরি করুন। সমস্ত R-এর জন্য q1-এ সন্নিবেশ করান, এবং সমস্ত D-এর জন্য, q2-তে সন্নিবেশ করুন৷
৷ -
যখন উভয় সারি খালি নেই
-
যদি q1 এর সামনের উপাদান
-
q1 এ n সন্নিবেশ করান, q2 এবং q1 থেকে মুছুন
-
-
অন্যথায় q2 তে n ঢোকান, q2 এবং q1
থেকে মুছে দিন -
n 1 দ্বারা বৃদ্ধি করুন
-
-
যদি সারি খালি থাকে, তাহলে Dire ফেরত দিন, অন্যথায়, রেডিয়েন্ট ফেরত দিন
উদাহরণ(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
