Hãy in ra tất cả các xâu độ dài ~n~ gồm ba kí tự A, B và C, sao cho không có hai kí tự liền nhau nào giống nhau.

Ví dụ, xâu ABBC không hợp lệ vì nó chứa hai kí tự B đứng cạnh nhau.

Dữ liệu vào

Một dòng duy nhất chứa số nguyên ~n~.

Kết quả

In ra tất cả các xâu hợp lệ, mỗi xâu trên một dòng. Thứ tự in ra là tùy ý.

Ví dụ

Đầu vào:

2

Đầu ra:

AB
AC
BA
BC
CA
CB

Giải thích: Với ~n = 2~ có ~6~ xâu hợp lệ. Mọi thứ tự in đều được chấp nhận, nên BA AB CB BC AC CA cũng là một đáp án đúng.

Giới hạn

• ~1 \le n \le 10~

Số xâu hợp lệ là ~3 \cdot 2^{n-1}~, nhiều nhất là ~1536~ xâu khi ~n = 10~.

Cho tập hợp ~S = \{1, 2, \ldots, n\}~. Hãy liệt kê tất cả các tập con có đúng ~k~ phần tử của ~S~ theo thứ tự từ điển.

Dữ liệu vào

Một dòng duy nhất chứa hai số nguyên ~n~ và ~k~.

Kết quả

Liệt kê tất cả các tập con gồm ~k~ phần tử của ~S~ theo thứ tự từ điển, mỗi tập con trên một dòng. Các phần tử trong cùng một tập con được in theo thứ tự tăng dần, cách nhau bởi dấu cách.

Ví dụ

Đầu vào:

4 2

Đầu ra:

1 2
1 3
1 4
2 3
2 4
3 4

Giải thích: Tập ~S = \{1, 2, 3, 4\}~ có ~\binom{4}{2} = 6~ tập con gồm ~2~ phần tử, được liệt kê theo thứ tự từ điển.

Giới hạn

• ~1 \le k \le n \le 20~

Khác với bài trước, ở bài này thứ tự in ra phải đúng theo thứ tự từ điển. Số tập con nhiều nhất là ~\binom{20}{10} = 184756~.

Khu rừng là một bảng kích thước ~4 \times 4~. Từ ô ~(i, j)~, Per có thể đi tới ô ~(i+1, j)~ hoặc ô ~(i, j+1)~.

Ô ~(i, j)~ có ~A_{i,j}~ cây nấm. Hành trình của Per bắt đầu từ ô ~(1, 1)~ và kết thúc ở ô ~(4, 4)~. Hỏi Per có thể thu được nhiều nhất bao nhiêu cây nấm?

Per thu hết số nấm ở mọi ô mà cô ấy đi qua, tính cả ô ~(1, 1)~ và ô ~(4, 4)~.

Dữ liệu vào

Gồm ~4~ dòng, mỗi dòng chứa ~4~ số nguyên — dòng thứ ~i~ chứa ~A_{i,1}, A_{i,2}, A_{i,3}, A_{i,4}~.

Kết quả

In ra số nấm nhiều nhất mà Per có thể thu được.

Ví dụ

Đầu vào:

2 2 2 1
1 1 2 1
1 1 2 1
1 1 2 2

Đầu ra:

14

Giải thích: Per đi dọc hàng đầu tới ô ~(1, 3)~, rồi đi thẳng xuống cột ~3~ tới ô ~(4, 3)~, cuối cùng sang ô ~(4, 4)~. Tổng số nấm là ~2 + 2 + 2 + 2 + 2 + 2 + 2 = 14~.

Giới hạn

• ~1 \le A_{i,j} \le 10^9~

Mỗi hành trình luôn đi qua đúng ~7~ ô, nên kết quả có thể lên tới ~7 \cdot 10^9~ và không vừa trong số nguyên 32 bit.

Đếm số cách đặt ~n~ quân hậu trên bàn cờ kích thước ~n \times n~ sao cho không có hai quân hậu nào tấn công nhau.

Hai quân hậu tấn công nhau nếu chúng nằm trên cùng một hàng, cùng một cột, hoặc cùng một đường chéo.

Một cách đặt ~5~ quân hậu hợp lệ:

X....
...X.
.X...
....X
..X..

Dữ liệu vào

Một dòng duy nhất chứa số nguyên ~n~.

Kết quả

In ra số cách đặt ~n~ quân hậu thỏa mãn.

Ví dụ

Đầu vào:

5

Đầu ra:

10

Giải thích: Với bàn cờ ~5 \times 5~ có đúng ~10~ cách đặt ~5~ quân hậu không tấn công nhau.

Giới hạn

• ~1 \le n \le 10~

Lưu ý rằng với ~n = 2~ và ~n = 3~ không có cách đặt nào, nên kết quả là ~0~.

