Đề Thi Olympic Tin Học 10 Sở GD&ĐT Quảng Nam [năm 2021]

TỔNG QUAN ĐỀ THI TỔNG QUAN ĐỀ BÀI

Dấu * được thay thế bởi PAS hoặc CPP của ngôn ngữ lập trình được sử dụng tương ứng là Pascal hoặc C++.

Hãy lập trình giải các bài toán sau:

Bài 1. Chia hết cho 3 (5 điểm)

Cho một số tự nhiên N (N<10³²).

Yêu cầu: Hãy cho biết N có chia hết cho 3 không?

Nếu N chia hết cho 3 thì ghi ra “YES”, ngược lại nếu N không chia hết cho 3 thì ghi ra “NO”.

Dữ liệu vào: Từ tệp văn bản CHIAHET3.INP gồm một số N;

Kết quả: Ghi ra tệp văn bản CHIAHET3.OUT chữ “YES” hoặc “NO”.

Ví dụ:

CHIAHET3.INP	CHIAHET3.OUT
123	YES
1234	NO

Ràng buộc:

• Có 60% test ứng 60% số điểm của bài với N ≤ 10⁶;

• Có 20% test ứng 20% số điểm của bài với N ≤ 10¹⁸;

• Có 20% test khác ứng với 20% số điểm còn lại của bài với N < 10³².

Bài 2. Số nguyên tố đặc biệt (5 điểm)

Nam rất yêu thích số nguyên tố vì vậy cậu ta thường sưu tầm các số nguyên tố. Lần này bộ sưu tập của Nam là những số nguyên tố đặc biệt, tức là những số nguyên tố đó có tổng các chữ số của nó lại là số nguyên tố.

Yêu cầu: Hãy liệt kê ra tất cả các số nguyên tố đặc biệt nhỏ hơn hoặc bằng N theo thứ tự tăng dần.

Dữ liệu vào: Từ tệp văn bản SPECPRIME.INP gồm 1 dòng chứa số N;      

Kết quả: Ghi ra tệp văn bản SPECPRIME.OUT các số nguyên tố đặc biệt nhỏ hơn hoặc bằng N theo thứ tự tăng dần.

Ví dụ:

SPECPRIME.INP	SPECPRIME.OUT
20	2 3 5 7 11

Ràng buộc:

• Có 60% test ứng 60% số điểm của bài với N ≤ 10⁶;

• Có 40% test ứng 40% số điểm của bài với N ≤ 10⁹;

Bài 3. Nén xâu (5 điểm)

Trong máy tính, để tiết kiệm bộ nhớ người ta thường tìm cách nén dữ liệu. Một xâu ký tự có thể nén lại thành một xâu mới bằng cách nén các ký tự giống nhau đứng cạnh nhau.

Ví dụ: Xâu aaaa sẽ nén thành 4a.

Yêu cầu: Hãy lập trình để nén một xâu ký tự thường theo cách trên.

Dữ liệu vào: Từ tệp văn bản NENXAU.INP, gồm một xâu các ký tự là chữ cái in thường.

Kết quả: Ghi ra tệp văn bản NENXAU.OUT, gồm một xâu ký tự sau khi nén.

Ví dụ:

NENXAU.INP	NENXAU.OUT
mmaabbbeeeezh	2m2a3b4ezh

Ràng buộc:

• Có 50% test ứng 50% số điểm của bài có độ dài xâu ≤ 255;

• Có 20% test ứng 20% số điểm của bài có độ dài xâu ≤ 10³;

• Có 30% test ứng 30% số điểm của bài có độ dài xâu ≤ 10⁵;

Bài 4. Số tự nhiên nhỏ nhất (5 điểm)

Mai và Lan là đôi bạn thân, Mai đang tìm cách giải một bài toán liên quan tới số tự nhiên. Lúc này, Mai đang rất cần sự giúp đỡ của Lan. Thử thách lần này là một dãy gồm N số tự nhiên bất kỳ nằm trong đoạn từ 0 tới 10⁶. Hãy viết chương trình tìm số tự nhiên nhỏ nhất không có trong dãy số đó. Vì số lượng các số tự nhiên trong dãy số đã cho có thể rất lớn nên việc tìm thủ công là không thể. Chính vì vậy, Mai cần một thuật toán để cài đặt vào máy tính và nhờ máy tính tìm giúp.

