Trên bàn cờ NxM, một quân Mã đang đứng tại vị trí (x1, y1). Hãy tính số bước đi ít nhất để quân Mã di chuyển đến vị trí (x2, y2). Nếu không thể đến được, in ra -1. Quân mã di chuyển theo quy tắc hình chữ L (như cờ vua).

Đầu vào:

Dòng 1: N, M.

Dòng 2: x1, y1.

Dòng 3: x2, y2. (Tọa độ tính từ 1).

Đầu ra:

Số bước đi ít nhất.

Ràng buộc:

1 <= N, M <= 1000

Ví dụ 1:

Input:

8 8 
1 1 
2 3

Output:

1

Ví dụ 2:

Input:

10 10 
1 1 
5 5

Output:

4

Cho một ma trận kích thước NxM. Với mỗi ô (i, j), một ô được gọi là "hàng xóm" nếu nó có chung cạnh với ô (i, j) (tức là ở phía trên, dưới, trái, phải). Hãy đếm xem trong ma trận có bao nhiêu ô mà giá trị của nó nghiêm ngặt lớn hơn tất cả các hàng xóm của nó (gọi là điểm cực đại địa phương).

Đầu vào:

Dòng 1: Hai số nguyên N, M.

N dòng tiếp theo: Mỗi dòng chứa M số nguyên dương A[i][j].

Đầu ra:

Một số nguyên duy nhất là số lượng ô thỏa mãn điều kiện.

Ràng buộc:

1 <= N, M <= 1000

1 <= A[i][j] <= 10^9

Ví dụ 1:

Input:

3 3 
1 2 1 
4 5 4 
1 2 1

Output:

1 

(Giải thích: Chỉ có số 5 ở giữa lớn hơn 2, 4, 4, 2)

Ví dụ 2:

Input:

3 3 
10 2 3 
4 5 6 
7 8 9

Output:

2 

(Giải thích: Số 10 và số 9 là các cực đại địa phương)

Cho ma trận NxM. Một "vùng ảnh hưởng" của ô (r, c) bao gồm chính nó và 8 ô xung quanh (trên, dưới, trái, phải, và 4 ô chéo). Hãy tính tổng giá trị của vùng ảnh hưởng lớn nhất trong ma trận.

Đầu vào:

Dòng 1: Hai số nguyên N, M.

N dòng tiếp theo: Mỗi dòng chứa M số nguyên A[i][j].

Đầu ra:

Tổng lớn nhất tìm được.

Ràng buộc:

3 <= N, M <= 1000

-10^5 <= A[i][j] <= 10^5

Ví dụ 1:

Input:

3 3 
1 1 1 
1 1 1 
1 1 1

Output:

9

Ví dụ 2:

Input:

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

Output:

31

(Giải thích: Tâm là số 7 hoặc 6 ở hàng 2 sẽ cho tổng lớn nhất khu vực 3x3 đó)

Cho một ma trận NxM chứa các số nguyên dương. Hai ô được gọi là liên thông nếu chúng có chung cạnh và cả hai đều chứa số nguyên tố. Một "vùng nguyên tố" là tập hợp các ô liên thông với nhau. Hãy tìm số lượng ô của "vùng nguyên tố" lớn nhất. (Lưu ý: Bài toán yêu cầu kiểm tra tính nguyên tố nhanh, cần sử dụng Sàng Eratosthenes).

Đầu vào:

Dòng 1: Hai số nguyên N, M.

N dòng tiếp theo: Ma trận A.

Đầu ra:

Diện tích (số lượng ô) của vùng nguyên tố lớn nhất.

Ràng buộc:

1 <= N, M <= 1000

1 <= A[i][j] <= 10^6 (Bắt buộc dùng sàng nguyên tố để không bị quá thời gian)

Ví dụ 1:

Input:

3 4 
2 3 5 4 
7 11 10 8 
13 4 2 2

Output:

6 

(Giải thích: Vùng 2-3-5-7-11-13 liên kết nhau)

Ví dụ 2:

Input:

3 3 
4 6 8 
9 10 12 
14 15 16

Output:

0

Sau trận mưa, trên sân kích thước NxM xuất hiện các vũng nước đọng. Số 1 biểu thị ô có nước, số 0 biểu thị ô đất khô. Hai ô nước được coi là cùng một "ao" nếu chúng liền kề nhau theo 4 hướng (trên, dưới, trái, phải). Hãy đếm số lượng ao nước trên sân.

