C++-এ পুয়র পিগস (Poor Pigs) সমস্যা

পুয়র পিগস সমস্যা

ধরুন ১০০০টি বালতি আছে, 그중 একটি বিষাক্ত। একজন শূকর বিষ পান করলে ১৫ মিনিটের মধ্যে মারা যায়। ১ ঘণ্টা (৬০ মিনিট) içinde বিষাক্ত বালটিটি শনাক্ত করতে কমপক্ষে কতজন শূকর দরকার?

সাধারণীকরণ: nটি বালতি, বিষাক্ত পান করলে m মিনিটে মৃত্যু, p মিনিটের সময় দেওয়া আছে। ঠিক একটি বালতি বিষাক্ত।

n=1000, m=15, p=60 হলে উত্তর: ৫

সমাধানের পদ্ধতি

এই সমস্যাটি একটি ভিত্তি-(p/m + 1) সংখ্যা পদ্ধতিতে সমাধান করা যায়। প্রতিটি শূকর (p/m + 1)টি অবস্থা দিতে পারে (মারা যাওয়ার সময় অনুযায়ী)।

• ret := 0
• while (minutesToTest / minutesToDie + 1)^ret < buckets:
  • ret++
• ret ফেরত দিন

C++ কোড উদাহরণ

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        int ret = 0;
        while(pow((minutesToTest / minutesToDie + 1), ret) < buckets) ret++;
        return ret;
    }
};

int main() {
    Solution ob;
    cout << (ob.poorPigs(1000, 15, 60));
    return 0;
}

ইনপুট

1000 15 60

আউটপুট

5