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

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

ĐỀ SỐ 13 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	Trâu ăn cỏ	`TRAMTRAU.*`	`TRAMTRAU.INP`	`TRAMTRAU.OUT`	4
2	Mua bút khuyến mãi	`MUABUT.*`	`MUABUT.INP`	`MUABUT.OUT`	5
3	Số gần nhất	`GANNHAT.*`	`GANNHAT.INP`	`GANNHAT.OUT`	5
4	Chuỗi ngày lãi nhất	`DOANMAX.*`	`DOANMAX.INP`	`DOANMAX.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. Trâu ăn cỏ (4 điểm)

Bài toán dân gian “Trăm trâu trăm cỏ” được mở rộng như sau: có a con trâu ăn hết b bó cỏ, trong đó mỗi trâu đứng ăn 5 bó, mỗi trâu nằm ăn 3 bó, và cứ 3 trâu già ăn chung 1 bó. Đàn trâu có đủ cả ba loại (mỗi loại ít nhất một con).

Yêu cầu: Cho biết bài toán có bao nhiêu nghiệm (số trâu đứng, nằm, già), và nghiệm có ít trâu đứng nhất.

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

Kết quả: Ghi ra file văn bản TRAMTRAU.OUT: dòng thứ nhất ghi số nghiệm; nếu có nghiệm thì dòng thứ hai ghi số trâu đứng, trâu nằm, trâu già của nghiệm có ít trâu đứng nhất.

Ví dụ:

TRAMTRAU.INP	TRAMTRAU.OUT	Giải thích
`100 100`	`3` `4 18 78`	Ba nghiệm (4, 18, 78), (8, 11, 81), (12, 4, 84).

Ràng buộc:

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

Bài 2. Mua bút khuyến mãi (5 điểm)

Một quầy tạp hóa bán bút với giá m đồng một chiếc, và có chương trình khuyến mãi: cứ mua n chiếc bút thì được tặng thêm 1 chiếc.

Yêu cầu:

Tính số tiền S ít nhất phải trả để được tặng đúng p chiếc bút.
Tính số tiền T ít nhất phải trả để có (tính cả bút mua và bút được tặng) ít nhất k chiếc bút.

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

Kết quả: Ghi ra file văn bản MUABUT.OUT gồm hai dòng: S và T.

Ví dụ:

MUABUT.INP	MUABUT.OUT	Giải thích
`6 5 3 20`	`90` `102`	Mua 15 chiếc (90 đồng) được tặng 3 chiếc. Mua 17 chiếc (102 đồng) được tặng 3 chiếc, có tổng 20 chiếc.

Ràng buộc:

Có 50% số test với k ≤ 10⁶ và n × p ≤ 10⁶.
Có 50% số test với k ≤ 10¹².

Bài 3. Số gần nhất (5 điểm)

Cho dãy n số nguyên a₁, a₂, …, a_n và q câu hỏi. Câu hỏi thứ j cho một số nguyên k_j.

Yêu cầu: Với mỗi câu hỏi, tìm số trong dãy gần k_j nhất (|a_i − k_j| nhỏ nhất); nếu có hai số cách đều thì chọn số nhỏ hơn.

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

Dòng đầu tiên chứa hai số nguyên dương n và q.
Dòng thứ hai chứa n số nguyên a₁, a₂, …, a_n.
q dòng tiếp theo, mỗi dòng chứa một số nguyên k_j.

Các số trong dữ liệu có giá trị tuyệt đối không quá 10⁹.

Kết quả: Ghi ra file văn bản GANNHAT.OUT gồm q dòng là câu trả lời cho các câu hỏi.

Ví dụ:

GANNHAT.INP	GANNHAT.OUT	Giải thích
`5 3` `1 9 4 12 7` `10` `8` `-5`	`9` `7` `1`	8 cách đều 7 và 9, chọn số nhỏ hơn là 7.

Ràng buộc:

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

Bài 4. Chuỗi ngày lãi nhất (6 điểm)

Một cửa hàng ghi lại tiền lãi của n ngày liên tiếp, ngày thứ i lãi a_i nghìn đồng (a_i âm nghĩa là ngày đó bị lỗ). Chủ cửa hàng muốn tìm một chuỗi ngày liên tiếp dài ít nhất L ngày có tổng tiền lãi lớn nhất để đưa vào báo cáo.

Yêu cầu: Tìm tổng tiền lãi lớn nhất của một đoạn ngày liên tiếp có độ dài ít nhất L.

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

Dòng đầu tiên chứa hai số nguyên dương n và L (L ≤ n).
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 DOANMAX.OUT một số nguyên là tổng lớn nhất.

Ví dụ:

DOANMAX.INP	DOANMAX.OUT	Giải thích
`7 3` `2 -5 4 -1 3 -8 6`	`6`	Đoạn 4, −1, 3 có tổng 6.

Ràng buộc:

Có 30% số test với n ≤ 200.
Có 30% số test với n ≤ 1500.
Có 40% 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