Có 1000 thùng nước, 1 thùng chứa thuốc độc. Heo uống thuốc độc sẽ chết sau 15 phút. Cần bao nhiêu heo tối thiểu để xác định thùng độc trong 1 giờ?
Bài toán tổng quát
Cho buckets thùng, heo chết sau minutesToDie phút, thời gian test minutesToTest phút. Tìm số heo tối thiểu.
Giải thích toán học
Mỗi heo có thể tham gia rounds = minutesToTest / minutesToDie vòng test. Với mỗi vòng, heo có thể sống hoặc chết → mỗi heo cung cấp (rounds + 1) trạng thái (chết ở vòng 1, 2, ..., rounds, hoặc sống hết).
Với p heo, tổng số trạng thái phân biệt được là (rounds + 1)^p. Cần số trạng thái này ≥ số thùng buckets.
→ Tìm p nhỏ nhất sao cho: (rounds + 1)^p ≥ buckets
Ví dụ
buckets = 1000, minutesToDie = 15, minutesToTest = 60
rounds = 60 / 15 = 4, mỗi heo có 5 trạng thái.
5^4 = 625 < 1000, 5^5 = 3125 ≥ 1000 → cần 5 heo.
Cài đặt C++
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
int ret = 0;
int rounds = minutesToTest / minutesToDie;
while (pow(rounds + 1, ret) < buckets) ret++;
return ret;
}
};
int main() {
Solution ob;
cout << ob.poorPigs(1000, 15, 60);
return 0;
}
Độ phức tạp
- Thời gian:
O(log buckets)— vòng lặp chạy tối đalog_{rounds+1}(buckets)lần. - Không gian:
O(1).
Input / Output
Input: 1000 15 60 Output: 5