প্রবলেম নাম্বার : http://bit.ly/1VqOsAJ
এই প্রব্লেম দিয়ে আমি আমার STL কন্টেইনার Queue এর ব্যবহার করা শুরু করেছি। সব STL Container তুলনা করলে আমার কাছে মনে হয় সব চেয়ে সহজ হচ্ছে Queue এর ব্যবহার।Queue এর ব্যসিক জানা না থাকলে এই লিংক থেকে আগে কিউয়ের ব্যসিক ক্লিয়ার করে আসলে ভালো হবে,বুজতেও সহজ হবে।প্রবলেম টি মোটামুটি সহজ কিন্তু কোড করতে জানলে সহজ,এটাকে আমি ভেক্টর দিয়েও করেছি তবে কিউ দিয়ে করলে ভালো।প্রব্লেম টি এরকম যে দুই জন সলজার আছে তারা কারড খেলবে ,প্রত্যেকের কাছে কত গুলো কারড আছে তা আগে থেকেই দেয়া থাকবে।আর প্রত্যের কারডের একটা মান দেয়া থাকবে।
তো আমরা ধরে নি যে প্রথম স্লজারের নাম হচ্ছে a আর অপর সলজারের নাম হচ্ছে b।
প্রবলেম ডিস্কাশনঃ এখন শুরুটা হবে এরকম , দুই সলজারের উভয়ের উপরের কারড এর উপর ডিপেন্ড করবে কে জয়ি।দুইজনের উপরে মানে Front এ যে কারড থাকবে সে দুইটা কারডের সাথে কম্পেয়ার করতে হবে যদি দেখা যায় প্রথম সলজারের মানে a এর কারড এর মান বড়, তাহলে সে তার অপজিট সলজারের b এর কারড নিয়ে সে নিজের নিকট নিয়ে নিবে।তবে এখানে নেয়ার ক্ষেত্রে যে সিস্টেম সেটাই একটু বড় ব্যপার,সেটা হচ্ছে যদি দেখা যায় a এর প্রথম কারড(যেহেতু আমাদের এই প্রবলেম ডিপেন্ড করবে উভয়ের উপরের কারড এর উপর) এর মান b এর প্রথম কারড থেকে বড় তাহলে প্রথমে a , b এর উপরের কারড তার একেবারে নিচে রাখবে এর পরে সে তার উপরে যে কারড ছিলো সেটা একেবারে নিচে রাখবে ,এভাবেই খেলা চলতে থাকবে।কোন এক সময় দেখা যাবে যে কোন এক জনের একটা কারডও থাকবে না শেষ পরযন্ত, তখন খেলা শেষ। আমাদের প্রিন্ট করতে হবে মোট কতবার এই ফাইট হয়েছে আর জয়ি কে হয়েছে।
সলুশনঃ যেহেতু এই প্রবলেম সল্ভ করার জন্য আমাদের কে এমন একটা কন্টেইনার ব্যবহার করতে হবে যা সারির একবারে উপরের টা নিয়েও কাজ করতে পারে(যেহেতু চেক করার পরে উভয়ের উপরেরটা আমরা মুছে যার উপরেরটা বড় তার নিচে নিচে রাখতে হবে) সাথে সাথে নিচের টা নিয়েও কাজ করতে পারে(যেহেতু উপরের টা এক এক করে আমরা যার বড় তার নিচে রাখবো),তাই আমরা এখানে STL এর Queue ব্যবহার করবো।queue এর সামনের দিক থেকে ডাটা এক্সট্র্যাক্ট করা হয়, আর ইনসার্ট করা হয় তার বিপরীত দিক থেকে।নিচের ছবির তদিকে লক্ষ্য করলে প্রব্লেমটি বুঝা অনেকটা সহজ হয়ে যাবে
এখানের Sample Input :
4 2 1 3 2 4 2
আর Sample Output :
6 2
4 হচ্ছে মোট কারডের সংখ্যা।এর পরের লাইন হচ্ছে a আর b এর কারড সংখ্যা আর এর মান। a এর কারডের মান হচ্ছে 1,3 আর b এর কারডের মান হচ্ছে 4,2।এখন আমরা যদি a আর b এর উপরের কারডের মান নিয়ে চিন্তা করি তাহলে দেখা যাবে a এর উপরে কারড=1 আর b এর উপরেটা =4 । মানে b এর টা বড়।এর মানে এখন b ,a এর উপরেটা টা প্রথমে তার নিচে পুশ করে এর পরে তার নিজের উপরেটা নিচে পুশ করবে যা ২ নাম্বার প্রসেসের মাধ্যমে বুঝানো হয়েছে।তাহলে এখন a এর কারড=3 আর b এর কারড = 2,1,4। সাথে সাথে আমরা ফাইট Count ও করবো,তাহলে এখন Count=1 । এর পরে আবার এভাবে চলবে এখন a এর উপরে যেটা আছে(বেচারার মাত্র একটাই আছে,তাই অইটাই ভাইয়ের উপর) তা b এর উপরে যে টা আছে (b এর উপরে আছে এখন 2) তার থেকে বড়।তাই এখন a ,b এর উপরেটা প্রথমে তার নিচে রাখবে (2 রাখবে) এর পরে a তার উপরেটাকে নিচে পাঠিয়ে দিবে(3 কে নিচে পাঠাবে)।তাহলে এখন count=2।এখন শেষ ধাপে চলে যাই যখন a এর কারড =2 আর b এর কারড=4,1,3 ।দেখা যাচ্ছে b এর উপরেটা বড় তাই a এর উপরেটা (2) সে টার নিচে পুশ করবে এর পরে তার নিজের উপরেটা ।তাহলে এখন a এর কারড=0। খেল খতম।b জয়ি আর কাউন্ট =6।আর একটা কথা while loop যতবার ঘুরবে ততবার বুজতে হবে ততবার ফাইত হয়েছে তাই লপের ভিতরে আমরা count++ করে দিবো।
কোড এর সলুশনঃ
মুল প্রসেস্টি তাহলে এভাবে হবে আমরা উভয়ের কারড কে দুইটা কিউতে পুশ করব তাই দুইটা কিউ ডিগলিয়ার করে দিবো
queue<LL int>c1,c2;
এর পরে কিউতে তাদের কারডের মান গুলো পুশ করবো
cin>>n1; for(i=0;i<n1;i++){ cin>>a; c1.push(a); }
cin>>n2; for(i=0;i<n2;i++){ cin>>b; c2.push(b); }
এর পরে একটা আমরা while loop চালাবো উভয় কিউয়ের সাইজের কন্ডিশনের উপরে,যদি দেখা যায় কখনো কোন একটা কিউ এর সাইজ 0 হবে এর মানে যে কোন এক জনের আর কোন কারড নেই।তার মানে খেলা শেষ, লুপ থেকে বাহির হয়ে যাবে আর কাউন্ট আর জয়ির নাম্বার প্রিন্ট করবে, এক নাম্বার হলে 1 এর দুইনাম্বার জন হলে 2।আর যদি দেখা যায় খেলা টি চলতেই আছে তাহলে বুজতে হবে খেলা ড্র প্রিন্ট করতে হবে -1।তবে -1 মানে খেলা ড্র যে হলো এটাবুঝার জন্য যে কন্ডিশন হবে তা আপনারা নিজেদের লজিক ব্যবহার করে বাহির করবেন,জিনিসটা ইজি কনচেপশন 🙂
while(cnt<=10000&&sz(c1)>0&&sz(c2)>0){ //sz(c1)==c1.size() cnt++; if(c1.front()>c2.front()){ c1.push(c2.front()); c1.push(c1.front()); c1.pop(); c2.pop(); } else if(c2.front()>c1.front()){ c2.push(c1.front()); c2.push(c2.front()); c1.pop(); c2.pop(); } }
while এর ভিতরে আমরা দুইজনের জন্য if else কন্ডিশন এপ্লাই করবো। if কন্ডিশনের মাধ্যমে আমরা উভয়ের front এ যে আছে তাদের মধ্যে বড় ছোট কম্পেয়ার করতেছি।এর পরে যে কন্ডিশনে মিলে যাবে সাথে সাথে অপজিশনেরটা সহ নিজেরটাও পুশ করবে।কিউ এর পুশ করার ক্ষেত্রে এটা নিচে নিচে মানকে পুশ করে।যেহেতু আমরা উভয়ের উপরের গুলোকে নিচে পাঠাচ্ছি তাহলে উভয়ের উপরে যা আছে সেগুলোকে ইরেজ বলেন ডিলিট বলেন তা করতে হবে,আর queue তে এটাকে pop দিয়ে সমাধান করা হয়।pop কাজ করে কিউ এর উপরের ইলিমেন্ট কে নিয়ে, প্রতিবার pop এর কারনে উভয় কিয় (মানে উভয় সলজারের) এর উপরের ইলিমেন্টকে সে কেটে দিবে আর পুশ এর মাধ্যমে সে ফ্রন্টে এ যে আছে তাকে নিচে পাঠিয়ে দিবে।
আশা করি while loop এর ভিতর থেকে বের হওয়ার পরে কে জয়ী হয়েছে সেটা বের করার জন্য কন্ডিশন কি দিবেন তা মাথায় এসে গেছে । সবার শেষে কন্ডিশনের লজিক হবে এভাবে if ধারা আমরা চেক করব কার queue এর সাইজ জিরো(0) ,যার সাইজ জিরো হবে size==0 , জয়ী হবে তার অপজিট সলজার বা এভাবেও দিতে পারেন যার কিউয়ের সাইজ জিরো না size!=0 বা এভাবেও হতে পারে সাইজের মান জিরো থেকে বড় size>0 সে হবে জয়ী।
আর ড্র হলে চেক করবেন এভাবে যেহেতু ড্র মানে লুপটি ইনফিনিট ভাবে চলচে থামবে না তাহলে ড্র এর জন্য while lop এ আপনি কাউন্ট এর যে আনুমানিক মান ধরেছেন যে বেশি হলে x বার ফাইট হতে পারে ।
তাহলে যদি দেখা যায় count এর মান x থেকে বড় বা তার সমান তাহলে বুজতে হবে লুপটি থামবে না খেলা ড্র ,প্রিন্ট করে দিবে -1;
if(cnt>=10000){ cout<<"-1"<<endl; } else{ cout<<cnt<<" "; if(sz(c1)>0){ cout<<"1"<<endl; } else if(sz(c2)>0){ cout<<"2"<<endl; } }
আশা করি আমার লেখার মাধ্যমে কিউয়ের বেসিক কিছুটা হলেও ক্লিয়ার হবে আপনাদের,আর কিছু না বুজলে আমাকে না জিজ্ঞাস করে যদি গুগল করেন তাহলে আপনার জন্য ভালো তাহলে শিখা টা বেশি হয়।আমি নিজেও যা শিখি তা গুগল করেই শিখি।আর শিখার জন্য http://www.cplusplus.com/ এই সাইট অনেক অপকারী।
জাবেদের হালখাতা :: JAVEDER HALKHATA 
সাম্প্রতিক মন্তব্যসমূহ