Đầu vào:

Dòng 1: N, M.

N dòng tiếp theo: Các số 0 hoặc 1.

Đầu ra:

Số lượng ao.

Ràng buộc:

1 <= N, M <= 1000

Ví dụ 1:

Input:

3 4 
1 0 1 1 
1 0 0 1 
0 1 0 0

Output:

3

Ví dụ 2:

Input:

2 2 
1 1 
1 1

Output:

1

Mô tả: Xây dựng cấu trúc PhanSo gồm tử số và mẫu số. Hãy thực hiện các phép tính cộng, trừ, nhân, chia cho 2 phân số và in kết quả dưới dạng tối giản. Đặc biệt, chương trình phải xử lý được dấu âm (ví dụ mẫu số âm phải chuyển dấu lên tử) và rút gọn phân số sau mỗi phép tính.

Yêu cầu kỹ thuật:

1. Nạp chồng toán tử nhập >> và xuất << .

2. Nạp chồng các toán tử + , - , * , /.

3. Tự động rút gọn phân số khi khởi tạo hoặc sau khi tính toán.

Dữ liệu vào:

• Dòng duy nhất chứa 4 số nguyên a, b, c, d lần lượt là tử và mẫu của phân số thứ nhất, tử và mẫu của phân số thứ hai (b, d ‡ 0).

Giá trị: -10^9 <= a, b, c, d <= 10^9

Dữ liệu ra:

• 4 dòng lần lượt là kết quả của: Tổng, Hiệu, Tích, Thương.

Ví dụ:

Input:

1 2 3 4

Output:

5/4
-1/4
3/8
2/3

Mô tả: Một số nguyên dương X được gọi là Số P-Ước nếu số lượng các ước số dương của X là một số nguyên tố. Ví dụ:

Số 4 có các ước là {1, 2, 4}. Số lượng ước là 3 (là số nguyên tố) → 4 là số P-Ước.

Số 6 có các ước là {1, 2, 3, 6}. Số lượng ước là 4 (không phải số nguyên tố) → 6 không phải.

Số 12 có 6 ước (6 không phải nguyên tố) → Không phải.

Số 2 có 2 ước (2 là số nguyên tố) → Là số P-Ước.

Cho Q truy vấn, mỗi truy vấn gồm hai số nguyên L và R. Hãy đếm xem trong đoạn [L, R) có bao nhiêu số P-Ước.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên Q (1 ≤ Q < 10^5) - số lượng truy vấn.

• Q dòng tiếp theo, mỗi dòng chứa hai số nguyên L, R (1 ≤ L ≤ R ≤ 10^6).

Dữ liệu ra:

• Với mỗi truy vấn, in ra số lượng số P-Ước trong đoạn [L, R] trên một dòng.

Ràng buộc:

Thời gian giới hạn: 1 giây.

Bộ nhớ giới hạn: 256MB.

Ví dụ:

Input:

3
1 10
4 4
10 20

Output:

6
1
5

Cho ma trận NxM. Hãy tìm ô (i, j) sao cho tổng giá trị của nó và 4 ô xung quanh là một số có nhiều ước số nhất. In ra số lượng ước số đó.

Đầu vào:

Dòng 1: N, M.

N dòng tiếp theo: Ma trận A.

Đầu ra:

Số lượng ước số lớn nhất tìm được của tổng các vùng 5 ô (dấu cộng).

Ràng buộc:

1 <= N, M <= 500

1 <= A[i][j] <= 10^4

Tổng giá trị vùng 5 ô có thể lên tới 5*10^4.

Ví dụ 1:

Input:

3 3 
1 1 1 
1 10 1 
1 1 1

Output:

4 
(Giải thích: Ô giữa có tổng vùng là 1+1+10+1+1 = 14. Ước của 14 là 1, 2, 7, 14 -> 4 ước)

Ví dụ 2:

Input:

3 3 
2 2 2 
2 2 2 
2 2 2

Output:

4 
(Giải thích: Tổng là 10. Ước của 10 là 1, 2, 5, 10 -> 4 ước)

Nhập vào N là số nguyên, sinh ra tất cả các xâu nhị phân có N bít

Ràng buộc: 1 <= N <= 20;

Input:

4

Output:

0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

Cho N và K là các số nguyên (K <= N). Hãy sinh ra tổ hợp chập K của N

Ràng buộc: 1 <= K <= N <= 15

Input:

5 3

Output:

123
124
125
134
135
145
234
235
245
345