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

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

ĐỀ SỐ 17 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	Đếm số chia hết	`CHIAHET.*`	`CHIAHET.INP`	`CHIAHET.OUT`	3
2	Tần số chữ cái	`TANSOKT.*`	`TANSOKT.INP`	`TANSOKT.OUT`	5
3	Mua hai món quà	`CAPTONG.*`	`CAPTONG.INP`	`CAPTONG.OUT`	6
4	Đọc sách nhiều ngày nhất	`DAYCONMAX.*`	`DAYCONMAX.INP`	`DAYCONMAX.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. Đếm số chia hết (3 điểm)

Yêu cầu: Cho bốn số nguyên dương a, b, x, y. Đếm số lượng số nguyên trong đoạn [a, b] chia hết cho x hoặc chia hết cho y.

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

Kết quả: Ghi ra file văn bản CHIAHET.OUT một số nguyên là số lượng tìm được.

Ví dụ:

CHIAHET.INP	CHIAHET.OUT	Giải thích
`1 20 4 6`	`7`	Các số 4, 6, 8, 12, 16, 18, 20.

Ràng buộc:

Có 50% số test với b ≤ 10⁶.
Có 50% số test với b ≤ 10¹⁸.

Bài 2. Tần số chữ cái (5 điểm)

Cho một dòng văn bản S gồm chữ cái tiếng Anh, chữ số, dấu câu và dấu cách.

Yêu cầu: Thống kê số lần xuất hiện của từng chữ cái trong S, không phân biệt chữ hoa và chữ thường. Liệt kê các chữ cái có xuất hiện (viết in thường) theo số lần xuất hiện giảm dần; nếu bằng nhau thì theo thứ tự bảng chữ cái.

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

Kết quả: Ghi ra file văn bản TANSOKT.OUT: mỗi dòng ghi một chữ cái và số lần xuất hiện của nó, theo thứ tự đã nêu. Nếu S không có chữ cái nào thì ghi -1.

Ví dụ:

TANSOKT.INP	TANSOKT.OUT
`Hello World!`	`l 3` `o 2` `d 1` `e 1` `h 1` `r 1` `w 1`

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

Có 50% số test với L ≤ 1000.
Có 50% số test với L ≤ 10⁶.

Bài 3. Mua hai món quà (6 điểm)

Cửa hàng lưu niệm có n món quà, món thứ i giá a_i đồng. Bạn Lan có K đồng và muốn mua đúng hai món khác nhau để tặng hai người bạn.

Yêu cầu: Đếm số cách chọn hai món quà có tổng giá không vượt quá K.

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

Dòng đầu tiên chứa hai số nguyên dương n và K (K ≤ 2 × 10⁹).
Dòng thứ hai chứa n số nguyên dương a₁, a₂, …, a_n (a_i ≤ 10⁹).

Kết quả: Ghi ra file văn bản CAPTONG.OUT một số nguyên là số cách chọn.

Ví dụ:

CAPTONG.INP	CAPTONG.OUT	Giải thích
`5 10` `3 8 5 2 6`	`6`	Các cặp (3, 5), (3, 2), (3, 6), (8, 2), (5, 2), (2, 6).

Ràng buộc:

Có 40% số test với n ≤ 2000.
Có 60% số test với n ≤ 2 × 10⁵.

Bài 4. Đọc sách nhiều ngày nhất (6 điểm)

Bạn Minh lập kế hoạch đọc sách trong n ngày, ngày thứ i cần a_i phút. Minh có tổng cộng S phút rảnh và muốn chọn một chuỗi ngày liên tiếp dài nhất để đọc sách sao cho tổng thời gian cần dùng không vượt quá S.

Yêu cầu: Tìm độ dài lớn nhất của chuỗi ngày liên tiếp có tổng không vượt quá S, và ngày bắt đầu của chuỗi đó (nếu có nhiều chuỗi dài nhất thì chọn chuỗi bắt đầu sớm nhất).

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

Dòng đầu tiên chứa hai số nguyên n và S (n ≥ 1, 0 ≤ S ≤ 10¹⁵).
Dòng thứ hai chứa n số nguyên dương a₁, a₂, …, a_n (a_i ≤ 10⁹).

Kết quả: Ghi ra file văn bản DAYCONMAX.OUT hai số: độ dài lớn nhất và ngày bắt đầu (đánh số từ 1). Nếu không chọn được ngày nào thì ghi 0.

Ví dụ:

DAYCONMAX.INP	DAYCONMAX.OUT	Giải thích
`8 10` `3 1 4 1 5 9 2 6`	`4 1`	Bốn ngày đầu cần 3 + 1 + 4 + 1 = 9 phút.

Ràng buộc:

Có 40% số test với n ≤ 2000.
Có 60% số test với n ≤ 2 × 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