Senate Evacuation

Một đám cháy nhỏ bùng lên trong phòng thượng viện và mọi người phải sơ tán!

Mỗi thượng nghị sĩ trong phòng thuộc một trong \(N\) đảng chính trị, được đặt tên theo \(N\) chữ cái in hoa đầu tiên của bảng chữ cái tiếng Anh. Cửa thoát hiểm đủ rộng cho nhiều nhất hai người, nên mỗi bước bạn có thể đưa một hoặc hai thượng nghị sĩ ra ngoài.

Quy tắc thượng viện cho phép những người còn trong phòng bỏ phiếu cho bất kỳ dự luật nào vào bất kỳ lúc nào, kể cả giữa cuộc sơ tán. Vì vậy, sau mọi bước, không đảng nào được có đa số tuyệt đối: số người của một đảng không bao giờ được lớn hơn một nửa tổng số người còn lại.

Hãy xây dựng một kế hoạch sơ tán; thượng viện đang trông cậy vào bạn!

Dữ liệu vào

Dòng đầu chứa số test \(T\). Mỗi test gồm hai dòng. Dòng đầu chứa \(N\), số đảng. Dòng thứ hai chứa \(N\) số nguyên \(P_1,P_2,\ldots,P_N\), trong đó \(P_i\) là số thượng nghị sĩ của đảng mang chữ cái thứ \(i\).

Dữ liệu ra

Với mỗi test, in Case #x: y, trong đó x là số thứ tự test và y là kế hoạch sơ tán. Kế hoạch là danh sách chỉ dẫn cách nhau bởi dấu cách theo đúng thứ tự thực hiện; mỗi chỉ dẫn gồm một hoặc hai chữ cái, biểu diễn đảng của những người rời phòng ở bước đó.

Đề bảo đảm có ít nhất một kế hoạch hợp lệ. Nếu có nhiều kế hoạch, có thể in bất kỳ kế hoạch nào.

Ràng buộc

• \(1\le T\le50\).
• Trước khi sơ tán, không đảng nào có đa số tuyệt đối.
• \(1\le P_i\le1000\) với mọi \(i\).

Phân nhóm

• Small Dataset (Test Set 1, hiển thị): \(2\le N\le3\) và \(\sum_iP_i\le9\).
• Large Dataset (Test Set 2, ẩn): \(2\le N\le26\) và \(\sum_iP_i\le1000\).

Đ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
2 2
3
3 2 2
3
1 1 2
3
2 3 1

Case #1: AB BA
Case #2: AA BC C BA
Case #3: C C AB
Case #4: BA BB CA

Nguồn

Google Code Jam 2018, Vòng luyện tập, bài Senate Evacuation.

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