Tối ưu hóa số ngày để tìm một cookie bị nhiễm độc

Question

Một người bạn của tôi đã được hỏi câu hỏi này cho một cuộc phỏng vấn và không thể giải quyết nó tại thời điểm đó. Nghĩ rằng tôi sẽ chia sẻ như vậy.

Có một nghìn cookie choco-chip với một trong số chúng bị đầu độc. Bạn có quyền truy cập vào 10 con chuột trong phòng thí nghiệm mỗi ngày. Mỗi con chuột có thể nibble trên bất kỳ số lượng của cookie và mỗi cookie có thể được nibbled bởi bất kỳ số lượng của chuột. Sau một chuột nibbles trên một cookie bị nhiễm độc, phải mất một ngày để xem các hiệu ứng sau khi trên chuột nếu nó đã bị nhiễm độc.

Tối ưu hóa số ngày. Tôi đã có thể tìm ra một thuật toán để tìm cookie bị nhiễm độc trong 2 ngày, mặc dù tôi tin rằng tồn tại một cách để thực hiện điều này trong 1 ngày

Answer 1

Tôi nghĩ mình đã hiểu.

Hãy tưởng tượng cây nhị phân có 1024 cookie làm gốc (Số này chỉ xuất hiện rõ ràng hơn, nhưng điều này sẽ hoạt động với bất kỳ số nào nhỏ hơn 1024). Chia nhỏ 1024 cookie thành hai nhóm 512, mỗi nhóm trong số đó là con của thư mục gốc. Sau đó, chia từng nhóm 512 thành các nhóm 256 và để chúng là con của mỗi người và cứ thế. Bạn nên kết thúc với 11 cấp độ của cây.

Chỉ định mỗi chuột cho một cấp độ của cây ngoại trừ gốc. Mỗi con chuột sẽ chỉ ăn các cookie trên các nhánh bên trái của cấp độ của chúng. Ngày hôm sau, lặp đi lặp lại thông qua cây và cho mỗi con chuột đã chết, theo nhánh bên trái, cho mỗi con chuột sống, theo đúng nhánh. Cookie kết quả phải là cookie bị nhiễm độc.

Answer 2

Đây là "dễ dàng" giải pháp trong ba ngày:

• Thứ nhất, cho phép mỗi chuột gặm 100 cookie.
• Sau một ngày, cho phép mỗi con chuột nibble 10 cookie được ăn bởi chuột chết.
• Sau hai ngày, cho phép mỗi con chuột nibble một trong các cookie được ăn bởi con chuột chết thứ hai.
• Sau ba ngày, bạn sẽ biết cookie nào bị nhiễm độc.

Bây giờ cho các giải pháp "cứng" trong một ngày:

• Số tất cả các cookie trong nhị phân.
• Mỗi con chuột là để nibble trên những cookie mà đại diện nhị phân có một bit thiết lập tại chỉ số của chuột. Vì vậy, ví dụ chuột 1 sẽ nibble tất cả các số lẻ cookie.
• Đặt một cách khác, cookie 37 sẽ được nibbled bởi chuột 1, 3 và 6. Vì vậy, nếu những người chính xác ba con chuột chết ngày hôm sau, bạn biết rằng cookie 37 là một trong những đầu độc.