Light OJ - 1393 - Crazy Calendar Tutorial
Problem Description here
প্রবলেমঃ প্রব্লেমটিতে মূলত বলা হয়েছে একটি r * c গ্রীড দেয়া থাকবে। গ্রীডের প্রতিটি সেলে কিছু কয়েন থাকবে। দুইজন প্লেয়ার অপটিমালি খেলবে। প্রতি টার্নে একজন প্লেয়ার এক বা একাধিক কয়েন নিবে একটি সেল থেকে। নিয়ে ঠিক তার নিচের অথবা ডানের সেলে রাখবে। যখন সবগুলো কয়েন grid[r][c] তে পৌছাবে তখন খেলা শেষ। শেষ মুভ যে প্লেয়ার দিবে সে জিতবে। বলতে হবে প্রথম প্লেয়ার জিতেছে নাকি হেরেছে।
আইডিয়াঃ এটি মূলত একটি নিম গেইম। এখন, আমরা প্রব্লেমটিকে নিম্বল গেইমে রূপান্তর এর চেষ্টা করবো। নিম্বল গেইম সম্পর্কে না জানলে ক্লিক করুন।
নিম্বল গেইমে একটি 1*n গ্রীডের প্রতিটি সেলে কিছু কয়েন থাকে। সেল গুলোর ইনডেক্স যদি 0 to n-1 হয় তবে প্রতি চালে যেকোন ঘর থেকে একটি কয়েন নিয়ে বামের যেকোন ঘরে রাখা যায় যতোক্ষণ না সবগুলো কয়েন সর্ববামের ঘরে চলে যায়।
এই প্রব্লেমে আমি (i,j) সেল থেকে ডেস্টিনেশন সেল (r,c) তে যেতে পারি (r-i)+(c-j) সংখ্যক মুভ দিয়ে। খেয়াল করলে বুঝবে যে এই প্রব্লেমে আমি কয়েন এক বা একাধিক নিতে পারি আর মুভ এক ঘর ই দিতে পারি এক টার্নে। নিম্বল গেইমের ঠিক উল্টো! ওখানে ছিলো কয়েন একটি আর মুভ এক বা একাধিক ঘর।
এখন, নিম্বল গেইমে কনভার্ট করলে অর্থাৎ 1D গ্রীডে কনভার্ট করলে কেমন হবে? grid[i][j] হবে 1D grid এর ইনডেক্স। আর ওই ইনডেক্স এর ভ্যালু হিসেবে যোগ হবে (r-i)+(c-j)। মানে, কয়েনগুলোকে ইনডেক্স বানিয়ে ফেলেছি আর দরকারী মুভ সংখ্যা কে কয়েন -_-
বাকি অংশ আশাকরি চিন্তা করে ইমপ্লিমেন্ট করতে পারবে। না পারলে কোড দেখতে পারো।
Comments
Post a Comment