Bathroom Stalls

Một nhà vệ sinh có \(N+2\) buồng trên một hàng. Hai buồng ngoài cùng bên trái và bên phải bị nhân viên bảo vệ chiếm vĩnh viễn; \(N\) buồng còn lại dành cho người dùng.

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

\(K\) người sắp lần lượt bước vào; mỗi người chọn xong trước khi người kế tiếp đến và không ai rời đi. Khi người cuối cùng chọn buồng \(S\), hai giá trị \(\max(L_S,R_S)\) và \(\min(L_S,R_S)\) bằng bao nhiêu?

Dữ liệu vào

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

Dữ liệu ra

Với mỗi test, in Case #x: y z, trong đó x là số thứ tự test, y là \(\max(L_S,R_S)\) và z là \(\min(L_S,R_S)\) mà người thứ \(K\) tính cho buồng đã chọn.

Ràng buộc

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

Phân nhóm

• Small Dataset 1 (Test Set 1, hiển thị): \(1\le N\le1000\).
• Small Dataset 2 (Test Set 2, hiển thị): \(1\le N\le10^6\).
• Large Dataset (Test Set 3, ẩn): \(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 2018, Vòng luyện tập, 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.