Đề test số 10
Đề 4 - Câu 1: Lũy thừa
Nộp bàiPoint: 4
BÀI 1: (4.0 điểm)
Tính (a mũ b) chia lấy dư cho c.
Dữ liệu: Ba số a, b, c (a, b, c <= 10^18).
Kết quả: Kết quả phép tính.
Ràng buộc: (a, b, c <= 10^18).
Ví dụ:
Ví dụ 1:
Input:
2 10 1000
Output:
24
Ví dụ 2:
Input:
3 3 10
Output:
7
Đề 4 - Câu 2: Đổi tiền
Nộp bàiPoint: 4
BÀI 2: (4.0 điểm)
Ngân hàng có các tờ tiền mệnh giá 1, 2, 5, 10, 20. Cần đổi số tiền N sao cho dùng ít tờ tiền nhất.
Dữ liệu: Số N (N <= 10^9).
Kết quả: Số tờ tiền ít nhất.
Ràng buộc: Luôn đổi được vì có tờ 1 đồng.
Ví dụ:
Ví dụ 1:
Input:
28
Output:
4
Ví dụ 2:
Input:
6
Output:
2
Đề 4 - Câu 3: Bậc thang
Nộp bàiPoint: 4
BÀI 3: (4.0 điểm)
Có n bậc thang. Mỗi bước có thể lên 1 hoặc 2 bậc. Hỏi có bao nhiêu cách để leo lên đỉnh?
Dữ liệu: Số n (n <= 90).
Kết quả: Số cách leo.
Ràng buộc: Kết quả có thể lớn, cần dùng kiểu long long.
Ví dụ:
Ví dụ 1:
Input:
3
Output:
3
Ví dụ 2:
Input:
4
Output:
5
Đề 4 - Câu 4: Xâu chung
Nộp bàiPoint: 4
BÀI 4: (4.0 điểm)
Cho 2 xâu S1 và S2. Tìm độ dài xâu con chung dài nhất (LCS - Longest Common Subsequence).
Dữ liệu: S1 và S2 (độ dài <= 2000).
Kết quả: Độ dài LCS.
Ràng buộc: S1 và S2 có độ dài <= 2000.
Ví dụ:
Ví dụ 1:
Input:
ABCDE ACE
Output:
3
Ví dụ 2:
Input:
ABC DEF
Output:
0
Đề 4 - Câu 5: Tổng Max
Nộp bàiPoint: 4
BÀI 5: (4.0 điểm)
Cho dãy số A gồm các số nguyên (có thể âm). Tìm tổng lớn nhất của một dãy con liên tiếp.
Dữ liệu: n (n <= 10^6) và dãy a.
Kết quả: Tổng lớn nhất.
Ràng buộc: n <= 10^6
Ví dụ:
Ví dụ 1:
Input:
9
-2 1 -3 4 -1 2 1 -5 4
Output:
6
Ví dụ 2:
Input:
3
-1 -2 -3
Output:
-1