Cho ma trận vuông cỡ NxN gồm N hàng và N cột. Hãy sắp xếp các phần tử trong ma trận theo cột theo thứ tự tăng dần.

Định dạng đầu vào: Dòng đầu tiên là số N. N dòng tiếp theo mỗi dòng có N số.

Ràng buộc: 1≤n≤200; Các phần tử trong ma trận là số dương không quá 10^9;

Định dạng đầu ra: In ra ma trận sau khi đã sắp xếp theo cột tăng dần.

Input:

3
1 2 3
5 5 2
1 4 7

Output:

1 2 2
1 4 3
5 5 7

Cho ma trận A các số nguyên có N hàng và M cột. Tìm đường đi từ ở [1, 1] tới ô [N, M] sao cho tổng các số trên đường đi là lớn nhất có thể, biết rằng ở mỗi bước chỉ có thể đi từ ô hiện tại xuống ô phía dưới hoặc đi sang phải.

Định dạng đầu bào: Dòng đầu tiên N và M. N dòng tiếp theo mỗi dòng gồm M phần tử.

Ràng buộc: 1 ≤ N,M ≤ 500; 1 ≤ A[i][j] ≤ 10^9

Định dạng đầu ra: In ra đường đi có tổng lớn nhất.

Input:

3 3
1 2 2
3 10 2
5 7 2

Output:

23

Cho mảng 2 chiều A gồm N hàng và N cột, hãy tìm 1 đường đi từ dòng 1 tới dòng N sao cho các phần tử trên đường đi đó là lớn nhất có thể. Biết rằng ở mỗi bước đi từ ô hiện tại chỉ có thể đi xuống ô dưới bên trái, ô dưới bên phải hoặc ô dưới của ô hiện tại. Hãy tìm 1 đường đi có tổng các số trên đường đi là lớn nhất.

Định dạng đầu vào:

• Dòng 1 là N

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

Ràng buộc: 1 <= N <＝ 100; 1 <= A[i][j] <= 100

Định dạng đầu ra: In ra kết quả của bài toán

Input:

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

Output:

33

Cho mảng 2 chiều A gồm N hàng và N cột, hàng được đánh số từ 1 đến N từ trên xuống dưới, cột được đánh số từ 1 tới N từ trái sang phải, hãy tìm 1 đường đi từ một ô ở cột 1 tới 1 ô ở cột N sao cho các phần tử trên đường đi đó là lớn nhất có thể. Biết rằng ở mỗi bước đi từ ô hiện tại (i, j) chỉ có thể đi sang phải (i, j + 1) hoặc đi xuống ô dưới bên phải (i + 1, j + 1), ô bên trên bên phải(i - 1, j + 1). Hãy tìm 1 đường đi có tổng các số trên đường đi là lớn nhất.

Định dạng đầu vào:

Dòng 1 là N

N dòng tiếp theo mỗi dòng gồm N số

Ràng buộc:

• 1<=N<=100

• -100<=A[][j]<=100

Định dạng đầu ra: In ra đáp án của bài toán

Input:

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

Output:

40

Giải thích: Đường đi có tổng lớn nhất : 9 + 6 + 9 + 7 + 9 = 40

Bạn được cung cấp một ma trận vuông có N dòng và N cột chỉ bao gồm các số hãy tìm hình vuông có kích thước 3 x 3 có tổng lớn nhất trong ma trận.

Đầu vào: Dòng đầu tiên gồm 2 số N và M; N dòng tiếp theo mỗi dòng M số nguyên;

Ràng buộc: 3 <= N, M <= 500:0 <= A[i][j] <= 10^6

Đầu ra: In ra kết quả đáp án của bài toán

Input:

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

Output:

56

Xây dựng tam giác Pascal tính tổ hợp chập K của N với K và N nhập từ bàn phím. Lưu ý kết quả chia dư cho ~10^9+7~

Ràng buộc: ~0 \leq K \leq N \leq 10^3~

