HSG lớp 9 Nam Định 2018-2019

ĐỀ THI CHỌN HỌC SINH GIỎI LỚP 9 TỈNH NAM ĐỊNH Năm học 2018 - 2019

MÔN TIN HỌC 4 bài: SOTL, HOPQUA, KHOBAU, PALIND

Bài 1. Số tương lai

Số đảo ngược của một số abc là cba, một số được coi là số tương lai nếu ước chung lớn nhất của số đó với số đảo ngược của nó bằng 1. Ví dụ số 23 có số đảo ngược là 32, hai số này có ước chung lớn nhất là 1 nên số 23 là số tương lai và 32 cũng là số tương lai.

Yêu cầu: Cho 2 số tự nhiên a, b (10 < a ≤ b ≤ 10⁵). Đếm xem trong đoạn từ a đến b có bao nhiêu số tương lai.

Dữ liệu: Vào từ file văn bản SOTL.INP gồm một dòng duy nhất chứa hai số a và b.

Kết quả: Đưa ra file văn bản SOTL.OUT số lượng số tương lai trong đoạn [a; b].

Ví dụ: a = 19, b = 29 có các số tương lai là: 19, 23, 25, 29.

SOTL.INP	SOTL.OUT
`19 29`	`4`

Bài 2. Hộp quà

Có N hộp quà được đánh số từ 1 đến N, hộp quà thứ i (i = 1, 2, …, N) có giá trị thẩm mỹ là mᵢ. Nếu xếp lần lượt các hộp quà theo số thứ tự 1, 2, …, N thì giá trị thẩm mỹ của N hộp quà là m₁ + m₂ + … + m_N + max(0, m₂ − m₁) + max(0, m₃ − m₂) + … + max(0, m_N − m_(N−1)). Học sinh An được giao nhiệm vụ là tìm ra cách xếp N hộp quà sao cho giá trị thẩm mỹ của N hộp quà là lớn nhất.

Yêu cầu: Cho N và mᵢ, i = 1, 2, …, N. Xác định giá trị thẩm mỹ lớn nhất của N hộp quà.

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

Dòng đầu tiên chứa số nguyên N (1 ≤ N ≤ 10⁵).
Dòng thứ 2 chứa N số nguyên m₁, m₂, …, m_N (1 ≤ mᵢ ≤ 10000). Các số ghi cách nhau một dấu cách.

Kết quả: Đưa ra file văn bản HOPQUA.OUT giá trị thẩm mỹ lớn nhất của N hộp quà.

Ví dụ:

HOPQUA.INP	HOPQUA.OUT
`5` `5 3 1 7 10`	`39`

Bài 3. Tìm kho báu

Trong trò chơi tìm kho báu của mụ phù thủy, chỉ có một con đường duy nhất để tìm ra kho báu. Trên con đường có một hàng N cây, cây thứ i có độ cao là Hᵢ. Để tìm được kho báu Hoàng được mụ phù thủy đưa cho một khóa K. Nhiệm vụ của cậu ta là phải đánh dấu được nhiều cây nhất, các cây được đánh dấu là các cây có độ chênh lệch về chiều cao không vượt quá khóa K.

Yêu cầu: Cho N, K và Hᵢ, i = 1, 2, …, N. Xác định số lượng cây nhiều nhất và chiều cao của các cây mà Hoàng đánh dấu.

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

Dòng đầu tiên chứa 2 số nguyên N và K (1 ≤ N ≤ 2×10⁴, 1 ≤ K ≤ 10⁹).
Dòng thứ 2 chứa N số nguyên H₁, H₂, …, H_N (1 ≤ Hᵢ ≤ 10⁹, i = 1, 2, …, N). Các số viết cách nhau một dấu cách.

Kết quả: Đưa ra file văn bản KHOBAU.OUT gồm:

Dòng đầu tiên chứa số lượng cây nhiều nhất mà Hoàng cần đánh dấu.
Dòng thứ 2 chứa chiều cao của các cây. Nếu không có thì in ra −1.

Ví dụ:

KHOBAU.INP	KHOBAU.OUT
`8 10` `10 5 90 6 20 9 16 100`	`5` `10 5 6 9 16`

Bài 4. Số đối xứng

Số nguyên không âm được gọi là số palindrome nếu trong biểu diễn hệ 10 (không có số 0 không có nghĩa) đọc từ trái sang phải cho kết quả giống như đọc từ phải sang trái.

Ví dụ: Các số sau là palindrome: 5, 343, 66811866.

Yêu cầu: Cho số nguyên không âm X (X có không quá 10000 chữ số). Hãy tìm một số palindrome lớn nhất có trong X.

Dữ liệu: Vào từ file văn bản PALIND.INP gồm duy nhất một số nguyên X.

Kết quả: Đưa ra file văn bản PALIND.OUT gồm 2 dòng:

Dòng đầu tiên ghi số chữ số của số palindrome lớn nhất có trong X.
Dòng thứ 2 ghi số palindrome lớn nhất có trong X.

Ví dụ:

PALIND.INP	PALIND.OUT
`21314`	`3` `131`
`2131451516`	`3` `515`

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