BÀI 1: (4.0 điểm)

Số chính phương là số có thể viết dưới dạng bình phương của một số nguyên (ví dụ: 1, 4, 9, 16...). Cho hai số nguyên dương L và R. Hãy đếm xem trong đoạn [L, R] có bao nhiêu số chính phương.

Dữ liệu: Hai số nguyên L, R (1 <= L <= R <= 10^14).

Kết quả: Số lượng số chính phương trong đoạn [L, R].

Ràng buộc: Có 60% test L, R <= 10^6. Có 40% test R <= 10^14.

Ví dụ:

Ví dụ 1:

Input:

1 10

Output:

3

(Giải thích: Các số là 1, 4, 9)

Ví dụ 2:

Input:

10 20

Output:

1

(Giải thích: Chỉ có số 16)

BÀI 2: (4.0 điểm)

Cho n số nguyên dương. Hãy sắp xếp các số này và ghép chúng lại để tạo thành một số lớn nhất có thể. Ví dụ: Có 3 số {12, 121} -> Ghép lại được 12121 hoặc 12112. Số lớn nhất là 12121.

Dữ liệu: Dòng 1: n (n <= 10^5).

Dòng 2: n số nguyên dương a_i.

Kết quả: Số lớn nhất tạo được (dưới dạng xâu ký tự).

Ràng buộc: Các số a_i <= 10^9.

Ví dụ:

Ví dụ 1:

Input:

3 
1 20 3

Output:

3201

Ví dụ 2:

Input:

2 
9 90

Output:

990

BÀI 3: (4.0 điểm) MA TRẬN XOẮN ỐC Cho số nguyên dương N. Hãy in ra ma trận vuông kích thước NxN chứa các số từ 1 đến N^2 được sắp xếp theo hình xoắn ốc từ ngoài vào trong, bắt đầu từ ô (1, 1).

Dữ liệu: Số nguyên N (1 <= N <= 100).

Kết quả: Ma trận xoắn ốc.

Ràng buộc: N <= 100.

Ví dụ: Ví dụ 1:

Input:

3

Output:

1 2 3 
8 9 4 
7 6 5

Ví dụ 2:

Input:

2

Output:

1 2 
4 3

BÀI 4: (4.0 điểm)

Cho ma trận kích thước NxM chỉ gồm các số 0 và 1. Hãy tìm kích thước cạnh của hình vuông con lớn nhất chứa toàn số 1.

Dữ liệu: Dòng 1: N, M (N, M <= 1000). N dòng tiếp theo: Mỗi dòng M số 0 hoặc 1.

Kết quả: Độ dài cạnh hình vuông lớn nhất.

Ràng buộc: Dùng Quy hoạch động hoặc Duyệt thông minh.

Ví dụ:

Ví dụ 1:

Input:

3 3 
1 1 0 
1 1 0 
0 0 0

Output:

2

Ví dụ 2:

Input:

2 2 
1 0 
0 1

Output:

1

BÀI 5: (4.0 điểm)

Cho ma trận NxM. Một Robot xuất phát từ ô (1, 1) muốn đi đến ô (N, M). Mỗi bước Robot chỉ được đi xuống dưới hoặc đi sang phải. Hãy đếm số cách di chuyển khác nhau của Robot.

Dữ liệu: Dòng 1: N, M (1 <= N, M <= 20).

Kết quả: Số cách di chuyển.

Ràng buộc: Kết quả đảm bảo không quá 2 tỉ.

Ví dụ:

Ví dụ 1:

Input:

2 2

Output:

2

Ví dụ 2:

Input:

3 3

Output:

6