Đề số 09 - Ôn thi HSG Tin học THCS

BỘ ĐỀ ÔN THI HỌC SINH GIỎI TIN HỌC THCS Bumbii Academy

ĐỀ SỐ 09 Thời gian làm bài: 150 phút
4 bài, tổng 20 điểm

Tổng quan đề thi

Bài	Tên bài	File chương trình	File dữ liệu vào	File kết quả	Điểm
1	Tổng xen dấu	`TONGXEN.*`	`TONGXEN.INP`	`TONGXEN.OUT`	4
2	Điền xâu đối xứng	`PALIN.*`	`PALIN.INP`	`PALIN.OUT`	5
3	Cặp số nguyên tố gần nhau	`GOLDBACH.*`	`GOLDBACH.INP`	`GOLDBACH.OUT`	5
4	Số siêu nguyên tố	`SIEUNT.*`	`SIEUNT.INP`	`SIEUNT.OUT`	6

Dấu * được thay bằng py hoặc cpp tùy theo ngôn ngữ lập trình sử dụng.

Bài 1. Tổng xen dấu (4 điểm)

Cho số nguyên dương n. Tính tổng

S = 1 + 2 − 3 + 4 + 5 − 6 + 7 + 8 − 9 + … (đến số hạng thứ n)

trong đó các số chia hết cho 3 mang dấu trừ, các số còn lại mang dấu cộng.

Dữ liệu vào: Từ file văn bản TONGXEN.INP gồm một số nguyên dương n.

Kết quả: Ghi ra file văn bản TONGXEN.OUT một số nguyên là giá trị S.

Ví dụ:

TONGXEN.INP	TONGXEN.OUT	Giải thích
`5`	`9`	1 + 2 − 3 + 4 + 5 = 9.
`7`	`10`	1 + 2 − 3 + 4 + 5 − 6 + 7 = 10.

Ràng buộc:

Có 50% số test với n ≤ 10⁶.
Có 50% số test với n ≤ 10⁹.

Bài 2. Điền xâu đối xứng (5 điểm)

Xâu đối xứng là xâu đọc từ trái sang phải hay từ phải sang trái đều giống nhau. Cho xâu S gồm các chữ cái in hoa A…Z và dấu ?. Cần thay mỗi dấu ? bằng một chữ cái in hoa để được một xâu đối xứng.

Yêu cầu: Tìm xâu đối xứng có thứ tự từ điển nhỏ nhất tạo được, hoặc cho biết không thể tạo được.

Dữ liệu vào: Từ file văn bản PALIN.INP gồm một dòng chứa xâu S.

Kết quả: Ghi ra file văn bản PALIN.OUT xâu đối xứng tìm được, hoặc -1 nếu không thể tạo được xâu đối xứng.

Ví dụ:

PALIN.INP	PALIN.OUT	Giải thích
`DE???D`	`DEAAED`	Vị trí thứ 5 phải bằng E; hai dấu ? ở giữa chọn chữ A nhỏ nhất.
`MH??GM`	`-1`	Chữ H ở vị trí 2 và chữ G ở vị trí 5 không thể bằng nhau.

Ràng buộc: Gọi L là độ dài xâu S.

Có 30% số test với L ≤ 10 và S có không quá 3 dấu ?.
Có 70% số test với L ≤ 10⁶.

Bài 3. Cặp số nguyên tố gần nhau (5 điểm)

Giả thuyết Goldbach nói rằng mọi số chẵn lớn hơn 2 đều viết được thành tổng của hai số nguyên tố. Ví dụ 22 = 3 + 19 = 5 + 17 = 11 + 11.

Yêu cầu: Cho q số chẵn, với mỗi số a hãy tìm hai số nguyên tố p ≤ q’ có tổng bằng a và gần nhau nhất (hiệu q’ − p nhỏ nhất).

Dữ liệu vào: Từ file văn bản GOLDBACH.INP gồm:

Dòng đầu tiên chứa số nguyên dương q.
q dòng tiếp theo, mỗi dòng chứa một số chẵn a (a ≥ 4).

Kết quả: Ghi ra file văn bản GOLDBACH.OUT gồm q dòng, mỗi dòng hai số p và q’ tìm được (p ≤ q’).

Ví dụ:

GOLDBACH.INP	GOLDBACH.OUT	Giải thích
`3` `22` `72` `18`	`11 11` `31 41` `7 11`	72 = 31 + 41, không có cặp nào có hiệu nhỏ hơn 10.

Dữ liệu các test đều thỏa mãn giả thuyết Goldbach (luôn có đáp án).

Ràng buộc:

Có 40% số test với q ≤ 100, a ≤ 10⁴.
Có 60% số test với q ≤ 5 × 10⁴, a ≤ 10⁶.

Bài 4. Số siêu nguyên tố (6 điểm)

Số siêu nguyên tố là số nguyên tố mà khi xóa đi một số tùy ý các chữ số ở bên phải thì phần còn lại vẫn là số nguyên tố. Ví dụ 3137 là số siêu nguyên tố vì 3137, 313, 31, 3 đều là số nguyên tố.

Yêu cầu: Cho q đoạn [L, R], với mỗi đoạn hãy đếm số lượng số siêu nguyên tố thuộc đoạn đó.

Dữ liệu vào: Từ file văn bản SIEUNT.INP gồm:

Dòng đầu tiên chứa số nguyên dương q.
q dòng tiếp theo, mỗi dòng chứa hai số nguyên L, R (1 ≤ L ≤ R).

Kết quả: Ghi ra file văn bản SIEUNT.OUT gồm q dòng, dòng thứ i là số lượng số siêu nguyên tố trong đoạn thứ i.

Ví dụ:

SIEUNT.INP	SIEUNT.OUT	Giải thích
`2` `1 100` `3100 3200`	`13` `2`	Đoạn [1, 100] có 2, 3, 5, 7, 23, 29, 31, 37, 53, 59, 71, 73, 79. Đoạn [3100, 3200] có 3119 và 3137.

Ràng buộc:

Có 40% số test với q ≤ 10, R ≤ 10⁴.
Có 60% số test với q ≤ 10⁵, R ≤ 10⁹.

Th.S Trần Huy Phúc

Kỹ sư phần mềm @Adnovum & Bumbii Academy

Học Tiếng Anh với Bumbii English