Đề bài

Bạn vừa đến nhận việc bếp trưởng tại Nhà Bánh kếp Vô hạn và, như thường lệ, bắt gặp một thảm họa đang diễn ra! Các đầu bếp khác đã vô tình làm ra một số chiếc bánh kếp hình tròn khổng lồ, tất cả đều có cùng kích thước. Những chiếc bánh này quá lớn để phục vụ nguyên chiếc, nên họ đã bắt đầu chặt chúng thành các miếng (trong bài này, các miếng là những hình quạt tròn). Hiện tại, bạn có \(N\) miếng; miếng thứ \(i\) là một hình quạt có góc trong (góc ở tâm) bằng \(A_i\) nanođộ (một nanođộ bằng \(10^{-9}\) độ).

Có \(D\) thực khách đang chờ món. Mỗi thực khách muốn nhận đúng một miếng có cùng kích thước với miếng của mọi thực khách khác, nhưng họ không quan tâm kích thước đó cụ thể là bao nhiêu. Tuy nhiên, có thể không thực hiện được điều này bằng các miếng hiện có, nên bạn có thể cần thực hiện một hoặc nhiều nhát cắt theo bán kính.

Một nhát cắt biến một miếng hiện có với góc trong \(X\) thành hai miếng mới có góc trong \(Y\) và \(X-Y\). Bạn có thể làm vậy với bất kỳ \(0<Y<X\) nào, và các giá trị này không nhất thiết phải là số nguyên. Bạn có thể tiếp tục cắt một hoặc cả hai miếng mới này, rồi cứ thế tiếp tục.

Bạn được phép để thừa một hoặc nhiều miếng (với kích thước bất kỳ) mà không đưa cho thực khách; bạn có thể ăn chúng sau, vì thảm họa này đang khiến bạn lỡ mất bữa sáng của chính mình!

Hãy xác định tổng số nhát cắt ít nhất cần thực hiện để đáp ứng các thực khách.

Dữ liệu vào

Dòng đầu tiên chứa số bộ test \(T\). Tiếp theo là \(T\) bộ test. Mỗi bộ bắt đầu bằng một dòng chứa hai số nguyên \(N\) và \(D\): số miếng hiện có và số thực khách. Sau đó là một dòng nữa chứa \(N\) số nguyên \(A_1,A_2,\ldots,A_N\); số thứ \(i\) biểu diễn góc trong (tính bằng nanođộ) của miếng thứ \(i\).

Dữ liệu ra

Với mỗi bộ test, in một dòng chứa Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ \(1\)), còn y là số nhát cắt nhỏ nhất cần thực hiện như mô tả ở trên.

Ràng buộc

• \(1\le T\le100\).
• \(1\le A_i<360\times10^9\) với mọi \(i\).

Phân nhóm

Test Set 1 (Phán quyết hiển thị)

• \(1\le N\le300\).
• \(2\le D\le3\).

Test Set 2 (Phán quyết hiển thị)

• \(1\le N\le300\).
• \(2\le D\le50\).

Test Set 3 (Phán quyết ẩn)

• Với đúng \(21\) bộ test, \(9000\le N\le10000\).
• Với đúng \(T-21\) bộ test, \(1\le N\le1000\).
• \(2\le D\le50\).

Đ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
1 3
1
5 2
10 5 359999999999 123456789 10
2 3
8 4
3 2
1 2 3

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

Nguồn

Google Code Jam 2020, Vòng 1C, bài Oversized Pancake Choppers.

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