Có \(N\) thí sinh trong một chương trình truyền hình thực tế. Mỗi thí sinh được ban giám khảo cho một số điểm và nhận được bình chọn từ khán giả. Điểm số từ ban giám khảo và bình chọn từ khán giả được kết hợp để tạo thành điểm số cuối cùng cho thí sinh theo cách sau:

Gọi \(X\) là tổng điểm số mà ban giám khảo đã cho tất cả các thí sinh. Giả sử một thí sinh nhận được \(J\) điểm từ ban giám khảo và nhận được một tỉ lệ \(Y\) (từ 0 đến 1, bao gồm cả hai đầu) trong tổng số phiếu bầu của khán giả (\(Y\) có thể ví dụ là 0.3). Khi đó điểm số cuối cùng của thí sinh đó là \(J + X \times Y\). Lưu ý rằng tổng tỉ lệ bình chọn của khán giả cho tất cả các thí sinh phải bằng 1.

Thí sinh có điểm số thấp nhất sẽ bị loại.

Cho biết số điểm mà các thí sinh nhận được từ ban giám khảo, nhiệm vụ của bạn là tìm ra, đối với mỗi thí sinh, phần trăm bình chọn tối thiểu từ khán giả mà họ phải nhận được để đảm bảo không bị loại, bất kể số phiếu bầu còn lại của khán giả được phân phối như thế nào.

Nếu có nhiều thí sinh cùng có điểm số thấp nhất, sẽ không có thí sinh nào bị loại.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(T\). \(T\) bộ test tiếp theo, mỗi bộ trên một dòng. Mỗi dòng bắt đầu bằng một số nguyên \(N\), số lượng thí sinh, theo sau là một khoảng trắng, rồi đến \(N\) số nguyên \(s_0, s_1, \dots, s_{N-1}\), ngăn cách bởi các khoảng trắng đơn. Số nguyên \(s_i\) là điểm số được ban giám khảo chấm cho thí sinh \(i\).

Dữ liệu ra

Với mỗi bộ test, xuất ra một dòng chứa "Case #x: " theo sau là \(N\) số thực: \(m_i\). Giá trị x là số thứ tự bộ test (bắt đầu từ 1). Giá trị \(m_i\) là phần trăm bình chọn tối thiểu của khán giả cần thiết để thí sinh \(i\) chắc chắn tránh bị loại.

Các câu trả lời trong phạm vi sai số tuyệt đối hoặc tương đối \(10^{-5}\) so với đáp án đúng sẽ được chấp nhận.

Ràng buộc

• \(0 \le s_i \le 100\).
• \(s_i > 0\) cho ít nhất một giá trị \(i\). Điều này có nghĩa là ít nhất một thí sinh sẽ có điểm số từ ban giám khảo lớn hơn 0.

Phân nhóm

• Test set 1 (Visible):
• \(1 \le T \le 20\).
• \(2 \le N \le 10\).
• Test set 2 (Hidden):
• \(1 \le T \le 50\).
• \(2 \le N \le 200\).

Đ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
2 20 10
2 10 0
4 25 25 25 25
3 24 30 21

Case #1: 33.333333 66.666667
Case #2: 0.000000 100.000000
Case #3: 25.0 25.0 25.0 25.0
Case #4: 34.666667 26.666667 38.666667

Nguồn

Google Code Jam 2012, Vòng 1B, bài Safety in Numbers.

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