UVA 10324 - Zeros and one
প্রব্লেম ঃ প্রবলেমটাতে বলা হয়েছে আমাদের স্ট্রিং অথবা ক্যারেক্টার অ্যারে সাইজটা ১০০০০০০ হতে পারবে । স্ট্রিংটাতে শুধুমাত্র '০' এবং '১' ক্যারেক্টার থাকতে পারবে। মূলত আমাদের ক্যারেক্টার থেকে চেক করতে হবে মিনিমাম নাম্বার i এবং j এর মাজে min(i,j) এবং ম্যাক্সিমাম নাম্বার i এবং j এর মাজে
max (i,j) ।
সল্ভিং টেকনিক ঃ
এই প্রব্লেমটাতে টাইমের কথা চিন্তা করলে আমি ১. ৩১০ সেকেন্ডের আনতে পারি নাই। আরও ভালো সল্যুশন হয়তো সম্ভব । প্রথমে আমরা ধরে নেই সবগুলা ক্যারেক্টার একই অর্থাৎ আমরা একটা ফ্ল্যাগ নিতে পারি এবং ফ্ল্যাগের মান ০ দেই। তারপর আমরা লুপের মাধ্যমে চেক করি i থেকে j পর্যন্ত ক্যরেক্টার গুলো একই কিনা? যদি একই না হয় তাহলে আমরা ফ্ল্যাগের মান ১ করে দেই। এখন ফ্ল্যাগের মান যদি ১ হয় তাহলে প্রিন্ট করি No আর যদি ফ্ল্যাগের মান ০ ই থাকে তাহলে প্রিন্ট করি Yes ।
ওকে তাহলে কোডিং শুরু করে দেন সল্ভ করার জন্য ।
আমার কোড নিচে দেওয়া আছে। আমি সি++ এ প্রব্লেমটা সল্ভ করছি। একান্ত চেষ্টা করার পরই কোডটা দেখতে পারেন।
কোড ঃ
#include<bits/stdc++.h>
using namespace std;
int main()
{
string s;
int cnt=1;
while(cin>>s)
{
if(s.size()==0)
break;
int a,b,c,flag;
cin>>a;
cout<<"Case "<<cnt<<":"<<endl;
while(a--)
{
flag=0;
cin>>b>>c;
if(b>c)
swap(b,c);
for(int j=b+1;j<=c;j++)
{
if(s[b]!=s[j])
flag=1;
}
if(flag==0)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
cnt++;
}
return 0;
}