Codeforces 158B(Taxi) Solution

আজকে আমি একটি  codeforces এর প্রবলেম নিয়ে আলোচনা করব।
প্রবলেম লিঙ্কঃ codeforces 158B
এখন প্রবলেমটি কিভাবে সমাধান করবে তা নিয়ে কিছু কথা।
প্রবলেমটি প্রথমে ভালভাবে পড়ার পর আমরা বুঝতে পারি যে,
কিছু সদস্য polycarpus এ জন্মদিন উদযাপন করার জন্য যাবে এবং ট্যাক্সিতে করে যাবে।
একটি ট্যাক্সিতে সর্বাধিক ৪ জন করে লোক উঠতে পারে।
এখানে কিছু কিছু সদস্যদের গ্রুপ আছে যেমন ১,২,৩,৪ মানে যারা উঠলে
একসাথে ট্যাক্সিতে উঠবে না হলে ৩ জন এর একটি গ্রুপ এর এমন হবে না যে
২ জনকে ১ট্যাক্সিতে বাকি ১ জন অন্য ট্যাক্সিতে;মানে গ্রুপ ভাগ করা যাবে না।
এইভাবে n সংখ্যক গ্রুপ থাকলে একসাথে নিয়ে যাওয়ার জন্য,
সর্বনিম্ন কয়টি ট্যাক্সি প্রয়োজন হবে?

ইনপুটঃ
প্রথম লাইনে থাকবে সদস্যদের কতটি গ্রুপ থাকবে।
দ্বিতীয় লাইনে থাকবে গ্রুপ এ কতজন করে সদস্য আছে।

আউটপুটঃ
সর্বনিম্ন কতটি ট্যাক্সি প্রয়োজন?

আইডিয়াঃ

সর্ব প্রথম আমরা চিন্তা করব কতভাবে ৪ বানান যায়।
১ম কেসঃ
৪জনের কতগুলো সদস্য আছে?
২য় কেসঃ
২জনের কতগুলো জোড়া আছে
৩য় কেসঃ
৩জনের কতগুলো সদস্য আছে এবং তাদের সংখ্যা ১ জনের সদস্য সংখ্যার চেয়ে বেশি কিনা?
যদি বেশি হয় বা কম হয় ওইটার উপর ভিত্তি করে আর ২টি কেস হবে
সবার শেষে আমরা চিন্তা করব এমন ৩, ৩, ২, ৩ অথবা ১, ১, ২ , ১মানে  যেগুলো একদম ৪ হয় না বা হলেও আমরা আগে চিন্তা করি নাই ।

সমাধান প্রক্রিয়াঃ
ভ্যারিয়াবল ডিকলেয়ার করা হল।সবাইকে শুরুতে ০ ধরে নিব।
c1 এ ১ সদস্য এর যতগুলো গ্রুপ আছে,তাদের রাখব।
c2,c3,c4 এইভাবে রাখব।
টোটাল sum হবে আমাদের আউটপুট।

int c1= 0, c2 = 0, c3=0, c4 = 0;
int sum = 0;

ইনপুট সংখ্যা হল  n,তাই আমরা n বার লুপ চালাব।
আর ১, ২, ৩ বা ৪ যে সদস্য এর গ্রুপ আমাদের ইনপুটে  আছে তার সংখ্যা  এক করে বাড়াব;
মানে ১ এর জন্যে c1, ২ এর জন্যে c2, বাড়াব এই ভাবে।

for(int i = 0, a; i <n; i++)
{
cin>>a;
        if(a==1)c1++;
        else if(a == 2)c2++;
        else if(a == 3)c3++;
        else c4++;
}
১ম কেসঃ
এখন আমাদের কাজ ১ম কেস  এর মানে ৪ কত গুলা আছে।
 এটা ত খুব সহজ, আমরা c4 দিয়ে ত ওইটাই বের করলাম নাকি যে ৪ জন এর কতগুলো গ্রুপ আছে।
তাহলে আমরা শুধু sum এর সাথে c4 যোগ করে দিব আর c4 এর মান ০ করে দিব;
কারন sum নেওয়ার পর আমাদের ৪ জন এর আর কোন গ্রুপ বাকি নেই।
যাতে পরে ঝামেলা না হয় তাই c4 নিয়েছি সেই জন্যে।
sum = sum+c4;
 c4 = 0;

২য় কেসঃ
এখন আসি আমাদের ২ জন এর কতগুলো গ্রুপ আছে।
এখন কথা হল দেখ, c2 এর মান জোড় অথবা বিজোড় হবে।
জোড় হলে হিসাব সহজ।আমরা শুধু c2 কে ২ দিয়ে ভাগ করে c2 তে ০ রেখে দিব;
কিন্তু যদি বিজোড় হয় মানে ধর c2 = ৫ এর মানে টোটাল ৫ টি গ্রুপ
আছে যেখানে প্রতি গ্রুপে ২ জন করে মানুষ আছে তাহলে ৪ টি গ্রুপকে
আমি ২ টি ট্যাক্সিতে করে রাখতে পারি মিনিমাম কিন্তু ১টি ২ সদস্যের গ্রুপ বাদ চলে যাবে;
মানে sum এর মান ২ বাড়িয়ে আমরা c2 এর মান ১ রেখে দিতে পারি যাতে বুঝা যায় যে এটা
আমরা বাকি রেখে দিয়েছি পরে হিসাব করে নিব। মানে এমন হতে পারে পরে আমরা ২টি  ১ সদস্যের গ্রুপ পেলাম।
তাহলে আমরা ২ + ১ + ১ মানে ৪ জন কে এক ট্যাক্সি তে করে পাঠাতে পারব।
আশা করি জোড় বিজোড় এর কেস২ টি বুঝতে পেরেছ।.

