HSG lớp 9 Bình Định 2021-2022

ĐỀ THI CHỌN HỌC SINH GIỎI LỚP 9 TỈNH BÌNH ĐỊNH Năm học 2021 - 2022

MÔN TIN HỌC 4 bài: BAUOC, NHAC, CHONSO, RUNG

---

Ghi chú

Đề được đánh máy lại theo tài liệu “50 đề thi HSG THCS” (không kèm phần tiêu đề, thời gian làm bài và thang điểm của đề gốc).

Bài 1. Số có ba ước nguyên dương

Bạn Hiền rất yêu thích toán học, đặc biệt là Số học. Một ngày nọ, trong lúc giải một bài toán số học, Hiền muốn đếm những số tự nhiên có đúng ba ước số nguyên dương trong một phạm vi nhất định. Hãy lập trình giúp bạn Hiền đếm xem có bao nhiêu số có đúng ba ước số nguyên dương khác nhau có giá trị không lớn hơn số nguyên N cho trước.

Dữ liệu vào: File BAUOC.INP gồm một dòng ghi số nguyên dương N.

Kết quả: File BAUOC.OUT gồm một dòng ghi một số nguyên là số lượng số có đúng ba ước nguyên dương đếm được.

Ví dụ:

BAUOC.INP	BAUOC.OUT
6	1

Giải thích: Có một số tự nhiên không lớn hơn 6 có đúng ba ước số là số 4 (ba ước số: 1, 2, 4).

Bài 2. Nghe nhạc

Tại một trung tâm thương mại, người ta lắp một băng nhạc vào một máy phát nhạc. Khách hàng muốn nghe bài hát nào chỉ việc nhấn phím ứng với bài đó. Để tìm và phát bài thứ i trên băng, máy xuất phát từ đầu cuộn băng, quay băng để bỏ qua i − 1 bài ghi trước đó, thời gian quay băng bỏ qua mỗi bài và thời gian phát bài đó được tính là như nhau (băng nhạc ghi N bài hát, được mã số từ 1 đến N có thời lượng tính theo phút đủ chứa toàn bộ các bài đã cho, với mỗi bài hát ta biết thời lượng phát của bài đó). Tính trung bình, các bài hát trong một ngày được khách hàng lựa chọn với số lần (tần suất) như nhau. Hãy tìm cách ghi các bài trên băng sao cho tổng thời gian quay băng trong mỗi ngày là ít nhất.

Dữ liệu vào: File NHAC.INP gồm 2 dòng, dòng 1 là số tự nhiên N cho biết số lượng bài hát, dòng 2 là N số nguyên dương thể hiện dung lượng tính theo phút của mỗi bài (mỗi số cách nhau 1 dấu cách).

Kết quả: File NHAC.OUT gồm:

• N dòng đầu tiên thể hiện trật tự bài hát trên băng (mỗi dòng gồm hai số nguyên dương j và d cách nhau bởi dấu cách, trong đó j là mã số của bài hát cần ghi, d là thời gian tìm và phát bài đó theo trật tự ghi này).
• Dòng thứ N + 1 ghi tổng số thời gian quay băng nếu mỗi bài hát được phát một lần trong ngày.

Ví dụ:

NHAC.INP	NHAC.OUT
3 8 3 4	2 3 3 7 1 15 25

Bài 3. Chọn số

Cho dãy số nguyên a₁, a₂, …, aₙ và một số nguyên dương M. Cần xác định một dãy gồm n bít t₁, t₂, …, tₙ (tᵢ bằng 1 hoặc 0), để có M = t₁a₁ + t₂a₂ + … + tₙaₙ.

Dữ liệu vào: File CHONSO.INP gồm:

• Dòng đầu tiên chứa số nguyên dương n (5 ≤ n ≤ 40);
• n dòng tiếp theo chứa các số nguyên aᵢ (i = 1..n) (tổng các số aᵢ không vượt quá 10⁹);
• Dòng cuối cùng (dòng thứ n + 2) chứa số nguyên M.

Kết quả: File CHONSO.OUT thông báo dãy bit tìm được.

Dữ liệu vào đảm bảo có nghiệm duy nhất.

Ví dụ:

CHONSO.INP	CHONSO.OUT
7 11 8 23 2 45 7 34 38	0110010

Bài 4. Rừng nguy hiểm

Một con hổ bị lạc trong một khu rừng nguy hiểm hình vuông, kích thước N × N, mỗi địa hình được mã hoá bởi các số 0 hoặc 1. Mỗi lần di chuyển con hổ có thể đi một bước theo hướng Đông (Đ), Tây (T), Nam (N), Bắc (B) (hay nói cách khác là một ô chung cạnh) với điều kiện nó đi sang một ô có cùng tính chất địa hình (giá trị) với ô nó đang đứng. Bạn hãy xem liệu con hổ có thể thoát khỏi khu rừng nguy hiểm này không, nếu có thì mất ít nhất là bao nhiêu bước dịch chuyển con hổ có thể thoát nguy được?

Dữ liệu vào: File RUNG.INP gồm:

• Dòng đầu là số N (2 ≤ N ≤ 50).
• Dòng thứ hai ghi hai số x, y là giá trị dòng, cột của vị trí đứng ban đầu của con hổ.
• N dòng tiếp theo, mỗi dòng chứa N số (gồm số 0 hoặc số 1) thể hiện cho khu rừng nguy hiểm.

Kết quả: File RUNG.OUT gồm:

• Dòng đầu ghi số 0 nếu con hổ không thể tìm được lối ra.
• Nếu có được lối ra thì:
  • Dòng đầu ghi số 1;
  • Dòng thứ hai ghi số bước ngắn nhất để con hổ thoát khỏi khu rừng (tại vị trí con hổ đang đứng được tính là 1 bước);
  • Các dòng tiếp theo, mỗi dòng ghi một tọa độ nằm trên đường con hổ thoát ra (gồm chỉ số hàng và chỉ số cột, ngăn cách nhau bởi dấu cách). Đường đi của hổ được xuất phát từ vị trí ban đầu nó đứng.

Ví dụ:

RUNG.INP	RUNG.OUT
4 2 2 1 0 1 1 1 0 1 1 1 0 0 0 1 1 1 1	1 2 2 2 1 2
4 2 2 1 1 1 1 1 0 1 1 1 0 0 1 1 1 1 1	0