[Học thêm HSG9] Backtracking

Cho \(n\) thành phố, di chuyển từ thành phố \(i\) sang thành phố \(j\) hết \(A_{i,j}\) xu. Hãy tìm lộ trình tốn ít tiền nhất để đi qua mỗi thành phố chính xác \(1\) lần và quay lại thành phố bắt đầu.

Input

Dòng đầu tiên gồm số nguyên \(n(1 \leq n \leq 10)\).
\(n\) dòng tiếp theo, mỗi dòng gồm \(n\) số nguyên \(A_{i,j}(1 \leq A_{i,j} \leq 10^9)\).

Output

Một số nguyên là lượng tiền ít nhất phải bỏ ra.

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

17

Cho dãy \(A\) gồm \(n\) số nguyên. Hãy tìm cách chia dãy thành \(k\) nhóm mà các nhóm có tổng bằng nhau. Mỗi nhóm phải có ít nhất một phần tử.

Input

Dòng đầu tiên gồm hai số nguyên \(n,k(2 \leq k < n \leq 10)\)
Dòng thứ hai gồm \(n\) số nguyên \(A_i\).

Output

In ra \(n\) số nguyên, số nguyên thứ \(i\) là nhóm của phần tử thứ \(i\). Nếu có nhiều đáp án, in ra đáp án bất kì.
Nếu không tồn tại đáp án, in ra \(ze\).

5 3
1 4 6 9 10

1 3 3 1 2

Đếm số lượng cách đặt \(n\) quân hậu trên bàn cờ kích cỡ \(n*n\)sao cho không có 2 quân hậu nào tấn công được nhau.
Ví dụ một cách đặt \(5\) quân hậu:
X....
...X.
.X...
....X
..X..

Input

Một số nguyên \(n(1 \leq n \leq 10)\).

Output

Một số nguyên duy nhất là số lượng cách đặt \(n\) quân hậu.

5

10

Hãy in ra những xâu độ dài \(n\) chỉ gồm ba loại kí tự \(A\), \(B\), và \(C\) và không có hai kí tự cạnh nhau nào được giống nhau.
Ví dụ xâu \(ABBC\) là không thỏa mãn do có hai kí tự \(B\) đứng cạnh nhau.

Input

Một dòng gồm một số nguyên \(n(n \leq 10)\).

Output

In ra toàn bộ những xâu thỏa mãn, có thể in ra theo thứ tự bất kì.

2

AB
BA
BC
CB
AC
CA

Có thể định nghĩa khái niệm dãy ngoặc đúng dưới dạng đệ quy như sau:

1. "()()" là dãy ngoặc đúng
2. \(C\) là dãy ngoặc đúng nếu \(C\) = (\(A\)) hay \(C\) = \(AB\) với \(A\), \(B\) là các dãy ngoặc đúng.

Ví dụ dãy ngoặc đúng: (), (()), ()(), (())()
Ví dụ dãy ngoặc sai: )(, ((((, ()((, )))), )()(
Bạn hãy viết chương trình liệt kê tất cả các dãy ngoặc đúng có chiều dài \(n\) (\(n\) chẵn)

Input

• Là số nguyên \(n\) (\(n\) chẵn, \(2 ≤ n ≤ 24\))

Output

• In số \(m\) là số lượng các dãy ngoặc đúng có chiều dài \(n\)

4

2

Cho bàn cỡ vua kích cỡ \(n*m\). Bạn được đặt một quân mã vào vị trí bất kì trên bàn cờ trống. Hãy tìm đường đi qua tất cả các ô trên bàn cờ, mỗi ô đúng một lần.

Input

Một dòng gồm hai số nguyên \(n,m(1 \leq n,m \leq 7)\).

Output

In ra một ma trận \(n\) dòng, \(m\) cột là thứ tự thăm các ô của con mã, bắt đầu từ \(1\). Có thể in ra cách đi bất kì.

5 5

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

Sinh các hoán vị từ tập \([1..n]\) biết mỗi số chỉ xuất hiện một lần và trong mỗi hoán vị số nào trong tập \([1..n]\) cũng phải xuất hiện.

Yêu cầu

• Cho số nguyên dương \(n\), hãy in tất cả các hoán vị của \(n\) số tự nhiên đầu tiên theo thứ tự từ điển.

Input

• 1 dòng duy nhất là số \(n\) \((0<n<10)\)

Output

• Kết quả bài toán

3

123
132
213
231
312
321

Tèo nay đã lớn và có \(3\) người con. Hôm nay, sau một ngày làm việc vất vả thì cả \(3\) người con của Tèo đều có mặt và xin Tèo tiền để mua bánh. Trong túi của Tèo hiện có \(n\) tờ tiền, tờ thứ \(i(1 \leq i \leq n)\) có mệnh giá là \(a_i\) . Tèo muốn tình yêu thương của mình đến các con thật công bằng nên sẽ tìm cách để chia hết số tiền cho \(3\) người sao cho tổng chênh lệch số tiền mỗi người là thấp nhất. Đồng thời Tèo muốn biết liệu mình có thể làm cho tổng chênh lệch đó bằng không được hay không.

Input

Dòng đầu tiên chứa số nguyên \(n( 3\leq n \leq 10)\)
Dòng tiếp theo chứa \(n\) số nguyên \(a_i(1 \leq a_i \leq 10^{11})\)

Output

Dòng đầu tiên xuất ra Yes nếu tồn tại cách có tổng chênh lệch bằng \(0\), ngược lại xuất ra tổng chênh lệch nhỏ nhất có thể.
Dòng thứ \(2\) xuất ra số lượng tờ tiền và mệnh giá các tờ tiền mà Tèo cho người con thứ nhất.
Dòng thứ \(3\) xuất ra số lượng tờ tiền và các mệnh giá các tờ tiền mà Tèo cho người con thứ hai.
Dòng thứ cuối xuất ra số lượng tờ tiền và các mệnh giá các tờ tiền mà Tèo cho người con thứ ba.
Lưu ý: Các số trên cùng một dòng cách nhau ít nhất một dấu cách.
Bạn có thể in ra một cách chia bất kỳ, miễn sao cách chia đó hợp lệ.

Sample

4
1 2 1 2

Yes
2 1 1
1 2
1 2

4
1 2 1 3

1
2 1 1
1 2
1 3

Cho \(S\) là tập gồm \(N\) chữ số thập phân khác nhau.

Yêu cầu

Viết chương trình tìm số tự nhiên \(X\) nhỏ nhất thỏa mãn:

• \(X \leq 10^9\)
• \(X\) có biểu diễn thập phân chỉ gồm các chữ số thuộc \(S\)
• \(X\) chia hết cho số \(m\) cho trước\((0 < m \leq 1000000)\)

Dữ liệu vào

Cho trong tập tin BAI3.INP gồm \(3\) dòng:
- Dòng thứ nhất chứa số nguyên dương \(N(1 \leq N \leq 10)\) – số lượng các chữ số có trong tập \(S\).
- Dòng thứ hai chứa số \(m(0 < m \leq 1000000)\)
- Dòng thứ ba chứa \(N\) chữ số thập phân của tập \((S_i < S_{i+1},1 \leq i \leq N\), các chữ số \(S_i\) cách nhau ít nhất một dấu cách).

Dữ liệu ra

Ghi ra tập tin BAI3.OUT gồm một dòng duy nhất:
- Nếu tìm được số \(X\) thỏa mãn yêu cầu đề bài thì ghi ra số \(X\).
- Nếu không tìm được số \(X\) thỏa mãn yêu cầu đề bài thì ghi ra thông báo vo nghiem.

2
8
1 4

144