sum = sum + c2/2;
c2 = c2%2;//c2 = 0 or 1 now

c2 তে এখন মান ২  বা ১ আছে যা ইনপুট এর উপর নির্ভরশীল।.
৩য় কেসঃ
এখন পরের কেসে c1 এর মান c2 এর মানের চেয়ে ছোট না বড় তার উপর ভিত্তি করে ২ টি কেস করতে হবে।
যদি c1 এর মান c3 এর চেয়ে বড় বা সমান হয় ।
যেমনঃ ১,১,১,৩,৩ এমন হয় তাহলে আমরা ৩ আর ১ এর ২ টি করে গ্রুপ তৈরি করতে পারি।
if(c1>=c3)
{
        sum = sum + c3;//মানে c3 এর প্রত্যেকটি গ্রুপের জন্য ১ জনের গ্রুপ পেয়ে গেছি।
        c1 = c1 - c3;//কিছু সংখ্যক ১ জনের গ্রুপ বাদ রয়ে যাবে, সেগুলো c1 এর ভিতর রেখে দিলাম।
        c3 = 0;//যেহেতু ৩ জনের আর কোনও গ্রুপ বাকি নাই,তাই c3=০
        sum = sum + c1/4;//১,১,১,১,১ এখানে আমরা ৪ জনকে আমরা একটি ট্যাক্সিতে পাঠাব।
        c1 = c1%4;//উপরের লাইনের বাকি ১ কে c1 এ রাখব এবং c1 এর ভ্যালু ০ থেকে ৩ পর্যন্ত যে কোনটাই হতে পারে।
//কিন্তু ৪ বা তার বেশি হতে পারে না।
        if(c1 + c2*2 <=4 && c1 + c2*2 >0)
{ //উপরের কেস ২ এর শেষ লাইনে দেখ,
//ঐ কেসটি এখানে লিখা হয়েছে। ১+১+২=৪ এই ক্ষেত্রে আমরা একটি এক্সট্রা ট্যাক্সি দিয়ে চলিয়ে দিতে পারছি।তাই sum ১ বাড়িয়েছি।
            sum++;
            c1 = 0;
            c2 = 0;
}

else if(c1 == 3 && c2 == 1)
{//১, ১, ১, ২ - এভাবে ৩ টি ১ থাকলে এবং ১ টি ২ থাকলে কিন্তু এক ট্যাক্সিতে ধরবে না,২টি ট্যাক্সি লাগবে।তাই sum ২ বাড়িয়েছি।
// আমরা বড় মানগুলো কেন চিন্তা করলাম না মানে c1 কি ৩ এর বেশি হতে পারে না?? c2 কি ২ বা তার বেশি হতে পারে না ?
//c1 এর ভ্যালুতে কেন ৩ এর বেশি হতে পারে না আর c2 এর ভ্যালুতে কেন ১ এর বেশি হতে পারে না,সেটা আগেই বলা হয়েছে।
sum = sum + 2;
        c1 = 0;
        c2 = 0;
        }
}

এখন যদি উল্টো কেস হয় মানে c1 থেকে c3 বড় (  ১, ১, ৩, ৩, ৩  )  হয়;
তাহলে আমরা আগের মতই  একটি ৩ আর একটি ১ এর ম্যাক্সিমাম কতগুলো গ্রুপ হয় তা বের করে sum এর শাথে যোগ করে দিব
else if(c1<c3)
{
        sum = sum + c1;
        c3 = c3 - c1;
        c1 = 0;
        sum = sum + c3 + c2;
//c3 এর ভ্যালু ২ এর চেয়ে বড় যে কোনটাই হতে পারে; কিন্তু c2 এর ভ্যালু ম্যাক্সিমাম ১ হতে পারে।
//মানে এখন শুধু পসিবল ৩,৩,২ বা ৩,৩,৩,২ বা ৩,৩ এই কেসগুলো
//আর সবগুলাতেই দেখ যত গ্রুপ ৪ জন করে হয় ততগুলো ট্যাক্সি লাগবে মানে ৩,৩,২ এ ৩টি ট্যাক্সি;
//৩,৩,৩,২  এ ৪টি ট্যাক্সি তাই c3 আর c2 যোগ করলেই কাজ শেষ।
//১ আর ২ এর জন্য কোনও কেস না থাকায় এখানে হিসাব কম।  
}
cout<<sum;
sum প্রিন্ট করে দিব।
আশা করি সবাই বুঝতে পেরেছ।
এখন প্রবলেম লিঙ্ক এ যেয়ে নিজে কোড টি সাবমিট করে দেখতে পার।
খুব বেশী প্রয়োজন না পড়লে  solution দেখবে না।