ডোটা-২-তে দুটি পার্টি আছে: রেডিয়েন্ট আর ডায়ার। সিনেটে উভয় পার্টির সিনেটর আছে। একটি পরিবর্তনের জন্য ভোটিং হবে যা রাউন্ড-ভিত্তিক। প্রতিটি রাউন্ডে প্রতিটি সিনেটর দুটি অধিকারের যেকোনো একটি ব্যালান্স করতে পারে:
- এক সিনেটরের অধিকার বাতিল করা — সে অন্য সিনেটরের সকল অধিকার এই ও পরের সব রাউন্ডের জন্য বাতিল করতে পারে।
- বিজয় ঘোষণা করা — যদি সে দেখে যে অধিকার বাঁচিয়ে থাকা সিনেটররা সব একই পার্টির, তবে সে বিজয় ঘোষণা করে গেমে পরিবর্তন আনতে পারে।
প্রতিটি সিনেটরের পার্টি বোঝানো একটি স্ট্রিং দেওয়া আছে। 'R' = রেডিয়েন্ট, 'D' = ডায়ার। n সিনেটর হলে স্ট্রিংয়ের দৈর্ঘ্য n। রাউন্ড-ভিত্তিক প্রক্রিয়া প্রথম সিনেটর থেকে শেষ পর্যন্ত চলে। অধিকার হারিয়ে যাওয়া সিনেটররা বাদ দিয়ে যাবে। প্রতিটি সিনেটর চতুর তাই নিজের পার্টির জন্য সেরা কৌশল খेলে। কোন পার্টি চূড়ান্ত বিজয় ঘোষণা করবে তা প্রিডিক্ট করুন। আউটপুট হবে "Radiant" বা "Dire"।
উদাহরণ: "RDD" হলে আউটপুট Dire। কারণ প্রথম সিনেটর রেডিয়েন্ট, সে পরের সিনেটরের অধিকার বাতিল করে। দ্বিতীয় সিনেটর আর কিছু করতে পারে না। তৃতীয় সিনেটর ডায়ার, সে প্রথম সিনেটরের অধিকার বাতিল করে। দ্বিতীয় রাউন্ডে শুধু তৃতীয় সিনেটর বাঁচে, সে বিজয় ঘোষণা করে।
সমাধানের ধাপগুলো:
- দুটি কিউ
q1, q2বানান,n := s.size()। সব 'R'-কেq1-এ, 'D'-কেq2-এ ঢোকান। - দুই কিউই খালি না হওয়া পর্যন্ত:
- যদি
q1.front() < q2.front():q1.push(n),q2.pop(),q1.pop()।
- অন্যথায়
q2.push(n),q2.pop(),q1.pop()। n++।
- যদি
q1খালি হলে "Dire", অন্যথায় "Radiant" ফেরত দিন।
উদাহরণ (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
