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

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

ĐỀ SỐ 27 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 công theo giờ	GIOLAM.*	GIOLAM.INP	GIOLAM.OUT	4
2	Đảo chữ	ANAGRAM.*	ANAGRAM.INP	ANAGRAM.OUT	5
3	Bộ ba có tổng bằng 0	BOBA0.*	BOBA0.INP	BOBA0.OUT	5
4	Đoạn ổn định	DOANDEU.*	DOANDEU.INP	DOANDEU.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 công theo giờ (4 điểm)

Một công nhân làm việc n ngày. Mỗi ngày anh chấm công lúc vào và lúc ra (trong cùng một ngày). Trong mỗi ngày, 8 giờ (480 phút) làm việc đầu tiên được trả a đồng mỗi phút, các phút làm vượt quá 8 giờ được trả b đồng mỗi phút (tiền tăng ca).

Yêu cầu: Tính tổng thời gian làm việc (giờ và phút) và tổng tiền công của n ngày.

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

• Dòng đầu tiên chứa ba số nguyên dương n, a, b (a ≤ b ≤ 10⁴).
• n dòng tiếp theo, mỗi dòng chứa giờ vào và giờ ra dạng hh:mm hh:mm (giờ ra không sớm hơn giờ vào).

Kết quả: Ghi ra file văn bản GIOLAM.OUT gồm hai dòng: số giờ và số phút của tổng thời gian làm việc; tổng tiền công.

Ví dụ:

GIOLAM.INP	GIOLAM.OUT	Giải thích
3 1000 1500 07:30 17:00 08:00 12:00 13:15 22:45	23 0 1470000	Ngày 1 và ngày 3 mỗi ngày làm 570 phút: 480 × 1000 + 90 × 1500 = 615 000 đồng. Ngày 2 làm 240 phút: 240 000 đồng.

Ràng buộc:

• Có 50% số test với n ≤ 100.
• Có 50% số test với n ≤ 10⁵.

Bài 2. Đảo chữ (5 điểm)

Hai từ được gọi là đảo chữ của nhau nếu có thể đổi chỗ các chữ cái của từ này để được từ kia. Ví dụ listen và silent là đảo chữ của nhau.

Yêu cầu: Cho n từ, đếm số cặp từ (i, j) với i nhỏ hơn j là đảo chữ của nhau, và cho biết nhóm lớn nhất gồm các từ đôi một là đảo chữ của nhau có bao nhiêu từ.

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

• Dòng đầu tiên chứa số nguyên dương n.
• n dòng tiếp theo, mỗi dòng chứa một từ gồm không quá 20 chữ cái in thường (các từ có thể trùng nhau).

Kết quả: Ghi ra file văn bản ANAGRAM.OUT gồm hai dòng: số cặp đảo chữ và số từ của nhóm lớn nhất.

Ví dụ:

ANAGRAM.INP	ANAGRAM.OUT	Giải thích
6 listen silent enlist google inlets gogole	7 4	Nhóm listen, silent, enlist, inlets cho 6 cặp; nhóm google, gogole cho 1 cặp.

Ràng buộc:

• Có 40% số test với n ≤ 1000.
• Có 60% số test với n ≤ 10⁵.

Bài 3. Bộ ba có tổng bằng 0 (5 điểm)

Yêu cầu: Cho dãy n số nguyên a₁, a₂, …, a_n, đếm số bộ ba chỉ số (i, j, k) với i nhỏ hơn j, j nhỏ hơn k sao cho a_i + a_j + a_k = 0.

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

• Dòng đầu tiên chứa số nguyên n (n ≥ 3).
• Dòng thứ hai chứa n số nguyên a₁, a₂, …, a_n (|a_i| ≤ 10⁹).

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

Ví dụ:

BOBA0.INP	BOBA0.OUT	Giải thích
6 -1 0 1 2 -1 -4	3	Hai bộ (−1, 0, 1) (dùng số −1 ở vị trí 1 hoặc vị trí 5) và bộ (−1, 2, −1).

Ràng buộc:

• Có 40% số test với n ≤ 100.
• Có 60% số test với n ≤ 1500.

Bài 4. Đoạn ổn định (6 điểm)

Một cảm biến ghi lại n giá trị đo liên tiếp a₁, a₂, …, a_n. Một đoạn các lần đo liên tiếp được gọi là ổn định nếu giá trị lớn nhất và giá trị nhỏ nhất trong đoạn chênh nhau không quá K.

Yêu cầu: Đếm số đoạn liên tiếp (gồm ít nhất một phần tử) ổn định.

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

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

Kết quả: Ghi ra file văn bản DOANDEU.OUT một số nguyên là số đoạn ổn định.

Ví dụ:

DOANDEU.INP	DOANDEU.OUT	Giải thích
5 2 4 2 5 3 8	7	5 đoạn một phần tử, cùng các đoạn (4, 2) và (5, 3).

Ràng buộc:

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

Lời giải và bộ test của đề này (có phí)

Hướng dẫn giải chi tiết, code Python và C++ đã được kiểm chứng, cùng bộ test và công cụ chấm cham.py, có trong bộ tài liệu đầy đủ (có phí).

Thầy cô và các em muốn mua bộ tài liệu vui lòng liên hệ tác giả qua Zalo 0972465159 hoặc Facebook.

Muốn xem trước cách trình bày lời giải, hãy xem Đề số 01 (có lời giải miễn phí).

Do số lượng đề bài, bài giải và bộ test rất nhiều nên tác giả đang kiểm tra từng bước. Thầy cô và các em học sinh nếu thấy sai sót xin vui lòng liên hệ tác giả qua Facebook hoặc Zalo (0972465159). Xin chân thành cảm ơn.