Các em hãy giúp đỡ hai bạn giải quyết bài toán nhé.

Yêu cầu: Cho một dãy A gồm N số tự nhiên. Hãy tìm số tự nhiên nhỏ nhất không xuất hiện trong dãy đó.

Dữ liệu vào :  Từ tệp văn bản SOMIN.INP gồm một dãy N số tự nhiên;

Dữ liệu ra : Ghi ra tệp văn bản SOMIN.OUT gồm duy nhất 1 số thỏa mãn yêu cầu.

Ví dụ:

SOMIN.INP	SOMIN.OUT
5 4 3 6 1 2	0
2 4 0 3 1 2 6 2 8 5	7

Ràng buộc:

• Có 80% test ứng 80% số điểm của bài với N ≤ 10⁴, 0 ≤ a_i ≤ 10⁶;

• Có 20% test ứng với 20% số điểm của bài với N ≤ 10⁶, 0 ≤ a_i ≤ 10⁹ .

–––––––––––– Hết ––––––––––––

Họ và tên thí sinh: …..…………………………………. Số báo danh: ………………

Bài 1: (5 điểm) Mỗi TEST đúng cho 0,25 điểm. Thời gian chạy 1s/ 1test.

TEST	CHIAHET3.INP	CHIAHET3.OUT
1	1111	NO
2	1234	NO
3	546	YES
4	207306	YES
…	CHIAHET3.INP	CHIAHET3.OUT
20	CHIAHET3.INP	CHIAHET3.OUT

Bài 2: (5 điểm) Mỗi TEST đúng cho 0,25 điểm. Thời gian chạy 1s/ 1test.

TEST	SPECPRIME.INP	SPECPRIME.OUT
1	20	2 3 5 7 11
2	50	2 3 5 7 11 23 29 41 43 47
3	100	2 3 5 7 11 23 29 41 43 47 61 67 83 89
…	SPECPRIME.INP	SPECPRIME.OUT
20	SPECPRIME.INP	SPECPRIME.OUT

Bài 3: (5 điểm) Mỗi TEST đúng cho 0,5 điểm. Thời gian chạy 1s/ 1test.

TEST	NENXAU.INP	NENXAU.OUT
1	fyyqagcodnbsyjiuadft	f2yqagcodnbsyjiuadft
2	nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb	48n43b
3	NENXAU.INP	NENXAU.OUT
…	NENXAU.INP	NENXAU.OUT
20	NENXAU.INP	NENXAU.OUT

Bài 4: (5 điểm) Mỗi TEST đúng cho 0,25 điểm. Thời gian chạy 1s/ 1test.

TEST	SOMIN.INP	SOMIN.OUT
1	49 21 26 55 55 7 1 44 20 55 50 40 20 36 52 45 33 11 24 53 13 4 34 50 50 39 30 23 40 7 21 24 48 13 21 4 35 48 2 18 19 38 9 21 22 17 27 14 41 26 21 52 4 10 19 11 39 19 37 24 48 1 10 15 35 25 36 57 8 27 7 12 47 11 43 34 2 27 58 8 36 16 40 15 52 23 27 4 10 41 53 34 29 30 26 15 16 18 1 23	0
2	6 45 50 26 45 2 27 55 21 27 44 19 53 23 54 2 5 26 26 40 32 25 46 39 16 17 25 23 23 53 0 55 53 14 41 59 26 49 13 42 39 56 41 19 27 11 36 52 32 19 42 15 13 10 38 11 1 28 21 3 46 9 27 10 26 17 5 50 46 15 11 3 36 9 35 50 0 42 57 0 10 18 14 5 30 57 27 6 49 29 31 22 40 11 41 54 9 4 4 7	8
3	SOMIN.INP	SOMIN.OUT
…	SOMIN.INP	SOMIN.OUT
20	SOMIN.INP	SOMIN.OUT

------------------------------------HẾT----------------------------------