অনলাইন জাজ সিরিজ – ৮ (UVa 10783 – Odd Sum)

Post updated on 11th June, 2021 at 10:12 am

UVa online judge এর একটা সোজা সাপটা ডাল ভাত টাইপের প্রবলেম আজকে দেখব। আমি ধরেই নিচ্ছি আমার ব্লগের কোন পাঠক থেকে থাকলে তারা হয়ত একদম নতুনই হবে। তাই ডালভাত টাইপ প্রবলেম সলভ করার মধ্য দিয়ে confidence level বাড়ানোর একটা চেষ্টা নিচ্ছি। আজকের প্রবলেমটি হচ্ছেঃ

UVa 10783 – Odd Sum

 

উপরের লিংক থেকে প্রবলেমটা পড়ে ফেল। তুমি চাইলেও প্রবলেমে কী চাওয়া হয়েছে না বুঝে থাকতে পারবা না। a ও b দুটি পূর্ণ সংখ্যা ইনপুট দেয়া হবে। এদের মান খুব বেশি বড় হবে না। শূণ্য থেকে ১০০ এর মধ্যেই থাকবে। এটা বলেই দেয়া আছে প্রবলেমে। তাই long long int নেয়ার কোন দরকার নাই। আরেকটা কথা বলা আছে যে ইনপুট দেয়ার সময় a সব ক্ষেত্রে b এর চেয়ে ছোট বা সমান দেয়া হবে। আমাদেরকে বের করতে হবে a থেকে b এর মধ্যে যে সকল বিজোড় সংখ্যা আছে তাদের যোগফল।

খুব সোজা আর straight forward problem এটা। কোন প্যাচগোজ নাই। একটা লুপ ঘুরাবা a থেকে b পর্যন্ত। আর প্রতিক্ষেত্রে check করবা সেটা odd number কিনা। Odd number হলে সেটাকে যোগ করার কাজটা করবা।

for(i = a; i<=b; i++)
{
    if(i is an odd number)
        sum = sum + i;
}

একটা ছোট গিট্টু চিন্তা করি! যদি a এর মান b এর চেয়ে ছোট বা সমান হবে এই কথা বলা না থাকত তাহলে কী হত? ইনপুটে 1 5 দেয়া হলে সোজা হিসাব করে বের করে দিতে পারি আউটপুট হবে 9. কিন্তু যদি 0 ≤ a ≤ b ≤ 100 এই কথা বলা না থাকত তাহলে কিন্তু কোডটা সে হিসাবেই করতে হত যেন 1 5 অথবা 5 1 যেভাবেই দেয়া হোক না কেন উভয়ের জন্যেই যেন আউটপুট আসে 9. এটার জন্য একটা কাজ করা যেতে, লুপে ঢোকার আগেই চেক করে নিব যে a ছোট আর b বড় কিনা। যদি a এর মান বড় হয়ে যায় তাহলে a ও b এর মান অদল বদল করে দিব। a এর মান b তে আর b এর মান a-তে দিয়ে দিব। তাহলেই কিন্তু এই প্রবলেমের সলভ হয়। এই প্যারাটা এমনিতেই লিখা। এই প্রবলেমের জন্য দরকারি না। তবে অন্যান্য প্রবলেমে এই টাইপের ব্যাপার মাথায় রাখার দরকার হতে পারে।

তো সুন্দর মত Test Case দিয়ে ইনপুট নিয়ে প্রবলেমটা সলভ করে ফেল! অভিনন্দন এটা সলভ করে ফেলায়! এবার আসো একটু গবেষণা করি এই প্রবলেমটা নিয়েই!

ধর আমি প্রথম নাম্বারটা দিলাম ১ আর দ্বিতীয় নাম্বারটা দিলাম ৯৯। তাহলে উপরের কোড অনুযায়ী আমাদের রেজাল্ট পাওয়ার জন্য ৯৯ বার লুপ ঘুরার দরকার হবে। একটু চিন্তা কর। এটাকে কি কোন ভাবে কমানো যায়?

কি, পেলে কিছু? হুম, ঠিক ধরেছ! ১ থেকে ৯৯ পর্যন্ত তো ৯৯ টা বিজোড় সংখ্যা নাই। আছে এর অর্ধেক সংখ্যক! তার মানে কোডটা একটু এডিট করলেই এই লুপ ঘুরার সংখ্যা অর্ধেকে নামিয়ে আনা যায়! ভিতরে IF এর চেক করাও দরকার পরে না। আগের কোডের আউটপুট দিতে যদি ১ সেকেন্ড সময় লাগত তাহলে অবশ্যই নতুন কোডে আধা সেকেন্ডের মত লাগবে! আমরা loop variable এর মান প্রতিবার ১ করে না বাড়িয়ে কিন্তু তাহলে ২ করে বাড়াতে পারি। তাহলেই কিন্তু লুপের সংখ্যা অর্ধেক হয়ে যায়। i++ এর জায়গায় শুধু i = i+2 লিখলেই কিন্তু হবে না! ঘাপলা আছে আরো! আমাদের প্রবলেমে কিন্তু বলে দেয়া নাই যে ইনপুটগুলোও বিজোড় হবে। আমাদেরকে একটু confused করার জন্য সেটার মহোদয় স্যাম্পলে খুব সুন্দ্রী টাইপের ইনপুট দিয়েছেন। কিন্তু আমরা চেহারা দেখে গলে যাবার পাত্র নই! B| 😀

যদি প্রথম সংখ্যাটা 4 হয় তাহলে i = i + 2 করা হলে 4, 8, 10… এভাবে চলতে থাকবে। তাহলে কিন্তু বিজোড় সংখ্যা পাওয়া যাবে না। তাই লুপে ঢুকার আগে চেক করব a জোড় নাকি বিজোড়। যদি জোড় হয় তাহলে a = a + 1 করে দিব। এর ফলে a থেকে b এর রেঞ্জের মধ্যকার প্রথম বিজোড় সংখ্যাটাই কিন্তু a-তে assign হয়ে যাবে। এরপর এই কোড করলেই কাজ শেষঃ

if(a is even)
  a = a + 1;
//Now the value of a is obviously an odd number

for(i = a; i<=b; i=+2)
{
     sum = sum + i;
}

এইটুকু code optimization করার কারণে আমাদের program এর efficiency কিন্তু দ্বিগুণ বেড়ে গেল!

আচ্ছা, এর চেয়ে কি বেশি ইফিসিয়েন্ট কোন পদ্ধতি আছে? এটা হয়ত কোন একটা equation দিয়েও সমাধান করা সম্ভব। মাধ্যমিক বা উচ্চ মাধ্যমিকের গণিতে একটা সূত্র ছিল। কোন সমান্তর ধারার a থেকে b এর মধ্যকার সকল পদের যোগফল বের করার। ২-১ টা condition checking আর এক-দুইটা equation দিয়েই হয়ত এই প্রবলেম সলভ করা যাবে। টেস্ট কেস নেয়া ছাড়া কোন লুপই ঘুরানো লাগবে না। চেষ্টা করতে পার হাতে সময় থাকলে।

আজ এ পর্যন্তই। কোন কিছু বুঝতে সমস্যা হলে বা পরামর্শ থাকলে কমেন্ট করতে ভুলবে না যেন!

Happy Coding… 🙂