Cho một ma trận nhị phân cỡ N x N, bạn xuất phát từ ô (1,1) và tìm đường đi tới ô (N, N). Ở mỗi bước đi bạn được phép đi theo 4 ước trên, dưới, trái, phải của ô hiện tại.

Mỗi lần đi qua một ô bạn sẽ nhặt số 0 hoặc 1 ở ô đó để ghép thành số nhị phân.

Có thể hiểu đơn giản là mỗi đường đi từ ô (1, 1) tới ô (N, N) sẽ tạo ra 1 số nhị phân tương ứng với đường đi đó.

Bạn hãy in ra đường đi có số nhị phân là lớn nhất (dạng thập phân tương ứng của nó là lớn nhất), biết rằng mỗi đường đi bạn chỉ được đi qua mỗi ô 1 lần. Lưu ý rằng các số nhị phân có thể có đường đi với số bit khác nhau.

Đầu vào

• Dòng 1 là số nguyên dương N

• N dòng tiếp theo là ma trận

Giới hạn

• 1<=N<=6

Đầu ra

In ra đường đi tương ứng với số nhị phân lớn nhất.

Ví dụ :

Input 01

3
1 1 1 
1 0 0 
1 0 0

Output 01

111001100

Cho bàn cờ vua cỡ NxN, bạn hãy tìm cách đặt N con hậu vào bàn cờ này sao cho không có 2 con hậu ăn nhau.

Giả sử X1, X2, X3…XN là vị trí con hậu đặt ở hàng 1, 2, 3…N.

Bạn hãy liệt kê các cấu hình này theo thứ tự từ điển tăng dần.

Đầu vào

• Dòng duy nhất chứa N

Giới hạn

In ra các cách đặt thỏa mãn

Đầu ra

In ra các cách đặt thỏa mãn

Ví dụ :

Input 01

4

Output 01

2 4 1 3 
3 1 4 2

Cho một số nguyên dương N, bạn hãy liệt kê các cách phân tích N dưới dạng tổng của các số nguyên dương không vượt quá N.

Các cấu hình được liệt kê theo thứ tự từ điển tăng dần.

Đầu vào

• Dòng duy nhất chứa N

Giới hạn

• 1<=N<=16

Đầu ra

In ra các cách phân tích thỏa mãn

Ví dụ :

Input 01

4

Output 01

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

Cho mảng A[] có N phần tử, bạn hãy cài đặt thuật toán Quick sort - Sắp xếp nhanh để sắp dãy số tăng dần sau đó in ra màn hình. Sử dụng phân hoạch Hoare

Đầu vào

• Dòng 1 là N : Số phần tử trong mảng

• Dòng 2 gồm N phần tử trong mảng A[]

Giới hạn

• 1<=N<=10^6

• 0<=A[i]<=10^9

Đầu ra

In ra dãy số sau khi sắp xếp

Ví dụ :

Input 01

10
413 348 77 923 538 154 462 450 71 733

Output 01

71 77 154 348 413 450 462 538 733 923

Cho xâu F được định nghĩa như sau :

F(1) = "28tech", F(2) = "C++", F(3) = "DSA JAVA"

F(N) = F(N - 3) + " " + F(N -2) + " " + F(N - 1).

Vì thế F(4) = "28tech C++ DSA JAVA", F(5) = "C++ DSA JAVA 28tech C++ DSA JAVA".

Nhiệm vụ của bạn là tìm từ thứ K trong xâu F(N), dữ liệu đảm bảo xâu F(N) có từ thứ K

Đầu vào

• Dòng 1 là T : số bộ test

• T dòng tiếp theo mỗi dòng gồm 2 số N, K

Giới hạn

• 1<=T<=100

• 1<=N<=60

• 1<=K<=10^16

Đầu ra

In ra kết quả của mỗi test trên từng dòng

Ví dụ :

Input 01

10
3 2
6 2
10 24
4 2
5 4
6 12
7 22
8 1
7 18
8 14

Output 01

JAVA
JAVA
JAVA
C++
28tech
DSA
C++
C++
C++
C++