หมูทดสอบพิษใน C++ (Poor Pigs)

ภาพรวมปัญหา

มีถังทั้งหมด buckets ถัง มีเพียง 1 ถังที่มีพิษ หากหมูดื่มพิษจะตายภายใน minutesToDie นาที ต้องการหาถังพิษภายใน minutesToTest นาที ต้องใช้หมูขั้นต่ำกี่ตัว?

ตัวอย่าง

buckets = 1000, minutesToDie = 15, minutesToTest = 60 → Output: 5

หลักการแก้ปัญหา

แต่ละหมูสามารถทดสอบได้หลายรอบ จำนวนรอบ = minutesToTest / minutesToDie
แต่ละหมูมีสถานะที่เป็นไปได้ = รอบ + 1 สถานะ (ตายที่รอบไหน หรือไม่ตายเลย)
ดังนั้น pigs ตัวสามารถแยกแยะได้ (states)^pigs ถัง

หา pigs น้อยที่สุดที่ทำให้: (minutesToTest / minutesToDie + 1)^pigs >= buckets

โค้ด 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));
}

การวิเคราะห์

• เวลา: O(log buckets) — วนลูปเพิ่ม ret จนกว่าเงื่อนไขจะเป็นจริง
• พื้นที่: O(1)

อธิบายตัวอย่าง

minutesToTest = 60, minutesToDie = 15 → รอบ = 4
สถานะต่อหมู = 5 (ตายรอบ 1,2,3,4 หรือไม่ตาย)
5^4 = 625 < 1000
5^5 = 3125 ≥ 1000 → ต้องใช้ 5 ตัว