Kỳ thi chọn học sinh giỏi cấp Quốc gia THPT môn Tin học

(Bản scan)

Bài 1. SEQ198 (6 điểm)

Con số 198 có gợi cho bạn điều gì không? Khi học lịch sử Việt Nam, Vinh biết rằng ngày 19-8-
1945 là ngày Tổng khởi nghĩa, ngày nhân dân cả nước ta nhất tÈ đứng lên làm nên cuộc Cách
mạng Tháng Tám vĩ đại. Hiện nay, 198 được đặt tên cho nhiều bệnh viện, công viên, đường phố
trong cả nước. Con số này đã gợi ý cho Vinh khảo sát dãy số SEQ198 sau đây: Dãy số nguyên
không âm a, đa, ..., a„ được gọi là đãy SEQ198 nếu không tổn tại hai chỉ số ¡ và j (1 < i,j d; — a hoặc là bằng ! hoặc là bằng 8 hoặc là bằng 9.

Ví dụ:

e Dãy số nguyên 1, 3, 5, 7 là dãy SEQ198.

e Dãy số nguyên 7, 3, 5, 1, 9, 2! không phải là dãy SEQ198 bởi vì có hai phản tử 1 và 9 có
hiệu 9 - 1 = 8. Tuy nhiên, sau khi xoá bớt phần tử 1, ta thu được dãy 7, 3, 5, 9, 21 là một
dãy SEQ198.

Vinh quan tâm đến bài toán sau đây: Cho dãy số nguyên không âm b1, b2, ..., bm, hãy tìm cách loại
bỏ một số ít nhất phân từ của dãy để dãy còn lại là SEQ198.
Yêu cầu: Hãy giúp Vinh giải quyết bài toán đặt ra.