Có ~n~ đồ vật, đồ vật thứ ~i~ có khối lượng ~w_i~ và giá trị ~v_i~. Bạn được chọn một số đồ vật bất kỳ miễn sao tổng khối lượng của chúng không vượt quá ~S~ cho trước. Hãy tìm cách chọn sao cho tổng giá trị là lớn nhất có thể.

Mỗi đồ vật chỉ được chọn nhiều nhất một lần.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~S~.
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~w_i~ và ~v_i~.

Kết quả

In ra tổng giá trị lớn nhất có thể thu được.

Ví dụ

Đầu vào:

3 5
1 4
4 1
2 100

Đầu ra:

104

Giải thích: Chọn đồ vật ~1~ và đồ vật ~3~: tổng khối lượng ~1 + 2 = 3 \le 5~, tổng giá trị ~4 + 100 = 104~. Không thể thêm đồ vật ~2~ vì khi đó khối lượng thành ~7 > 5~.

Giới hạn

• ~1 \le n \le 20~
• ~1 \le S \le 10^9~
• ~1 \le w_i, v_i \le 10^9~

Lưu ý rằng ~S~ rất lớn nên không thể quy hoạch động theo khối lượng; tuy nhiên ~n \le 20~ nên số cách chọn chỉ nhiều nhất là ~2^{20}~. Kết quả có thể lên tới ~2 \cdot 10^{10}~, không vừa trong số nguyên 32 bit.

Có ~n~ thành phố. Đi từ thành phố ~i~ tới thành phố ~j~ tốn ~A_{i,j}~ đồng. Hãy tìm hành trình có chi phí nhỏ nhất, đi qua mỗi thành phố đúng một lần rồi quay trở về thành phố xuất phát.

Lưu ý rằng chi phí không nhất thiết đối xứng: ~A_{i,j}~ có thể khác ~A_{j,i}~.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên ~n~.
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa ~n~ số nguyên ~A_{i,1}, A_{i,2}, \ldots, A_{i,n}~.

Kết quả

In ra một số nguyên là chi phí nhỏ nhất.

Ví dụ

Đầu vào:

5
0 2 8 5 1
10 0 5 9 9
3 5 0 6 6
2 8 2 0 2
6 3 8 7 0

Đầu ra:

17

Giải thích: Hành trình ~1 \to 5 \to 2 \to 3 \to 4 \to 1~ có chi phí ~1 + 3 + 5 + 6 + 2 = 17~, và đó là chi phí nhỏ nhất.

Giới hạn

• ~1 \le n \le 10~
• ~1 \le A_{i,j} \le 1000~ với ~i \ne j~
• ~A_{i,i} = 0~

Với ~n = 1~, hành trình không cần đi đâu cả nên chi phí là ~0~.

Cho một dãy ~A~ gồm ~n~ số nguyên. Hãy tìm cách chia dãy thành ~k~ nhóm sao cho tổng các phần tử trong mỗi nhóm bằng nhau. Mỗi nhóm phải chứa ít nhất một phần tử, và mỗi phần tử thuộc đúng một nhóm.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~.
• Dòng thứ hai chứa ~n~ số nguyên ~A_1, A_2, \ldots, A_n~.

Kết quả

In ra ~n~ số nguyên, trong đó số thứ ~i~ là chỉ số nhóm (một số từ ~1~ đến ~k~) của phần tử thứ ~i~. Nếu có nhiều đáp án, in ra một đáp án bất kỳ.

Nếu không có cách chia nào thỏa mãn, in ra một số ~0~ duy nhất.

Ví dụ

Đầu vào:

5 3
1 4 6 9 10

Đầu ra:

1 2 2 1 3

Giải thích: Tổng của cả dãy là ~30~, nên mỗi nhóm phải có tổng ~10~. Nhóm ~1~ gồm ~A_1 + A_4 = 1 + 9 = 10~, nhóm ~2~ gồm ~A_2 + A_3 = 4 + 6 = 10~, nhóm ~3~ gồm ~A_5 = 10~. Các đáp án 1 3 3 1 2 hay 3 1 1 3 2 cũng được chấp nhận.

Giới hạn

• ~2 \le k < n \le 10~
• ~1 \le A_i \le 100~

Hãy tìm một lời giải cho bảng Sudoku còn dở dang. Nếu có nhiều hơn một lời giải, in ra một lời giải bất kỳ.

Một bảng Sudoku hoàn chỉnh là bảng ~9 \times 9~ trong đó mỗi hàng, mỗi cột và mỗi khối con ~3 \times 3~ đều chứa đủ các chữ số từ ~1~ đến ~9~, mỗi chữ số đúng một lần.

Dữ liệu đảm bảo tồn tại ít nhất một lời giải.

Dữ liệu vào

Gồm ~9~ dòng, mỗi dòng chứa ~9~ số nguyên trong đoạn ~[0, 9]~. Số ~0~ nghĩa là ô còn trống.

Kết quả

