Giới thiệu

Cookie Clicker là một trò chơi Javascript của Orteil, nơi người chơi nhấp vào hình ảnh một chiếc bánh quy khổng lồ. Nhấp vào bánh quy sẽ giúp họ có thêm bánh quy. Họ có thể dùng số bánh quy đó để mua các tòa nhà. Những tòa nhà này giúp họ kiếm được nhiều bánh quy hơn nữa. Giống như bài toán này, trò chơi tập trung rất nhiều vào bánh quy. Bài toán này có ý tưởng tương tự, nhưng không yêu cầu bạn phải từng chơi Cookie Clicker. Làm ơn đừng đi chơi nó bây giờ: có thể sẽ rất lâu sau bạn mới quay lại được đấy.

Đề bài

Trong bài toán này, bạn bắt đầu với 0 bánh quy. Bạn nhận được bánh quy với tốc độ 2 chiếc mỗi giây bằng cách nhấp vào một chiếc bánh quy khổng lồ. Bất cứ khi nào bạn có ít nhất \(C\) bánh quy, bạn có thể mua một trang trại bánh quy (cookie farm). Mỗi khi bạn mua một trang trại, bạn tốn \(C\) bánh quy và nó giúp bạn tăng thêm \(F\) bánh quy mỗi giây.

Khi bạn có \(X\) bánh quy mà bạn chưa dùng để mua trang trại, bạn thắng! Hãy tính toán xem sẽ mất bao lâu để bạn thắng nếu bạn sử dụng chiến thuật tối ưu nhất.

Ví dụ

Giả sử \(C=500.0\), \(F=4.0\) và \(X=2000.0\). Đây là cách chiến thuật tối ưu diễn ra:

1. Bạn bắt đầu với 0 bánh quy, sản xuất 2 bánh quy mỗi giây.
2. Sau 250 giây, bạn sẽ có \(C=500\) bánh quy và có thể mua một trang trại sản xuất \(F=4\) bánh quy mỗi giây.
3. Sau khi mua trang trại, bạn có 0 bánh quy, và tổng tốc độ sản xuất bánh quy của bạn là 6 chiếc mỗi giây.
4. Trang trại tiếp theo sẽ tốn 500 bánh quy, bạn có thể mua sau khoảng 83.3333333 giây.
5. Sau khi mua trang trại thứ hai, bạn có 0 bánh quy, và tổng tốc độ sản xuất là 10 chiếc mỗi giây.
6. Một trang trại khác sẽ tốn 500 bánh quy, bạn có thể mua sau 50 giây.
7. Sau khi mua trang trại thứ ba, bạn có 0 bánh quy, và tổng tốc độ sản xuất là 14 chiếc mỗi giây.
8. Một trang trại nữa sẽ tốn 500 bánh quy, nhưng thực tế việc không mua nó lại hợp lý hơn: thay vào đó bạn chỉ cần đợi cho đến khi có \(X=2000\) bánh quy, mất khoảng 142.8571429 giây.

Tổng thời gian: 250 + 83.3333333 + 50 + 142.8571429 = 526.1904762 giây.

Lưu ý rằng bạn nhận được bánh quy liên tục: vì vậy 0.1 giây sau khi trò chơi bắt đầu, bạn sẽ có 0.2 bánh quy, và \(\pi\) giây sau khi bắt đầu, bạn sẽ có \(2\pi\) bánh quy.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ thử nghiệm, \(T\). \(T\) dòng tiếp theo. Mỗi dòng chứa ba số thực cách nhau bởi khoảng trắng: \(C\), \(F\) và \(X\), ý nghĩa của chúng đã được mô tả ở trên.

\(C\), \(F\) và \(X\) mỗi số sẽ bao gồm ít nhất 1 chữ số, theo sau là 1 dấu thập phân và từ 1 đến 5 chữ số sau dấu thập phân. Sẽ không có số 0 ở đầu.

Dữ liệu ra

Đối với mỗi bộ thử nghiệm, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ thử nghiệm (bắt đầu từ 1) và y là số giây tối thiểu để bạn có thể có \(X\) chiếc bánh quy ngon lành.

Chúng tôi khuyên bạn nên xuất y đến 7 chữ số thập phân, nhưng không bắt buộc. y sẽ được coi là chính xác nếu nó đủ gần với con số chính xác: trong phạm vi sai số tuyệt đối hoặc tương đối là \(10^{-6}\).

Ràng buộc

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

Phân nhóm

• Small dataset: \(1 \le C \le 500\); \(1 \le F \le 4\); \(1 \le X \le 2000\).
• Large dataset: \(1 \le C \le 10000\); \(1 \le F \le 100\); \(1 \le X \le 100000\).

Đ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ụ

4
30.0 1.0 2.0
30.0 2.0 100.0
30.50000 3.14159 1999.19990
500.0 4.0 2000.0

Case #1: 1.0000000
Case #2: 39.1666667
Case #3: 63.9680013
Case #4: 526.1904762

Nguồn

Google Code Jam 2014, Vòng loại, bài Cookie Clicker Alpha.

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