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

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

ĐỀ SỐ 05 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	Ba thanh tre	`TAMGIAC.*`	`TAMGIAC.INP`	`TAMGIAC.OUT`	3
2	Chính phương và lũy thừa của 2	`LUYTHUA.*`	`LUYTHUA.INP`	`LUYTHUA.OUT`	5
3	Phiếu bầu chọn	`TANSUAT.*`	`TANSUAT.INP`	`TANSUAT.OUT`	6
4	Tổng các số chính phương	`TONGBP.*`	`TONGBP.INP`	`TONGBP.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. Ba thanh tre (3 điểm)

Bạn Minh có ba thanh tre dài a, b, c (đơn vị cm) và muốn ghép chúng thành khung một hình tam giác (không được cắt thanh tre).

Yêu cầu: Cho biết ba thanh tre có ghép được thành tam giác hay không; nếu được thì cho biết chu vi và tam giác đó là tam giác vuông, nhọn hay tù.

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

Kết quả: Ghi ra file văn bản TAMGIAC.OUT:

Nếu không ghép được tam giác, ghi KHONG.
Ngược lại, ghi chu vi tam giác và một trong các từ VUONG, NHON, TU, cách nhau một dấu cách.

Ví dụ:

TAMGIAC.INP	TAMGIAC.OUT	Giải thích
`3 5 4`	`12 VUONG`	3² + 4² = 5².
`3 5 8`	`KHONG`	3 + 5 = 8, ba thanh nằm thẳng hàng.
`4 5 8`	`17 TU`	8² = 64 > 4² + 5² = 41.

Ràng buộc:

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

Bài 2. Chính phương và lũy thừa của 2 (5 điểm)

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

Yêu cầu:

Tìm số chính phương lớn nhất không vượt quá N.
Tìm số tự nhiên x lớn nhất và số tự nhiên y sao cho 2^x + y = N.

Dữ liệu vào: Từ file văn bản LUYTHUA.INP gồm một số nguyên dương N.

Kết quả: Ghi ra file văn bản LUYTHUA.OUT gồm hai dòng: dòng thứ nhất ghi số chính phương tìm được; dòng thứ hai ghi hai số x và y.

Ví dụ:

LUYTHUA.INP	LUYTHUA.OUT	Giải thích
`17`	`16` `4 1`	16 = 4²; 17 = 2⁴ + 1.
`64`	`64` `6 0`	64 vừa là số chính phương, vừa là lũy thừa của 2.

Ràng buộc:

Có 50% số test với N ≤ 10⁹.
Có 50% số test với N ≤ 10¹⁸.

Bài 3. Phiếu bầu chọn (6 điểm)

Trong cuộc bình chọn tiết mục văn nghệ, mỗi bạn ghi lên phiếu một số nguyên (mã số tiết mục; do ghi vội nên có cả số 0 và số âm). Ban tổ chức thu được n phiếu a₁, a₂, …, a_n.

Yêu cầu:

Tìm số nguyên dương nhỏ nhất không được ghi trên phiếu nào (để làm mã số cho tiết mục mới).
Liệt kê các số được ghi trên từ hai phiếu trở lên, kèm số phiếu ghi số đó. Sắp xếp theo số phiếu giảm dần; nếu bằng nhau thì theo giá trị tăng dần.

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

Dòng đầu tiên chứa số nguyên dương 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 TANSUAT.OUT:

Dòng đầu tiên ghi số nguyên dương nhỏ nhất tìm được ở câu 1.
Các dòng tiếp theo, mỗi dòng ghi một số và số phiếu ghi số đó, theo thứ tự đã nêu. Nếu không có số nào xuất hiện từ hai lần trở lên thì ghi -1.

Ví dụ:

TANSUAT.INP	TANSUAT.OUT	Giải thích
`7` `5 -3 2 5 -3 1 5`	`3` `5 3` `-3 2`	Số 1, 2 đã có, 3 chưa có. Số 5 xuất hiện 3 lần, số −3 xuất hiện 2 lần.

Ràng buộc:

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

Bài 4. Tổng các số chính phương (6 điểm)

Số chính phương là bình phương của một số nguyên dương: 1, 4, 9, 16, 25, … Mỗi số nguyên dương n đều có thể viết thành tổng của một số số chính phương (các số hạng có thể bằng nhau). Ví dụ: 60 = 49 + 9 + 1 + 1 = 36 + 16 + 4 + 4.

Yêu cầu: Tìm số lượng số hạng ít nhất khi viết n thành tổng các số chính phương.

Dữ liệu vào: Từ file văn bản TONGBP.INP gồm một số nguyên dương n.

Kết quả: Ghi ra file văn bản TONGBP.OUT một số nguyên là số lượng số hạng ít nhất.

Ví dụ:

TONGBP.INP	TONGBP.OUT	Giải thích
`60`	`4`	Không thể viết 60 thành tổng của 1, 2 hay 3 số chính phương.
`13`	`2`	13 = 9 + 4.

Ràng buộc:

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