সমস্যা
একটি স্ট্রিং আছে 'x' (সিগন্যাল সোর্স) এবং 'o' (খালি) দিয়ে। সিগন্যাল উভয় দিকে প্রতি ইউনিট টাইমে এক 'o'-কে 'x'-এ রূপান্তর করে। পুরো স্ট্রিং 'x' হয়ে যাওয়ার টোটাল টাইম বের করুন।
অ্যালগরিদম
- স্ট্রিং স্ক্যান করে רצף 'o'-এর দৈর্ঘ্য মাপুন।
- প্রতিটি সেগমেন্টের জন্য:
- উভয় পাশে 'x' আছে → টাইম = ceil(len/2)
- এক পাশে 'x' আছে → টাইম = len
- কোনো পাশে 'x' নেই → টাইম = len (যদি শুধু 'o' থাকে, তবে সিগন্যাল আসে না, কিন্তু সমস্যা অনুমান করে সিগন্যাল আছে)।
- সব সেগমেন্টের ম্যাক্সিমাম টাইমই উত্তর।
C++ কোড
#include <bits/stdc++.h>
using namespace std;
int findMaximumDuration(string s, int n) {
int maxLen = 0;
s += '1'; // সেন্টিনেল
int cnt = 0;
for (int i=0; i<=n; i++) {
if (s[i] == 'o') cnt++;
else {
if (cnt > maxLen) {
int left = (i-cnt-1 >= 0 && s[i-cnt-1] == 'x') ? 1 : 0;
int right = (s[i] == 'x') ? 1 : 0;
int time = (left + right == 0) ? cnt : (cnt + left + right - 1) / (left + right);
maxLen = max(maxLen, time);
}
cnt = 0;
}
}
return maxLen;
}
int main() {
string str = "xooxoooxxoooxoooxooxooox";
cout << findMaximumDuration(str, str.size()); // 2
}
আউটপুট
2
