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

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

ĐỀ SỐ 04 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	Tiền xe công nghệ	`TIENXE.*`	`TIENXE.INP`	`TIENXE.OUT`	4
2	Phép tính phân số	`PHANSO.*`	`PHANSO.INP`	`PHANSO.OUT`	5
3	Số nguyên tố theo tổng chữ số	`NTCS.*`	`NTCS.INP`	`NTCS.OUT`	5
4	Chữ số thứ k	`CHUSOK.*`	`CHUSOK.INP`	`CHUSOK.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. Tiền xe công nghệ (4 điểm)

Một hãng xe công nghệ tính tiền theo quãng đường n km (n nguyên dương) như sau:

Quãng đường	Đơn giá
Km đầu tiên	10 000 đồng
Từ km thứ 2 đến km thứ 10	9 000 đồng/km
Từ km thứ 11 trở đi	8 000 đồng/km

Ngoài ra, chuyến đi dài hơn 50 km được giảm 10% trên tổng số tiền.

Yêu cầu: Tính số tiền khách phải trả cho chuyến đi n km.

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

Kết quả: Ghi ra file văn bản TIENXE.OUT một số nguyên là số tiền phải trả (đồng).

Ví dụ:

TIENXE.INP	TIENXE.OUT	Giải thích
`9`	`82000`	10 000 + 8 × 9 000 = 82 000.
`70`	`513900`	10 000 + 9 × 9 000 + 60 × 8 000 = 571 000, giảm 10% còn 513 900.

Ràng buộc:

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

Bài 2. Phép tính phân số (5 điểm)

Cho hai phân số a/b và c/d với a, b, c, d là các số nguyên dương.

Yêu cầu: Tính tổng S = a/b + c/d và thương Q = a/b : c/d, viết dưới dạng phân số tối giản.

Dữ liệu vào: Từ file văn bản PHANSO.INP gồm một dòng chứa bốn số nguyên dương a, b, c, d.

Kết quả: Ghi ra file văn bản PHANSO.OUT gồm hai dòng lần lượt là S và Q. Mỗi kết quả ghi dưới dạng tử/mẫu đã tối giản; nếu mẫu số bằng 1 thì chỉ ghi tử số.

Ví dụ:

PHANSO.INP	PHANSO.OUT	Giải thích
`3 4 5 6`	`19/12` `9/10`	3/4 + 5/6 = 19/12; 3/4 : 5/6 = 18/20 = 9/10.
`1 2 3 6`	`1` `1`	1/2 + 3/6 = 1 và 1/2 : 3/6 = 1.

Ràng buộc:

Có 50% số test với a, b, c, d ≤ 1000.
Có 50% số test với a, b, c, d ≤ 10⁹.

Bài 3. Số nguyên tố theo tổng chữ số (5 điểm)

Cho hai số nguyên dương m và s.

Yêu cầu: Đếm số lượng số nguyên tố không vượt quá m có tổng các chữ số bằng s, và tìm số lớn nhất trong các số đó.

Dữ liệu vào: Từ file văn bản NTCS.INP gồm một dòng chứa hai số nguyên dương m, s (s ≤ 100).

Kết quả: Ghi ra file văn bản NTCS.OUT gồm hai dòng: dòng thứ nhất ghi số lượng số nguyên tố tìm được; dòng thứ hai ghi số lớn nhất trong đó, nếu không có số nào thì ghi -1.

Ví dụ:

NTCS.INP	NTCS.OUT	Giải thích
`30 5`	`2` `23`	Các số nguyên tố không vượt quá 30 có tổng chữ số bằng 5 là 5 và 23.
`100 9`	`0` `-1`	Số có tổng chữ số bằng 9 thì chia hết cho 9 nên không là số nguyên tố.

Ràng buộc:

Có 40% số test với m ≤ 10⁴.
Có 60% số test với m ≤ 5 × 10⁶.

Bài 4. Chữ số thứ k (6 điểm)

Viết liên tiếp các số nguyên dương 1, 2, 3, … thành một dãy chữ số vô hạn:

123456789101112131415161718192021…

Yêu cầu: Cho số nguyên dương k, hãy cho biết chữ số ở vị trí thứ k của dãy (vị trí được đánh số từ 1) và chữ số đó thuộc số nào.

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

Kết quả: Ghi ra file văn bản CHUSOK.OUT gồm hai số cách nhau một dấu cách: chữ số ở vị trí thứ k và số chứa chữ số đó.

Ví dụ:

CHUSOK.INP	CHUSOK.OUT	Giải thích
`11`	`0 10`	Các vị trí 10, 11 là hai chữ số của số 10.
`190`	`1 100`	9 số có một chữ số và 90 số có hai chữ số chiếm 189 vị trí; vị trí 190 là chữ số đầu của 100.

Ràng buộc:

Có 40% số test với k ≤ 10⁶.
Có 60% số test với k ≤ 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