HSG lớp 9 Khánh Hòa 2022-2023

ĐỀ THI HỌC SINH GIỎI CẤP THCS TỈNH KHÁNH HÒA Năm học 2022 - 2023

MÔN TIN HỌC Ngày thi: 07/12/2022
Thời gian: 150 phút

Tổng quan đề thi

Bài	Tên bài	File CT	File input	File output	Điểm
1	Vượt chướng ngại vật	`ATHORUA.*`	`ATHORUA.INP`	`ATHORUA.OUT`	5
2	Chia bánh	`CHIABANH.*`	`CHIABANH.INP`	`CHIABANH.OUT`	6
3	Chữ số thứ K	`NUMBER.*`	`NUMBER.INP`	`NUMBER.OUT`	5
4	Chia kẹo	`RCHIAKEO.*`	`RCHIAKEO.INP`	`RCHIAKEO.OUT`	4

Dấu * được thay thế bởi PAS, CPP hoặc PY của ngôn ngữ lập trình được sử dụng tương ứng là Pascal, C++ hoặc Python.

Bài 1. Vượt chướng ngại vật (5 điểm)

Thỏ và Rùa cùng tham gia trò chơi vượt chướng ngại vật. Chướng ngại vật là con dốc dài V mét, có độ dốc lớn. Lúc đầu cả hai xuất phát cùng lúc dưới chân dốc, ngày leo đêm ngủ trong nhiều ngày đêm mới lên đến đỉnh dốc, con nào lên tới đỉnh dốc với số ngày đi ít hơn thì chiến thắng. Thỏ trong một ngày có thể leo lên A₁ mét, trong mỗi đêm nó ngủ quên lại bị tụt xuống B₁ mét. Còn Rùa trong một ngày có thể leo A₂ mét, trong mỗi đêm nó ngủ quên lại bị tụt xuống B₂ mét.

Yêu cầu: Với các số V, A₁, B₁, A₂, B₂ cho trước, em hãy lập trình cho biết Thỏ hay Rùa chiến thắng hay chúng hòa nhau.

Input: 5 dòng ghi 5 số V, A₁, B₁, A₂, B₂ (0 < V < 1000; 1 ≤ B₁ < A₁ < V; 1 ≤ B₂ < A₂ < V).

Output: ghi tên con vật chiến thắng (THO hay RUA hay HOA).

Input	Output
`7` `3` `1` `4` `2`	`HOA`
`50` `12` `2` `10` `1`	`THO`

Bài 2. Chia bánh (6 điểm)

Trong dịp sinh nhật, Thảo mời Tuấn đến nhà chơi và cùng ăn bánh pizza. Chiếc bánh pizza Thảo là hình tròn, được chia làm tám mảnh, trên mỗi mảnh có đính các chiếc nấm xinh xắn với số lượng khác nhau. Thảo biết bạn rất thích ăn nấm, nên Thảo đố Tuấn chọn nhanh bốn mảnh liên tiếp nhau của chiếc bánh sao cho tổng số nấm trên bốn mảnh đó là lớn nhất.

Trong bất chợt, Tuấn bối rối chưa nghĩ ra cách nhanh nhất để chọn bốn mảnh bánh liên tiếp theo yêu cầu của Thảo.

Yêu cầu: Em hãy lập trình giúp Tuấn chọn nhanh bốn mảnh liên tiếp có tổng số nấm nhiều nhất.

Input: một dòng chứa 8 số nguyên a₁, a₂, …, a₈ (0 < aᵢ < 60).

Output: một số nguyên là tổng số nấm lớn nhất trên bốn mảnh liên tiếp.

Input	Output
`6 2 6 5 3 3 7 2`	`19`

Bài 3. Chữ số thứ K (5 điểm)

Tí là học sinh rất thông minh. Trong giờ toán, Tí luôn hoàn thành rất nhanh tất cả các bài tập được giao, sau đó chọc ngoáy các bạn. Để tránh cho Tí làm ảnh hưởng các bạn, cô giáo thường giao thêm cho Tí bài tập riêng. Bài tập hôm nay cô giáo ra là: Tìm chữ số thứ K của một số tự nhiên rất lớn tính từ trái sang phải. Số tự nhiên rất lớn này được tạo ra bằng cách ghép các số tự nhiên liên tiếp 1, 2, 3, 4, 5, … lại với nhau.

Ví dụ: một số tự nhiên rất lớn được tạo ra theo cách trên

1234567891011121314151617181920212223242526272829303132333435…

Với K = 10, chữ số thứ 10 của số tự nhiên trên là 1.

Với mỗi số K cho trước, Tí đều tìm được chữ số thứ K của số tự nhiên rất lớn trên, nhưng tính toán rất lâu mới được kết quả.

Yêu cầu: Em hãy lập trình giúp Tí tìm nhanh chữ số thứ K.

Input: một dòng chứa số nguyên dương K (K < 10⁹).

Output: chữ số thứ K.

Ràng buộc:

Có 50% test ứng với 0 < K < 1000;
Có 50% test không ràng buộc gì thêm.

Input	Output
`10`	`1`
`54`	`3`

Bài 4. Chia kẹo (4 điểm)

Ông già Noel mang một bao kẹo lớn chứa M viên kẹo phát cho N học sinh ở trường X trong dịp Giáng sinh. Mỗi học sinh mong muốn nhận được một số kẹo nhất định. Nếu một học sinh không nhận được đủ số kẹo mà học sinh đó mong muốn, em học sinh đó sẽ giận hờn. Mức độ giận hờn của mỗi học sinh bằng bình phương số kẹo mà học sinh đó thiếu.

Ví dụ: Học sinh A mong muốn nhận 32 viên kẹo nhưng chỉ được phát 29 viên kẹo, bạn ấy thiếu 3 viên. Suy ra mức độ giận hờn của em đó là 3² = 9.

Do không biết số lượng kẹo mong muốn được nhận của mỗi học sinh, nên Ông già Noel đã mang thiếu kẹo để chia theo mong muốn của mỗi em. Vì vậy Ông già Noel không biết cách chia kẹo cho các học sinh sao cho tổng mức độ giận hờn của các em là nhỏ nhất.

Em hãy chỉ ra phương án giúp Ông già Noel chia kẹo sao cho tổng mức độ giận hờn là nhỏ nhất.

Input:

Dòng thứ nhất chứa hai số nguyên M (1 ≤ M ≤ 10⁵) và N (1 ≤ N ≤ 5000).
N dòng tiếp theo, mỗi dòng chứa một số tự nhiên là số kẹo mong muốn nhận được của mỗi học sinh.

Output: ghi một số nguyên là tổng số giận hờn nhỏ nhất.

Ràng buộc:

40% test ứng với 0 < N < 100;
60% test không có ràng buộc gì thêm.

Input	Output
`29 1` `32`	`9`
`32 5` `13` `8` `9` `2` `15`	`47`

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