মান লিজিয়ে, S নামক একটি স্ট্রিং আছে যাতে '0', '1' বা '?' ক্যারেক্টার রয়েছে। আমরা T স্ট্রিং বানাবো '?'-কে 0 বা 1 দিয়ে প্রতিস্থাপন করে। T-র আনব্যালেন্সডনেস হলো: সব l এবং r (0 <= l <= r < S-র আকার) এর জন্য l-থ থেকে r-থ ক্যারেক্টারের মধ্যে 0 এবং 1-এর সংখ্যার পার্থক্যের निरপেক্ষ মানের সর্বোচ্চ মান। আমাদের লক্ষ্য হলো T-র ন্যূনতম সম্ভাব্য আনব্যালেন্সডনেস বের করা।
যেমন, ইনপুট হলে S = "0??0", তবে আউটপুট হবে 2।
সমাধানের ধাপসমূহ
এই সমস্যাটি সমাধান করার জন্য নিচের ধাপগুলো অনুসরণ করব:
check() ফাংশন সংজ্ঞায়িত করুন, যা S, x গ্রহণ করবে: L := 0, R = x B := true i := 0 থেকে S-র আকার-১ পর্যন্ত: if S[i] == '0', তবে: L এবং R কে ১ করে কমিয়ে if S[i] == '1', তবে: L এবং R কে ১ করে বাড়িয়ে if S[i] == '?', তবে: if L == R, তবে: B := false (L ১ কমিয়ে) (R ১ বাড়িয়ে) if R == x + 1, তবে: if B নন-জিরো, তবে: R ১ কমিয়ে অন্যথায়: R := R - 2 if L < 0, তবে: if B নন-জিরো, তবে: L ১ বাড়িয়ে অন্যথায়: L := L + 2 if L > R, তবে: return false return true মূল ফাংশন থেকে: L := 1, R := 1000000 while L <= R: Mid := floor((L + R)/2) if check(S, Mid), তবে: R := Mid - 1 অন্যথায়: L := Mid + 1 return R + 1
উদাহরণ
নিচের ইমপ্লিমেন্টেশনটি দেখুন আরও ভালো বুঝতে:
#include <bits/stdc++.h> using namespace std; bool check(string S, int x) { int L = 0, R = x; bool B = true; for (int i = 0; i < S.size(); i++) { if (S[i] == '0') L--, R--; if (S[i] == '1') L++, R++; if (S[i] == '?') { if (L == R) B = false; L--; R++; } if (R == x + 1) { if (B) R--; else R -= 2; } if (L < 0) { if (B) L++; else L += 2; } if (L > R) return false; } return true; } int solve(string S) { int L = 1, R = 1000000; while (L <= R) { int Mid = L + R >> 1; if (check(S, Mid)) R = Mid - 1; else L = Mid + 1; } return R + 1; } int main() { string S = "0??0"; cout << solve(S) << endl; } ইনপুট
0??0
আউটপুট
2
