আসুন সলভ করি - হরতাল নিয়ে ইউ.ভি.এ এর প্রবলেম সেটার রেজাউল আলম চৌধুরী এর প্রবলেম

১৪ ই মার্চ, ২০১৩ সন্ধ্যা ৭:৩৬

প্রবলেমটা খুব ইজি কিন্তু মজা পেতে পারেন।



বিস্তারিততে না যেয়ে আমি সংক্ষেপে প্রবলেমটি বলছি।



প্রতিটি পার্টি একটি নির্দিষ্ট সংখ্যক দিন পর পর হরতাল দেয়। যেমন, ৩ দিন পর পর, ৪ দিন পর পর ইত্যাদি। এটাকে ডেনোট করছি h দিয়ে। ধরুন, ৩ টি পার্টি আছে যেখানে, h1 = 3, h2 = 4, and h3 = 8. অর্থাত প্রথম পার্টি হরতাল দেয় ৩ দিন পর পর, দ্বিতীয় পার্টি হরতাল দেয় ৪ দিন পর পর, আর তৃতীয় পার্টি হরতাল দেয় ৮ দিন পর পর। ১৪ টি দিনের মধ্যে এই ৩ পার্টি যদি তাদের নিয়মিত বিরতীতে হরতাল দেয় তাহলে ১৪ দিনের মধ্যে কতদিন হরতাল হয় তা ক্যালকুলেট করতে হবে। মনে রাখতে হবে, শুক্রবার আর শনিবারে হরতাল হলে সেটা গণনায় ধরা যাবে না। আর গণনা শুরু করতে হবে রবিবার থেকে। অর্থাত

১ম দিন - রবিবার

২য় দিন - সোমবার

... ... ...



এভাবে চলবে। যা্ই হোক, ১৪ দিনে ৩ টি পার্টি যদি ৩,৪,৮ বিরতীতে হরতাল দেয় তাহলে হরতালের ছক নিচের ছবির টেবিলের মতো হয়।



*********** ছবিটি বড় করে দেখতে ক্লিক করুন ***********







দেখা যাচ্ছে, ১ম পার্টি ১ম হরতাল দেয় ৩ তারিখে, তারপর প্রতি ৩ দিনের দিন হরতাল দিয়েছে। অর্থাত ৩,৬,৯,১২ তারিখে হরতায় দিয়েছে। ২য় পার্টির হরতাল শুরু হইছে ৪ তারিখ থেকে এবং তারপর থেকে প্রতি ৪ দিনের দিন হরতাল দিয়েছে, অর্থাত ৪,৮,১২ তারিখে হরতাল দেয়। আর ৩য় পার্টি হরতাল দেয়া শুরু করে ৮ তারিখে। যেহেতু এর ৮ দিন পরে তারিখ হয় ১৬ তারিখ যা ১৪ দিনের মধ্যে নয়, তাই তা দেখানো হয় নাই। দেখার বিষয় হচ্ছে,



৮ আর ১২ তারিখে যথাক্রমে ২য় ও ৩য় এবং ১ম ও ২য় পার্টির হরতাল কমন পড়েছে। কমন হরতালের ক্ষেত্রে সবগুলো মিলে ১ টি হরতাল হয়।



৬ তারিখের হরতাল নেওয়া হয় নাই কারণ ৬ তারিখ শুক্রবার।



যাই হোক, এই হচ্ছে প্রবলেম।



ইনপুট কিভাবে দেওয়া হবে সেটা নিয়ে আলোচনা না করে বলি যে কি কি ইনফো শুরুতেই দিবো,



১ম এ দেওয়া হবে কতগুলো দিনের মধ্যে গণনা হবে।

২য় এ দেওয়া হবে কতগুলো দল।

৩য় এ দেওয়া হবে প্রতিটি দলের হরতালের সিকোয়েন্স কমা সেপারেটেড হিসেবে।



স্যাম্পল ইনপুট: ১৪ ৩ ৩,৪,৮

আউটপুট: ৫



স্যাম্পল ইনপুট: ১০০ ৪ ১২,১৫,২৫,৪০

আউটপুট: ১৫



** ইনপুট যেভাবে খুশি নিয়েন।



এই লিংকে আমার করা সমাধান দেওয়া আছে। তবে আশা করি নিজে নিজে চেষ্টা করে দেখবেন আগে। জানি পেরে যাবেন। বাই চান্স না করে উঠতে পারলে আমার বা অন্যদের সল্যুশন স্টাডি করতে পারেন।



ক্লিক দিস লিংক : Solution - Problem from the book Programming Challenges : 1

২ টি +০/-০