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

Cho số nguyên n. Hãy in ra số lượng các số nguyên tố nhỏ hơn hoặc bằng n.

Dữ liệu: Số n (n <= 10^7).

Kết quả: Số lượng số nguyên tố.

Ràng buộc: Thời gian chạy 1 giây.

Ví dụ:

Ví dụ 1:

Input:

10

Output:

4

Ví dụ 2:

Input:

20

Output:

8

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

Một bức tường dài L mét. Có n thợ sơn, thợ thứ i sơn từ mét ai đến mét bi. Hỏi có bao nhiêu mét tường được sơn ít nhất 1 lần?

Dữ liệu:

Số n (n <= 10^5).

Các dòng sau chứa cặp ai, bi (0 <= ai < bi <= 10^6).

Kết quả: Tổng độ dài được sơn.

Ràng buộc: Các đoạn có thể chồng chéo lên nhau.

Ví dụ:

Ví dụ 1:

Input:

2 
1 5 
3 7

Output:

6

Ví dụ 2:

Input:

2 
1 3 
5 7

Output:

4

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

Cho dãy số A đã sắp xếp tăng dần. Hãy tìm hai số có tổng bằng X. Nếu có nhiều cặp, in ra cặp đầu tiên tìm thấy. Nếu không có in -1.

Dữ liệu: n (n <= 10^6), X và dãy a.

Kết quả: Hai số tìm được hoặc -1.

Ràng buộc: Dãy a đã sắp xếp tăng dần.

Ví dụ:

Ví dụ 1:

Input:

5 10 
1 4 5 6 9

Output:

1 9

Ví dụ 2:

Input:

4 10 
1 2 3 4

Output:

-1

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

Cho dãy địa hình A gồm n điểm có độ cao khác nhau. Một đoạn đường được gọi là "dốc đều" nếu chênh lệch độ cao giữa 2 điểm liên tiếp luôn bằng nhau (tạo thành cấp số cộng). Tìm độ dài đoạn con dốc đều dài nhất.

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

Kết quả: Độ dài lớn nhất (số lượng phần tử).

Ràng buộc: Nếu không có đoạn nào dài hơn 2, in ra 1 hoặc 2 tùy theo n.

Ví dụ:

Ví dụ 1:

Input:

5 
1 3 5 7 8

Output:

4

Ví dụ 2:

Input:

4 
1 2 4 8

Output:

2

Người xưa nói rằng: 'Số 6 là lộc, số 8 là phát, còn số 9 là trường cửu – bền lâu, vững vàng'

Vì thế, trong truyền thuyết của thế giới số học, người ta tin rằng nếu một con số chỉ gồm 6, 8 và 9, thì đó chính là số lộc phát trường cửu – mang may mắn, tài lộc và sự thịnh vượng dài lâu.

Bạn hãy viết chương trình kiểm tra xem một số nguyên dương N có phải là số tài lộc phát 6–8–9 hay không

Dữ liệu đầu vào: Nhập vào một số nguyên dương N có độ dài không quá 100 chữ số.

Dữ liệu đầu ra: In ra 'YES' nếu số nhập vào là số tài lộc phát, in ra 'NO' nếu không phải

Ví dụ:

Input 01:

686889

Output 01:

YES

Input 02:

886089

Output 02:

NO

50% số điểm ứng với các test có 1 ≤ N ≤ 10^18

50% số điểm còn lại không có ràng buộc bố sung

Viết chương trình cho phép nhập vào hai số nguyên dương và tìm tất cả các số Strong (là số có tổng giai thừa các chữ số bằng chính nó) nằm trong khoảng đó (nếu không tồn tại số nào thì in ra 0).

INPUT:

1 1000

OUTPUT:

1 2 145

Giới hạn thời gian: 1 giây Giới hạn bộ nhớ: 256 MB Dữ liệu vào: Hai số nguyên dương A và B (1 nhỏ hơn hoặc bằng A nhỏ hơn hoặc bằng B).

Phân bố điểm chi tiết:

Subtask 1 (chiếm 30% số điểm): B nhỏ hơn hoặc bằng 1000. Gợi ý: Thí sinh cần tìm các số Strong nhỏ (1, 2, 145).

Subtask 2 (chiếm 30% số điểm): B nhỏ hơn hoặc bằng 10000. Gợi ý: Phạm vi này yêu cầu kiểm tra hiệu suất của thuật toán tính tổng giai thừa các chữ số.

Subtask 3 (chiếm 40% số điểm): B nhỏ hơn hoặc bằng 50000. Gợi ý: Giới hạn này bao gồm số Strong lớn nhất đã biết (40585), yêu cầu độ chính xác và khả năng tối ưu (sử dụng bảng tra cứu giai thừa).