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

Cho số tự nhiên N. Hãy đếm xem N! (Giai thừa) có bao nhiêu chữ số 0 ở tận cùng.

Dữ liệu: N (N <= 10^9).

Kết quả: Số lượng số 0 tận cùng.

Ràng buộc: Không tính N! vì sẽ tràn số. Đếm số thừa số 5.

Ví dụ:

Ví dụ 1:

Input:

10

Output:

2

(10! = 3628800)

Ví dụ 2:

Input:

5

Output:

1

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

Tính tổ hợp chập k của n (C(n, k)) chia lấy dư cho 10^9 + 7.

Dữ liệu: n, k (k <= n <= 1000).

Kết quả: Kết quả C(n, k) % (10^9+7).

Ràng buộc: k <= n <= 1000.

Ví dụ:

Ví dụ 1:

Input:

4 2

Output:

6

Ví dụ 2:

Input:

5 0

Output:

1

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

Cho dãy số A. Hãy tìm độ dài của dãy con tăng dài nhất (các phần tử không nhất thiết phải liên tiếp).

Dữ liệu: n (n <= 1000) và dãy a.

Kết quả: Độ dài LIS.

Ràng buộc: n <= 1000.

Ví dụ:

Ví dụ 1:

Input:

6 
1 2 5 3 4 6

Output:

5

(Dãy: 1 2 3 4 6)

Ví dụ 2:

Input:

3 
3 2 1

Output:

1

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

Có n công việc, mỗi việc có thời gian bắt đầu và kết thúc. Hãy chọn được nhiều công việc nhất sao cho không có 2 việc nào bị trùng thời gian.

Dữ liệu: n và các cặp (start, end).

Kết quả: Số việc tối đa.

Ràng buộc: Tham lam (Sắp xếp theo thời gian kết thúc).

Ví dụ:

Ví dụ 1:

Input:

3 
1 3 
2 4 
3 5

Output:

2

(Chọn 1-3 và 3-5)

Ví dụ 2:

Input:

2 
1 10 
2 3

Output:

1

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

Cho ma trận NxM gồm các số nguyên dương. Tìm đường đi từ ô (1, 1) đến ô (N, M) sao cho tổng các số trên đường đi là nhỏ nhất. Chỉ được đi xuống hoặc sang phải.

Dữ liệu: N, M và ma trận.

Kết quả: Tổng nhỏ nhất.

Ràng buộc: 1 <= N, m <= 1000

Ví dụ:

Ví dụ 1:

Input:

2 2 
1 2 
3 4

Output:

7

(1 -> 2 -> 4)

Ví dụ 2:

Input:

2 3 
1 1 1 
9 9 1

Output:

4

(1->1->1->1)