Join the Ranks

Đề bài

Gần đây, bạn có một bộ bài mới. Mỗi lá mang một hạng, là số nguyên từ 1 đến \(R\), và một chất, là số nguyên từ 1 đến \(S\). Với mỗi cặp hạng và chất có đúng một lá bài, nên bộ bài có tổng cộng \(R \times S\) lá. Ta ký hiệu lá bài hạng \(r\), chất \(s\) là \((r,s)\).

Vì còn mới, bộ bài được xếp từ trên xuống dưới theo chất tăng dần; nếu cùng chất thì theo hạng tăng dần. Cụ thể: \((1,1)\), \((2,1)\), ..., \((R,1)\), rồi \((1,2)\), \((2,2)\), ..., \((R,2)\), và cứ thế đến \((R,S)\). Ví dụ, với \(R=4\), \(S=2\), thứ tự ban đầu là \((1,1),(2,1),(3,1),(4,1),(1,2),(2,2),(3,2),(4,2)\).

Bạn muốn sắp xếp lại bộ bài theo hạng: đặt mọi lá cùng hạng cạnh nhau và các hạng theo thứ tự tăng dần. Bạn không quan tâm thứ tự các chất trong mỗi hạng. Chẳng hạn, với \(R=4\), \(S=2\), một thứ tự mới hợp lệ là \((1,2),(1,1),(2,1),(2,2),(3,1),(3,2),(4,2),(4,1)\).

Bạn đang học nấu ăn nên muốn sắp xếp bộ bài mà không đặt những chiếc xẻng lật xuống. Bạn quyết định chỉ dùng thao tác nhiều bước sau:

• Lấy một hoặc nhiều lá trên cùng, đặt riêng thành chồng A.
• Lấy một hoặc nhiều lá từ vị trí trên cùng mới, đặt riêng thành chồng B.
• Đặt chồng A lên bộ bài, rồi đặt chồng B lên trên bộ bài mới.

Thao tác hoán đổi phần A và B mà không ảnh hưởng các lá nằm sâu hơn trong bộ bài (nếu có).

Tiếp tục ví dụ \(R=4\), \(S=2\): nếu nước đầu chọn 3 lá cho A và 2 lá cho B, ta có:
A: \((1,1),(2,1),(3,1)\),
B: \((4,1),(1,2)\), và
Phần còn lại: \((2,2),(3,2),(4,2)\).
Sau khi đặt A lên bộ bài rồi B lên A, thứ tự mới là \((4,1),(1,2),(1,1),(2,1),(3,1),(2,2),(3,2),(4,2)\).

Cho \(R\) và \(S\), hãy tìm một dãy thao tác sắp xếp bộ bài theo hạng như trên với số thao tác ít nhất có thể.

Dữ liệu vào

Dòng đầu là số bộ test \(T\). Mỗi dòng trong \(T\) dòng tiếp theo chứa hai số nguyên \(R,S\), lần lượt là số hạng và số chất.

Dữ liệu ra

Với mỗi bộ test, in Case #x: y, trong đó x là số thứ tự bộ test (từ 1), còn y là số thao tác tối thiểu. Sau đó in thêm y dòng a_i b_i: ở thao tác thứ \(i\), lấy trước \(a_i\) lá làm A rồi lấy \(b_i\) lá tiếp theo làm B.

Ràng buộc

Phân nhóm

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

• \(T=12\).
• \(2 \le R \le 5\).
• \(2 \le S \le 7\).
• \(R \times S \le 14\).

Test Set 2 (phán quyết ẩn)

• \(1 \le T \le 100\).
• \(2 \le R \le 40\).
• \(2 \le S \le 40\).

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

3
2 2
3 2
2 3

Case #1: 1
2 1
Case #2: 2
3 2
2 1
Case #3: 2
2 3
2 2

Nguồn

Google Code Jam 2020, Vòng 1B, bài Join the Ranks.

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