Bạn đang chơi một trò chơi điện tử và sẽ nhận được một thành tựu nếu hoàn thành tất cả các màn chơi liên tiếp mà không bị chết. Bạn có thể chơi các màn theo bất kỳ thứ tự nào, và mỗi lần chơi một màn, bạn sẽ hoàn thành nó hoặc bị chết. Mỗi màn chơi có một xác suất nhất định để bạn hoàn thành và tốn một khoảng thời gian cụ thể. Bạn nên chơi các màn theo thứ tự nào để thời gian kỳ vọng để đạt được thành tựu là nhỏ nhất? Giả sử rằng thời gian để vượt qua một màn chơi hoặc chết trong màn đó là như nhau, và bạn sẽ bắt đầu lại từ màn đầu tiên trong thứ tự đã chọn ngay khi bạn chết.

Lưu ý: Nếu bạn không hoàn thành được một màn chơi, cá nhân bạn không chết — chỉ có nhân vật của bạn trong trò chơi chết. Nếu không phải như vậy, chỉ có rất ít người cố gắng đạt được thành tựu này.

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 theo sau, mỗi bộ gồm ba dòng.

• Dòng đầu tiên của mỗi bộ test chứa một số nguyên duy nhất N, số lượng màn chơi.
• Dòng thứ hai chứa N số nguyên cách nhau bởi dấu cách \(L_i\). \(L_i\) là số giây mà màn chơi i kéo dài, thời gian này độc lập với việc bạn hoàn thành màn chơi hay bị chết.
• Dòng thứ ba chứa N số nguyên cách nhau bởi dấu cách \(P_i\). \(P_i\) là phần trăm khả năng bạn sẽ chết trong bất kỳ lần thử nào để hoàn thành màn chơi i.

Dữ liệu ra

Với mỗi bộ test, hãy xuất một dòng chứa "Case #x: ", trong đó x là số thứ tự bộ test (bắt đầu từ 1), tiếp theo là N số nguyên cách nhau bởi dấu cách. Số nguyên thứ j trong danh sách phải là chỉ số của màn chơi thứ j bạn nên thử vượt qua để giảm thiểu thời gian kỳ vọng đạt được thành tựu.

Các chỉ số đi từ 0 đến N-1. Nếu có nhiều thứ tự cho cùng một thời gian kỳ vọng, hãy xuất thứ tự nhỏ nhất về mặt từ điển. Trong hai thứ tự, thứ tự nhỏ hơn về mặt từ điển là thứ tự có chỉ số nhỏ hơn tại vị trí đầu tiên mà chúng khác nhau.

Ràng buộc

• 1 ≤ T ≤ 100.
• 0 ≤ \(P_i\) < 100.

Phân nhóm

• Nhóm test 1 (Visible Verdict):
• 1 ≤ N ≤ 20.
• \(L_i\) = 1.
• Nhóm test 2 (Hidden Verdict):
• 1 ≤ N ≤ 1000.
• 1 ≤ \(L_i\) ≤ 100.

Đ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
1 1 1 1
50 0 20 20
3
100 10 1
0 50 0
3
100 80 50
40 20 80

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

Nguồn

Google Code Jam 2012, Vòng 3, bài Perfect Game.

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