Many Prizes

Đề bài

Chúng ta sẽ tổ chức một giải đấu với \(2^N\) đội, và trao \(P\) giải thưởng giống hệt nhau cho các đội có thứ hạng từ \(0\) đến \(P-1\).

Các đội được đánh số từ \(0\) đến \(2^N-1\). Khi đội \(i\) và đội \(j\) đối đầu với nhau trong một trận đấu, đội \(i\) sẽ thắng nếu và chỉ nếu \(i < j\).

Các đội trong giải đấu được sắp xếp theo một thứ tự nhất định, gọi là danh sách giải đấu, chứa tất cả \(2^N\) đội. Danh sách giải đấu này sẽ ảnh hưởng đến việc đội nào gặp đội nào và theo thứ tự nào.

Nhiệm vụ của bạn là tìm số hiệu đội lớn nhất chắc chắn giành được giải thưởng, bất kể danh sách giải đấu được sắp xếp như thế nào; và tìm số hiệu đội lớn nhất có thể giành được giải thưởng, tùy thuộc vào cách sắp xếp danh sách giải đấu.

Thể thức giải đấu

Giải đấu được tiến hành trong \(N\) vòng.

Mỗi đội có một thành tích: danh sách kết quả các trận đấu mà đội đó đã chơi cho đến nay. Ví dụ, nếu một đội đã chơi ba trận, thắng trận đầu, thua trận thứ hai và thắng trận thứ ba, thành tích của đội đó là [W, L, W]. Nếu một đội chưa chơi trận nào, thành tích là [].

Trong mỗi vòng, mọi đội đều đấu một trận với một đội khác có cùng thành tích. Đội đầu tiên trong danh sách giải đấu có một thành tích cụ thể sẽ đấu với đội thứ hai có cùng thành tích đó; đội thứ ba có cùng thành tích sẽ đấu với đội thứ tư; và cứ tiếp tục như vậy.

Sau \(N\) vòng, mỗi đội sẽ có một thành tích khác nhau. Các đội được xếp hạng theo thứ tự từ điển đảo ngược của thành tích; vì vậy [W, W, W] > [W, W, L] > [W, L, W] ... > [L, L, L].

Dưới đây là ví dụ về một giải đấu với \(N=3\), và danh sách giải đấu là [2, 4, 5, 3, 6, 7, 1, 0], trong đó các cột đại diện cho các vòng đấu khác nhau và các đội được nhóm theo thành tích của họ. Đội thắng trong mỗi trận đấu được đánh dấu bằng dấu *.

Round 1    Round 2    Round 3    Final Result
                                 (best rank at top)
[]         [W]        [W,W]
2  *       2  *       2          0  [W,W,W]
4          3          0  *       2  [W,W,L]
                      [W,L]
5          6          3  *       3  [W,L,W]
3  *       0  *       6          6  [W,L,L]
           [L]        [L,W]
6  *       4  *       4          1  [L,W,W]
7          5          1  *       4  [L,W,L]
                      [L,L]
1          7          5  *       5  [L,L,W]
0  *       1  *       7          7  [L,L,L]

Nếu chúng ta trao 4 giải thưởng (\(N=3, P=4\)), các giải thưởng sẽ thuộc về các đội 0, 2, 3 và 6.

Số hiệu đội lớn nhất chắc chắn giành giải với \(N=3, P=4\), bất kể thứ tự danh sách giải đấu, là đội 0: danh sách giải đấu ví dụ trên cho thấy đội 1 có thể không giành được giải, và thực tế là đội 0 sẽ luôn giành được giải cho dù danh sách giải đấu có thế nào đi nữa.

Số hiệu đội lớn nhất có thể giành giải với \(N=3, P=4\), tùy thuộc vào cách sắp xếp danh sách giải đấu, là đội 6: danh sách giải đấu ví dụ trên cho thấy đội 6 có thể giành giải, và thực tế là đội 7 sẽ không bao giờ giành được giải cho dù danh sách giải đấu có thế nào đi nữa.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(T\). Tiếp theo là \(T\) bộ test. Mỗi bộ test gồm hai số nguyên cách nhau bởi dấu cách: \(N\), cho biết giải đấu có \(2^N\) đội, và \(P\), số lượng giải thưởng.

Dữ liệu ra

Với mỗi bộ test, hãy xuất một dòng chứa "Case #x: y z", trong đó x là số thứ tự bộ test (bắt đầu từ 1), y là số hiệu đội lớn nhất chắc chắn giành được giải thưởng, và z là số hiệu đội lớn nhất có thể giành được giải thưởng.

Ràng buộc

• \(1 \le T \le 100\).
• \(1 \le P \le 2^N\).

Phân nhóm

• Test set 1 (Visible): \(1 \le N \le 10\).
• Test set 2 (Hidden): \(1 \le N \le 50\).

Đ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
3 4
3 5
3 3

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

Nguồn

Google Code Jam 2013, Vòng 2, bài Many Prizes.

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