In ra kết quả là tổ hợp châp K của N

Input:

10 5

Tính tổ hợp chập 5 của 10

Output:

252

Cho một ma trận nhị phân cỡ ~N*M~ chỉ bao gồm các số 0, 1. Hãy xác định vùng nhiều số 1 nhất trên ma trận, biết rằng các ô có chung cạnh được coi là cùng miền.

Đầu vào

Dòng đầu tiên là ~N~ và ~M~ tương ứng với số hàng, cột của ma trận. ~N~ dòng tiếp theo mỗi dòng có M số

Giới hạn

~1 \leq N, M \leq 500~

Các phần tử trong ma trận có giá trị 0 hoặc 1.

Đầu ra

In ra diện tích miền có nhiều số 1 nhất

Ví dụ :

Input 01

5 6
0 1 0 1 0 1 
0 0 0 1 1 0 
0 1 1 0 1 1 
0 1 1 0 0 0 
0 0 0 0 0 0

Output 01

5

Cho ma trận A có N hàng và M cột. Tìm đường đi từ ô đầu tiên [1, 1] đến ô cuối cùng [N , M] sao cho tổng các số trên đường đi phải là lớn nhất, biết rằng mỗi bước chỉ có thể đi từ ô hiện tại xuống ô phía dưới hoặc ô bên phải.

Ràng buộc: ~1 \leq N \leq 100~; ~1 \leq A[i][j] \leq 10^9~

In ra giá trị tổng lớn nhất

Input:

3 3
1 2 2
3 10 2
5 7 2

Output:

23

Tèo khá thích chơi cờ vua và quân cờ mà Tèo yêu thích chính là quân Xe, bây giờ Tèo có một bàn cờ cỡ NxN, trên bàn cở sẽ có những ở trồng và có những ô có vật cản, nhiệm vụ của bạn là hãy xác định xem số lượng ô trên bàn cờ mà quân Xe có thế di chuyển tới, biết ràng nó có thế đi qua đi lại 1 ô trống nhiều lần và không thể đi vào ô có vật cản.

Bàn cờ gồm N hàng N cột, mỗi ô là số 1 tương ứng với vật cản và ô số 0 tương ứng với ô trồng. Ban đầu quân Xe năm ở vị trí hàng 5 và cột T và ô (5, T) là ô trống

Định dạng đầu vào:

• Dòng 1 là N, S, T

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

Ràng buộc:

~5 \leq N＜=20~

~0 \leq A[i][j] \leq 1~

Đầu ra:

In ra số lượng ô trên bàn cờ mà quân Xe có thể đến được

Ví dụ:

Input:

7 4 6
1 1 1 0 0 1 0
1 1 0 0 0 1 1
0 1 0 0 0 0 0
1 0 1 0 1 0 1
1 0 1 1 1 1 0
1 1 0 0 1 0 1
0 0 0 0 1 1 0

Output:

12

Tèo khá thích chơi cờ vua và quân cờ mà Tèo yêu thích chính là quân Tịnh, bây giờ Tèo có một bàn cờ cỡ NxN, trên bàn cờ sẽ có những ô trống và có những ô có vật cản, nhiệm vụ của bạn là hãy xác định xem số lượng ô trên bàn cờ mà quân Tịnh có thế di chuyển tới, biết rằng nó có thể đi qua đi lại 1 ô trống nhiều lần và không thể đi vào ô có vật cản.

Bàn cờ gồm N hàng N cột, mỗi ô là số 1 Tương ứng với vật cản và ô số 0 tương ứng với ô trống. Ban đầu quân Tịnh năm ở vị trí hàng S và cột T và ô (S, T) là ô trống

Định dạng đầu vào:

• Dòng 1 là N, S, T

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

Ràng buộc:

~5 \leq N＜=20~

~0 \leq A[i][j] \leq 1~

Đầu ra:

In ra số lượng ô trên bàn cờ mà quân Tịnh có thể đến được

Ví dụ:

Input:

6 1 3
0 0 0 1 1 0
1 1 1 0 1 0
1 0 0 1 0 1
1 1 1 1 1 0
0 0 1 1 1 0
0 1 1 0 1 0

Output:

6

Cho bàn cờ vua cỡ N * N, các ô trên bàn cờ có giá trị là 0 hoặc 1. Một con mã xuất phát từ ô (s, t) và muốn di chuyến tới ô (u, v), con mã chỉ có thể di chuyển ở các ô mà tại ô đó có giá trị là 1 và nó có thế di chuyến qua lại 1 ô nhiều lần. Hãy xác định xem con mã có thế tìm được đường đi hay không, dữ liệu đảm bảo ô (s, t) và ô (u, v) đều có giá trị là 1.

Ràng buộc: 1 ≤ N,M ≤ 100; 1 ≤ s,t,u,v ≤ N; 0 ≤ A[i][j] ≤ 1;

In YES nếu con mã có thể tìm được đường đi, ngược lại in NO.

Input:

9
7 5 4 3
1 0 1 0 1 0 1 1 1
1 1 1 1 0 0 0 0 1
1 0 1 1 1 0 1 1 1
1 0 1 0 1 0 0 0 0
0 1 1 0 1 0 1 1 1
1 0 0 0 0 1 1 0 1
1 0 1 0 1 0 1 1 0
0 1 1 0 0 0 0 1 1
0 0 1 1 0 0 0 0 1

Output:

YES

Cho một ma trận nhị phân có N hàng và M cột, một chú chuột bắt đầu từ ô có toa độ [s, t] và tìm đường đi tới ô [u, v], biết răng ở mỗi bước con chuột có thể di chuyển từ ô hiện tại sang các ô chung cạnh với ô hiện tại và số ở ô chung cạnh là số 1. Bạn chỉ được đi qua 1 ô đúng 1 lần hãy kiểm tra xem con chuột có thể tim được đường đi tới ô [u, v] hay không? Dữ liệu đảm bảo 2 ô [s, t] và ô [u, v] đều bằng 1.

Ràng buộc: 1 ≤ N,M ≤ 100; 1 ≤ s,u ≤ N; 1 ≤ t, v ≤ M;

In YES nếu con chuột có thể tim được đường đi, ngược lại in NO.

Input 01:

3 5
1 1 3 5
1 0 1 0 0
0 1 1 1 1
1 0 0 0 1

Output 01:

NO

Input 02:

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

Output 01:

YES

Cho một ma trận nhị phân có N hàng và M cột, một con chuột bắt đầu từ ô có tọa độ [s, t] và tìm đường đi tới ô [u, v], biết rằng ở mỗi bước con chuột có thể di chuyển từ ô hiện tại sang các ô chung cạnh với ô hiện tại và số ở ô chung cạnh là số 1.

Bạn chỉ được đi qua 1 ô đúng 1 lần hãy kiểm tra xem con chuột có thể tìm được đường đi tới ô [u, v] hay không ? Dữ liệu đảm bảo 2 ô [s, t] và ô [u, v] đều bằng 1.

Gợi ý : Loang từ ô (u, v) xem ô (s, t) có bị đi qua không, nếu có là sẽ tìm được đường đi

Ví dụ con chuột có thể đi từ ô (1, 1) tới ô (3, 6) theo đường đi được tô màu xanh

Đầu vào

Dòng đầu tiên N và M.

Dòng thứ 2 là 4 số s, t, u , v

N dòng tiếp theo mỗi dòng gồm M phần tử.

Giới hạn

1 ≤ N, M ≤ 100

1 ≤ s, u ≤ N

1 ≤ t, v ≤ M

Đầu ra

In YES nếu con chuột có thể tìm được đường đi, ngược lại in NO.

Ví dụ :

Input 01

3 5
1 1 3 5
1 0 1 0 0 
0 1 1 1 1 
1 0 0 0 1

Output 01

NO