ধরো, তোমাকে একটি Parenthesis Sequence এর স্ট্রিং দেওয়া হলো। এটা নিশ্চিত নয় যে ব্যালেন্সড। তোমাকে সিকোয়েন্সটিকে ব্যালেন্স করতে হবে সবচেয়ে কম সংখ্যাক অপারেশনে। একটি ধাপে তুমি এর উপর অথবা ফাংশন প্রয়োগ করতে পার।
এর প্রথম ভুক্তিটি সরিয়ে ফেল এবং এটিকে এর শেষে যুক্ত করে দাও।
এর শেষ ভুক্তিটি সরিয়ে ফেল এবং এটিকে এর শুরুতে যুক্ত করে দাও।
তুমি এই অপারেশনগুলো যতবার ইচ্ছে ব্যাবহার করতে পারবে। কিন্তু তোমার কাজ হলো ক্ষুদ্রতম সংখ্যাকবার ব্যাবহার করে সিকোয়েন্সটিকে ব্যালেন্স করা।
মনে রেখ, একটি Balanced Parenthesis নিম্নোক্ত দুইটি শর্ত মেনে চলেঃ
এর কোন যুগল করা সম্ভব নয় এমন ভুক্তি থাকবে না। অর্থাৎ প্রতি একটি এর জন্য পরবর্তিতে একটি পাওয়া যাবে।
যেকোন যুগলের দ্বারা আবদ্ধ Parenthesis Subset ব্যালেন্সড হবে।
ইনপুটের প্রথম লাইনে একটি পূর্ণসংখ্যা দেওয়া হবে যা মোট টেস্টকেসের সংখ্যা নির্দেশ করে। পরবর্তী সংখ্যাক লাইনের প্রতিটিতে একটি করে স্ট্রিং দেওয়া হবে। উল্লেখ্য হলো উপরোক্ত Parenthesis Sequence ।
For 10 points:
For 90 points:
প্রতি টেস্টকেসের জন্য প্রিন্ট করো "Case x: y" (কোটেশন চিহ্ন ছাড়া)। যদি ব্যালেন্স করা সম্ভব না হয় তাহলে প্রিন্ট করো “Case x: impossible” । এখানে হলো তুমি এখন কত নম্বর টেস্টকেসের উত্তর প্রিন্ট করছো, আর হলো ক্ষুদ্রতম কতগুলো অপারেশনে কে ব্যালেন্স করা সম্ভব সেই সংখ্যা।
Input | Output |
---|---|
3 )((()) )((())) ((())) | Case 1: 1 Case 2: impossible Case 3: 0 |