Một nhà vệ sinh có \(N+2\) buồng nằm trên một hàng; hai buồng ngoài cùng luôn bị nhân viên bảo vệ chiếm, còn \(N\) buồng ở giữa dành cho người dùng.

Mỗi người bước vào đều cố chọn buồng xa người khác nhất theo quy tắc tất định sau. Với mỗi buồng trống \(S\), họ tính \(L_S\) và \(R_S\): số buồng trống nằm giữa \(S\) và buồng có người gần nhất tương ứng về bên trái và bên phải. Trước tiên họ chỉ xét các buồng tối đa hóa \(\min(L_S,R_S)\). Nếu chỉ còn một buồng thì chọn nó; nếu vẫn hòa, họ tối đa hóa \(\max(L_S,R_S)\); nếu vẫn còn nhiều lựa chọn, họ chọn buồng ngoài cùng bên trái.

Có \(K\) người sắp vào, từng người chọn xong trước khi người tiếp theo xuất hiện, và không ai rời đi. Khi người cuối cùng chọn buồng \(S\), hãy tìm \(\max(L_S,R_S)\) và \(\min(L_S,R_S)\).

Dữ liệu vào

Dòng đầu chứa số test \(T\). Mỗi dòng trong \(T\) dòng tiếp theo chứa hai số nguyên \(N,K\) như mô tả trên.

Dữ liệu ra

Với mỗi test, in Case #x: y z, trong đó x là số thứ tự test bắt đầu từ 1, \(y=\max(L_S,R_S)\) và \(z=\min(L_S,R_S)\) đối với buồng \(S\) mà người cuối cùng chọn.

Ràng buộc

• \(1\le T\le100\).
• \(1\le K\le N\).

Phân nhóm

• Test Set 1 (Visible): \(1\le N\le1000\).
• Test Set 2 (Visible): \(1\le N\le10^6\).
• Test Set 3 (Hidden): \(1\le N\le10^{18}\).

Đ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ụ

5
4 2
5 2
6 2
1000 1000
1000 1

Case #1: 1 0
Case #2: 1 0
Case #3: 1 1
Case #4: 0 0
Case #5: 500 499

Nguồn

Google Code Jam 2017, Vòng loại, bài Bathroom Stalls.

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