HSG lớp 9 Kon Tum 2023-2024

ĐỀ THI CHỌN HỌC SINH GIỎI LỚP 9 TỈNH KON TUM Năm học 2023 - 2024

MÔN TIN HỌC 4 bài: SONN, DOIHINH, MS, SAPXEP

Bài 1. Số nhỏ nhất

Cho số nguyên dương n.

Yêu cầu: Hãy tìm số nguyên dương m nhỏ nhất sao cho tổng các chữ số của m đúng bằng n và các chữ số của m phân biệt (không có chữ số nào xuất hiện nhiều hơn 1 lần).

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

Kết quả: Ghi ra file văn bản SONN.OUT số nguyên dương m tìm được.

Ví dụ:

SONN.INP	SONN.OUT
`25`	`1789`
`44`	`23456789`
`11`	`29`

Bài 2. Đội hình biểu diễn

Học sinh trường XYZ vinh dự được chọn tham gia biểu diễn trong lễ khai mạc Hội khỏe Phù Đổng tỉnh ZZZ. Để đội hình biểu diễn đồng đều, đẹp, Ban tổ chức muốn chọn những em học sinh có chiều cao bằng nhau trong n học sinh của trường XYZ.

Yêu cầu: Hãy giúp Ban tổ chức chọn ra một nhóm học sinh có chiều cao bằng nhau với số lượng nhiều nhất, nếu có nhiều nhóm có số lượng bằng nhau thì chọn nhóm có chiều cao lớn nhất.

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

Dòng 1: Số nguyên n (1 ≤ n ≤ 10⁵) là số lượng học sinh của trường XYZ.
Dòng 2: Chứa n số nguyên h₁, h₂, …, hₙ (1 ≤ hᵢ ≤ 250) là chiều cao của các học sinh trường XYZ, các số cách nhau một khoảng trắng.

Kết quả: Ghi ra file văn bản DOIHINH.OUT hai số nguyên là chiều cao và số lượng học sinh được chọn, hai số cách nhau một khoảng trắng.

Ví dụ:

DOIHINH.INP	DOIHINH.OUT
`6` `156 161 158 161 159 161`	`161 3`

Bài 3. Mã số bí ẩn

Bạn Nam rất thích chơi trò tìm số bí ẩn. Mỗi lần cả gia đình Nam phải đi vắng, Nam được giao nhiệm vụ khóa cửa và gửi một dòng tin nhắn hướng dẫn mở khóa cho cả gia đình. Nội dung tin nhắn gồm một xâu kí tự gồm các chữ cái in thường và các chữ số. Mã số bí ẩn để mở khóa chính là số lượng các số nguyên phân biệt xuất hiện trong dòng tin nhắn.

Ví dụ: Dòng tin nhắn gồm 1 xâu ab00012ggg12cvb5xyz12a07bb7 sẽ chứa 3 số nguyên phân biệt 12, 5, 7 (sau khi đã loại bỏ các số 0 ở đằng trước số 00012 và 07). Nên mật mã là 3.

Yêu cầu: Em hãy viết chương trình để giúp gia đình bạn Nam tìm ra mã số bí ẩn.

Dữ liệu: Nhập dữ liệu từ file MS.INP một xâu (độ dài xâu ≤ 100) gồm các chữ số và các kí tự in thường.

Kết quả: Ghi ra file MS.OUT một số nguyên duy nhất là kết quả bài toán.

Ví dụ:

MS.INP	MS.OUT
`zz12bbblc2d3`	`4`
`ss00013ab13xx23bb09cc9`	`3`

Bài 4. Sắp xếp

Đầu mỗi năm mới, trường XYZ tổ chức Hội chợ xuân với rất nhiều trò chơi. Trò chơi i có thời gian bắt đầu bᵢ và thời gian kết thúc kᵢ. An muốn sắp xếp thời gian để có thể tham gia nhiều trò chơi nhất có thể mà không trùng về mặt thời gian.

Yêu cầu: Xác định số lượng trò chơi nhiều nhất mà An có thể tham gia.

Dữ liệu: Vào từ file văn bản SAPXEP.INP gồm n + 1 dòng:

Dòng đầu ghi một số nguyên n (1 ≤ n ≤ 1000) là số lượng trò chơi.
Dòng thứ i trong n dòng tiếp theo chứa 2 số nguyên bᵢ, kᵢ (1 ≤ bᵢ < kᵢ ≤ 10⁹) là thời điểm bắt đầu và thời điểm kết thúc của trò chơi thứ i (1 ≤ i ≤ n), hai số cách nhau một khoảng trắng.

Kết quả: Ghi ra file văn bản SAPXEP.OUT số nguyên là số lượng trò chơi nhiều nhất mà An có thể tham gia.

Ví dụ:

SAPXEP.INP	SAPXEP.OUT	Giải thích
`6` `4 9` `7 8` `5 9` `3 4` `9 12` `7 13`	`3`	Đầu tiên An tham gia trò chơi thứ 4, sau đó tham gia trò chơi thứ 2 và cuối cùng tham gia trò chơi thứ 5.

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