Gồm ~9~ dòng, mỗi dòng chứa ~9~ số nguyên trong đoạn ~[1, 9]~ — một lời giải hợp lệ. Các chữ số đã cho trong dữ liệu vào phải được giữ nguyên.

Ví dụ

Đầu vào:

5 3 0 0 7 0 0 0 0
6 0 0 1 9 5 0 0 0
0 9 8 0 0 0 0 6 0
8 0 0 0 6 0 0 0 3
4 0 0 8 0 3 0 0 1
7 0 0 0 2 0 0 0 6
0 6 0 0 0 0 2 8 0
0 0 0 4 1 9 0 0 5
0 0 0 0 8 0 0 7 9

Đầu ra:

5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9

Giải thích: Mọi hàng, mọi cột và mọi khối ~3 \times 3~ đều chứa đủ các chữ số từ ~1~ đến ~9~, và tất cả các chữ số đã cho ban đầu đều được giữ nguyên.

Giới hạn

Bảng luôn có kích thước ~9 \times 9~ và luôn tồn tại ít nhất một lời giải. Số ô trống có thể lên tới ~81~ (bảng trống hoàn toàn).

Cho một bàn cờ kích thước ~n \times m~. Hãy tìm một dãy các nước đi của quân mã sao cho quân mã đi qua mỗi ô đúng một lần. Ban đầu bạn được đặt quân mã ở bất kỳ ô nào.

Quân mã đi theo hình chữ L: từ ô ~(r, c)~ nó có thể nhảy tới ô ~(r', c')~ nếu ~\{|r - r'|, |c - c'|\} = \{1, 2\}~.

Dữ liệu vào

Một dòng duy nhất chứa hai số nguyên ~n~ và ~m~.

Kết quả

In ra một bảng kích thước ~n \times m~ thể hiện thứ tự đi thăm các ô, bắt đầu từ ~1~. Nếu có nhiều đáp án, in ra một đáp án bất kỳ.

Nếu không tồn tại hành trình nào thỏa mãn, in ra ~-1~.

Ví dụ

Đầu vào:

5 5

Đầu ra:

1 20 9 14 3
10 15 2 19 24
21 8 23 4 13
16 11 6 25 18
7 22 17 12 5

Giải thích: Quân mã bắt đầu ở ô ~(1, 1)~ và kết thúc ở ô ~(4, 4)~, đi qua cả ~25~ ô đúng một lần. Mọi hành trình hợp lệ khác cũng được chấp nhận.

Giới hạn

• ~1 \le n, m \le 7~

Lưu ý rằng có những bàn cờ không tồn tại hành trình nào, ví dụ ~2 \times 2~, ~3 \times 3~ hay ~4 \times 4~ — với những trường hợp đó hãy in ~-1~.

Trò chơi Dò Mìn được chơi trên một lưới gồm ~n~ hàng và ~m~ cột. Mỗi ô trong lưới có thể chứa mìn hoặc không. Người chơi lần lượt chọn các ô để mở. Nếu ô được mở không chứa mìn, số mìn trong ~8~ ô kề với nó sẽ được hiển thị. Người chơi phải dựa vào các thông tin đó để đánh dấu toàn bộ những ô có mìn.

Ở bài này, thay vì chơi trò chơi, bạn được cho một lưới ~A~ gồm ~n~ hàng và ~m~ cột. Số ở hàng ~i~, cột ~j~ cho biết số mìn trong ~8~ ô kề với ô ~(i, j)~. Nhiệm vụ của bạn là tìm ra những ô có chứa mìn.

Lưu ý: ~A_{i,j}~ được cho với mọi ô, kể cả ô có mìn, và không tính bản thân ô ~(i, j)~.

Dữ liệu đảm bảo tồn tại ít nhất một cách đặt mìn thỏa mãn.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~.
• ~n~ dòng tiếp theo, mỗi dòng chứa ~m~ số nguyên — lưới ~A~.

Kết quả

In ra một lưới gồm ~n~ hàng và ~m~ cột. Số ở hàng ~i~, cột ~j~ bằng ~1~ nếu ô ~(i, j)~ có mìn, ngược lại bằng ~0~. Nếu có nhiều đáp án, in ra một đáp án bất kỳ.

Ví dụ

Đầu vào:

3 3
1 1 1
2 2 3
2 2 2

Đầu ra:

0 0 0
0 1 0
0 1 1

Giải thích: Mìn nằm ở các ô ~(2,2)~, ~(3,2)~ và ~(3,3)~. Chẳng hạn ô ~(2,3)~ kề với cả ba quả mìn nên ~A_{2,3} = 3~; còn ô ~(2,2)~ tuy có mìn nhưng chỉ kề với hai quả mìn ở ~(3,2)~ và ~(3,3)~ nên ~A_{2,2} = 2~.

Giới hạn

• ~1 \le n, m \le 20~
• ~0 \le A_{i,j} \le 8~