Bể bơi trẻ em là một chiếc bể lớn có thể chứa nước để trẻ nhỏ vui chơi.

Bạn có \(N\) nguồn nước khác nhau. Nguồn thứ \(i\) cung cấp nước với lưu lượng \(R_i\) và nhiệt độ \(C_i\). Ban đầu, tất cả nguồn nước đều tắt. Mỗi nguồn chỉ có thể được bật một lần và tắt một lần; thao tác bật hoặc tắt không tốn thêm thời gian. Nhiều nguồn có thể hoạt động đồng thời.

Bể có thể chứa vô hạn nước, nhưng bạn muốn đổ vào bể chính xác thể tích \(V\) với nhiệt độ chính xác \(X\) trong thời gian ngắn nhất. Nếu bật và tắt các nguồn một cách tối ưu (không nhất thiết phải dùng mọi nguồn), cần ít nhất bao nhiêu giây?

Trong bài này, khi trộn tức thời lượng nước có thể tích \(V_0\), nhiệt độ \(X_0\) với lượng nước có thể tích \(V_1\), nhiệt độ \(X_1\), ta thu được thể tích \(V_0+V_1\) và nhiệt độ

Ví dụ, trộn 5 lít nước ở 10 độ với 10 lít nước ở 40 độ sẽ cho 15 lít nước ở 30 độ. Cũng giả sử rằng nước không tự nóng lên hay nguội đi theo thời gian, trừ khi được trộn với nước khác.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng ba số cách nhau bởi dấu cách: số nguyên \(N\) và hai số thực \(V\), \(X\) như mô tả ở trên.

\(N\) dòng tiếp theo, mỗi dòng chứa hai số thực \(R_i\) và \(C_i\), lần lượt là lưu lượng và nhiệt độ của nguồn thứ \(i\). Thể tích được tính bằng lít, lưu lượng tính bằng lít mỗi giây và nhiệt độ tính bằng độ C.

Mọi số thực đều được biểu diễn chính xác với bốn chữ số sau dấu thập phân.

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ 1), còn \(y\) là số giây nhỏ nhất cần để đổ vào bể đúng thể tích và nhiệt độ yêu cầu. Nếu không thể thực hiện với dữ liệu đã cho, \(y\) phải là chuỗi IMPOSSIBLE.

\(y\) được coi là đúng nếu sai số tuyệt đối hoặc tương đối so với đáp án đúng không vượt quá \(10^{-6}\). Dấu chấm . được dùng làm dấu thập phân.

Ràng buộc

• \(1\le T\le100\).
• \(0.1\le X\le99.9\).
• \(0.1\le C_i\le99.9\).

Phân nhóm

• Tập nhỏ: \(1\le N\le2\); \(0.0001\le V\le100.0\); \(0.0001\le R_i\le100.0\).
• Tập lớn: \(1\le N\le100\); \(0.0001\le V\le10000.0\); \(0.0001\le R_i\le10000.0\).

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

6
1 10.0000 50.0000
0.2000 50.0000
2 30.0000 65.4321
0.0001 50.0000
100.0000 99.9000
2 5.0000 99.9000
30.0000 99.8999
20.0000 99.7000
2 0.0001 77.2831
0.0001 97.3911
0.0001 57.1751
2 100.0000 75.6127
70.0263 75.6127
27.0364 27.7990
4 5000.0000 75.0000
10.0000 30.0000
20.0000 50.0000
300.0000 95.0000
40.0000 2.0000

Case #1: 50.0000000
Case #2: 207221.843687375
Case #3: IMPOSSIBLE
Case #4: 0.500000000
Case #5: 1.428034895
Case #6: 18.975332068

Nguồn

Google Code Jam 2015, Vòng 2, bài Kiddie Pool.

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