Kiểm tra dị ứng

Đề bài

Kelly bị dị ứng với đúng một trong số \(N\) loại thực phẩm, nhưng cô ấy không chắc là loại nào. Vì vậy, cô ấy quyết định thực hiện một số thí nghiệm để tìm ra loại thực phẩm đó.

Trong mỗi thí nghiệm, Kelly chọn một vài loại thực phẩm và ăn tất cả chúng. Cô ấy đợi \(A\) ngày để xem mình có phản ứng dị ứng nào không. Nếu không, cô ấy biết mình không bị dị ứng với bất kỳ loại thực phẩm nào đã ăn. Nếu có phản ứng, cô ấy phải đợi cho đến khi phản ứng đó biến mất: việc này mất tổng cộng \(B\) ngày (tính từ thời điểm cô ấy ăn thực phẩm).

Để đơn giản hóa việc thử nghiệm, Kelly quyết định đợi cho đến khi mỗi thí nghiệm kết thúc (sau \(A\) hoặc \(B\) ngày) trước khi bắt đầu thí nghiệm tiếp theo. Khi bắt đầu mỗi thí nghiệm, cô ấy có thể chọn nhóm thực phẩm muốn ăn dựa trên kết quả của các thí nghiệm trước đó.

Kelly chọn loại thực phẩm để ăn cho mỗi thí nghiệm sao cho tối thiểu hóa số ngày trong trường hợp xấu nhất trước khi cô ấy biết mình bị dị ứng với loại nào trong số \(N\) loại thực phẩm. Hỏi cô ấy mất bao lâu trong trường hợp xấu nhất?

Dữ liệu vào

Dòng đầu tiên của đầu vào cho biết số lượng bộ test, \(T\). \(T\) bộ test tiếp theo, mỗi bộ test nằm trên một dòng, chứa ba số nguyên cách nhau bởi dấu cách: \(N\), \(A\) và \(B\).

Dữ liệu ra

Với mỗi bộ test, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và \(y\) là số ngày Kelly cần để tìm ra loại thực phẩm mình bị dị ứng trong trường hợp xấu nhất.

Ràng buộc

• \(1 \le T \le 200\).

Phân nhóm

• Small dataset:

  • \(1 \le N \le 10^{15}\).
  • \(1 \le A \le B \le 100\).

  • Large dataset:

  • \(1 \le N \le 10^{15}\).

  • \(1 \le A \le B \le 10^{12}\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
4 5 7
8 1 1
1 23 32

Case #1: 12
Case #2: 3
Case #3: 0

Nguồn

Google Code Jam 2014, Chung kết thế giới, bài Allergy Testing.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.