Để giải quyết dứt điểm câu hỏi muôn thuở rằng ngôn ngữ lập trình nào là tốt nhất, bạn hỏi tổng cộng \(N\) người về ngôn ngữ yêu thích của họ. Đây là câu hỏi mở: mỗi người được tự do nêu bất kỳ ngôn ngữ nào, và trên thế giới có vô hạn ngôn ngữ.

Một số người đã trả lời, và bạn đã tổng hợp thông tin thành một danh sách số lượng. Chẳng hạn, 1 2 có nghĩa là cho đến lúc này bạn đã hỏi 3 người: một người chọn một ngôn ngữ nào đó, còn hai người kia chọn một ngôn ngữ khác.

Bạn định công bố kết quả dưới dạng bảng liệt kê từng ngôn ngữ và tỷ lệ phần trăm số người chọn nó. Mỗi tỷ lệ được làm tròn tới số nguyên gần nhất; nếu phần thập phân lớn hơn hoặc bằng 0,5 thì làm tròn lên. Ví dụ, 12,5% được làm tròn thành 13%, 99,5% thành 100%, còn 12,4999% thành 12%.

Trong những khảo sát như vậy, đôi khi tổng các tỷ lệ đã làm tròn không đúng bằng 100. Sau khi bạn khảo sát xong những người còn lại, tổng lớn nhất có thể của các tỷ lệ đã làm tròn là bao nhiêu?

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\).

Mỗi bộ test gồm hai dòng. Dòng đầu chứa hai số nguyên \(N\) và \(L\): tổng số người trong khảo sát và số ngôn ngữ khác nhau đã xuất hiện trong câu trả lời của những người đã trả lời. Dòng thứ hai chứa \(L\) số nguyên \(C_i\); số thứ \(i\) là số người đã chọn ngôn ngữ thứ \(i\) trong số các ngôn ngữ đã xuất hiện.

Dữ liệu ra

Với mỗi bộ test, in một dòng có dạng Case #x: y, trong đó \(x\) là số thứ tự bộ test, bắt đầu từ 1, và \(y\) là tổng lớn nhất có thể của các tỷ lệ phần trăm đã làm tròn như mô tả trên.

Ràng buộc

• \(1 \le T \le 100\).
• \(1 \le L < N\).
• \(1 \le C_i\) với mọi \(i\).
• \(\sum_i C_i < N\).

Phân nhóm

• Test Set 1 (Hiển thị): \(2 \le N \le 25\).
• Test Set 2 (Hiển thị): \(2 \le N \le 250\).
• Test Set 3 (Ẩn): \(2 \le N \le 10^5\).

Đ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
3 2
1 1
10 3
1 3 2
6 2
3 1
9 8
1 1 1 1 1 1 1 1

Case #1: 100
Case #2: 100
Case #3: 101
Case #4: 99

Nguồn

Google Code Jam 2018, Vòng 1B, bài Rounding Error.

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