BOI 2008 - Ngày 1

Hai người chơi A và B chơi trên một bàn cờ vuông kích thước \(n\times n\). Mỗi ô là ô trắng hoặc ô đen; trò chơi chỉ diễn ra trên các ô trắng. Mỗi người có một quân cờ, ban đầu đặt tại ô xuất phát của mình. Hai ô xuất phát đều trắng và khác nhau.

Trong mỗi lượt, người chơi di chuyển quân của mình sang một ô trắng kề cạnh theo một trong bốn hướng. Nếu quân vừa đi vào ô đang có quân đối phương, người chơi được đi thêm một bước; nhờ vậy quân có thể nhảy qua đối phương, và hướng của bước thứ hai không nhất thiết giống bước thứ nhất.

A đi trước, sau đó hai người luân phiên. Mục tiêu là đưa quân tới ô xuất phát của đối phương. Người đầu tiên làm được điều đó sẽ thắng. Hãy xác định người có chiến thuật thắng, tức có thể thắng bất kể đối phương đi như thế nào.

Trong hình trên, nếu A đi sang phải trong ba lượt đầu thì B sẽ đi lên trong ba lượt đầu. Ở lượt thứ ba, B đi vào ô của A, được đi thêm và sẽ tới ô xuất phát của A trước.

Trong hình trên, A có thể bắt đầu bằng một bước sang phải và một bước xuống dưới. Tùy hai bước đầu của B, A tiếp tục đi xuống hoặc sang phải để tránh B và tới ô xuất phát của B trước.

Dữ liệu vào

Dòng đầu chứa số nguyên \(t\) — số bộ test (\(1\le t\le 10\)).

Mỗi bộ test được mô tả như sau:

• Dòng đầu chứa số nguyên \(n\) (\(2\le n\le 300\)).
• \(n\) dòng tiếp theo, mỗi dòng gồm đúng \(n\) ký tự, mô tả bàn cờ. Mỗi ký tự là . (ô trắng), # (ô đen), A (ô xuất phát của A) hoặc B (ô xuất phát của B).

Luôn tồn tại một đường đi chỉ qua các ô trắng giữa hai ô xuất phát.

Dữ liệu ra

Với mỗi bộ test, in một dòng chứa ký tự A hoặc B, cho biết người có chiến thuật thắng.

Phân nhóm

1. 40 điểm: \(n\le 40\).
2. 20 điểm: \(n\le 150\).
3. 40 điểm: không có ràng buộc bổ sung.

Ví dụ

2
4
A...
.#..
....
...B
4
A...
....
..#.
...B

B
A

Hai hồ nước được nối bởi \(n\) kênh. Mỗi kênh có hai cổng và chỉ mở khi cả hai cổng đều mở. Các cổng được điều khiển bởi \(m\) công tắc: một công tắc có thể điều khiển nhiều cổng, nhưng mỗi cổng do đúng một công tắc điều khiển. Hai cổng của cùng một kênh có thể dùng chung công tắc; cũng có thể có công tắc không điều khiển cổng nào.

Mỗi cổng hoạt động theo một trong hai chế độ:

• cổng mở khi công tắc bật và đóng khi công tắc tắt;
• cổng đóng khi công tắc bật và mở khi công tắc tắt.

Hãy xác định liệu có thể đặt trạng thái các công tắc sao cho mọi kênh đều đóng hay không. Nếu có, hãy tìm một cấu hình như vậy.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(n\) và \(m\) — số kênh và số công tắc (\(1\le n\le 250\,000\), \(1\le m\le 500\,000\)). Các công tắc được đánh số từ \(1\) đến \(m\).

Mỗi trong \(n\) dòng tiếp theo chứa bốn số nguyên \(a,s_a,b,s_b\). Hai cổng của kênh lần lượt do công tắc \(a\) và \(b\) điều khiển (\(1\le a,b\le m\)). Mỗi giá trị \(s_a,s_b\) bằng 0 hoặc 1; \(s_i=0\) nghĩa là cổng đóng khi và chỉ khi công tắc \(i\) tắt, còn \(s_i=1\) nghĩa là cổng đóng khi và chỉ khi công tắc \(i\) bật.

Dữ liệu ra

Nếu có thể đóng tất cả các kênh, in \(m\) dòng. Dòng thứ \(i\) chứa 0 nếu công tắc \(i\) cần tắt, hoặc 1 nếu cần bật. Nếu có nhiều cấu hình hợp lệ, có thể in bất kỳ cấu hình nào.

Nếu không thể, in một dòng duy nhất chứa IMPOSSIBLE.

Phân nhóm

1. Ít nhất 30 điểm: \(n\le 40\) và \(m\le 20\).
2. Các test còn lại: không có ràng buộc bổ sung.

Ví dụ

3 2
1 0 2 1
1 0 2 0
1 1 2 1

0
1

2 1
1 0 1 0
1 1 1 1

IMPOSSIBLE

Đá Xi-\(n\)-\(k\) chỉ có ở Xứ Sở Thần Tiên. Mỗi viên là một tấm đá granit khắc đúng \(n\) chữ cái, mỗi chữ là X hoặc I. Trên tấm đá có không quá \(k\) vị trí mà hai chữ kề nhau khác nhau.

Tấm đá không có cạnh trên hay cạnh dưới cố định, nên có thể xoay ngược 180 độ. Chẳng hạn, IXXIIXXX và XXXIIXXI là hai cách nhìn cùng một viên đá. Viên này thuộc loại Xi-\(8\)-\(3\), đồng thời cũng thuộc loại Xi-\(8\)-\(k\) với mọi \(k\ge3\).

Không có hai viên đá nào giống nhau, trong đó hai dòng chữ đảo ngược nhau được coi là cùng một viên. Biểu diễn chính tắc của một viên đá là cách đọc nhỏ hơn theo thứ tự từ điển trong hai cách đọc. Nếu dòng chữ đối xứng thì nó chỉ có một cách đọc khác biệt và đó là biểu diễn chính tắc.

Ở đây I đứng trước X trong thứ tự từ điển: với hai xâu cùng độ dài, tại vị trí khác nhau đầu tiên, xâu có I nhỏ hơn xâu có X.

Ví dụ, có đúng 6 viên loại Xi-\(3\)-\(2\); các biểu diễn chính tắc theo thứ tự là III, IIX, IXI, IXX, XIX, XXX.

Hãy tìm biểu diễn chính tắc thứ \(i\) theo thứ tự từ điển của các viên đá loại Xi-\(n\)-\(k\).

Dữ liệu vào

Dòng duy nhất chứa ba số nguyên \(n,k,i\) (\(0\le k<n\le60\), \(0<i<10^{18}\)).

Dữ liệu ra

In biểu diễn chính tắc thứ \(i\). Nếu có ít hơn \(i\) viên đá loại Xi-\(n\)-\(k\), in NO SUCH STONE.

Phân nhóm

• 100 điểm: không có ràng buộc bổ sung; bộ dữ liệu chính thức gồm 15 nhóm chấm độc lập.

Ví dụ

3 2 5

XIX

3 2 7

NO SUCH STONE