HSG lớp 9 Bình Định 2018-2019

SỞ GIÁO DỤC VÀ ĐÀO TẠO BÌNH ĐỊNH ĐỀ CHÍNH THỨC

KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH LỚP 9 THCS Khóa ngày 18 - 3 - 2019
Môn thi: Tin học - Ngày thi: 18/3/2019
Thời gian: 150 phút (không kể thời gian phát đề)
(Đề thi có 02 trang)

---

Tổng quan bài thi

Bài	Tên bài, điểm	Tên tệp chương trình	Dữ liệu vào	Dữ liệu ra
1	Tìm số (5,0 điểm)	TimSo.*	TimSo.INP	TimSo.OUT
2	Bộ số tam giác (5,0 điểm)	TamGiac.*	TamGiac.INP	TamGiac.OUT
3	Lược đồ Horner (5,0 điểm)	Horner.*	Horner.INP	Horner.OUT
4	Đường đi của quân cờ (5,0 điểm)	QuanCo.*	QuanCo.INP	QuanCo.OUT

Bài 1. Tìm số (5,0 điểm)

Cho xâu s có chiều dài không quá 1000 gồm các kí tự là chữ cái và chữ số trong đó có ít nhất 3 kí tự số. Lập chương trình xóa bỏ một số kí tự trong xâu s chỉ để lại 3 kí tự số vẫn giữ nguyên thứ tự của chúng trong xâu và tạo nên số có giá trị lớn nhất.

Dữ liệu vào: Từ tệp TimSo.INP gồm 1 dòng chứa xâu s.

Dữ liệu ra: ghi vào tệp TimSo.OUT xâu s chứa 3 kí tự số còn lại tạo thành số lớn nhất.

TimSo.INP	TimSo.OUT
18HSG03	803

Bài 2. Bộ số tam giác (5,0 điểm)

Cho dãy số A gồm n phần tử nguyên dương a₁, a₂, …, a_n. Mỗi phần tử có giá trị không vượt quá 10⁹ và 1 < n ≤ 5000. Một bộ ba số được gọi là bộ số tam giác, nếu ba số này tạo thành ba cạnh của một tam giác nào đó.

Yêu cầu: Hãy đếm xem trong dãy A có bao nhiêu bộ số tam giác (a_i, a_j, a_k) với i, j, k đôi một khác nhau.

Dữ liệu vào từ tệp TamGiac.INP:

• Dòng đầu là số n;
• Dòng tiếp theo là các phần tử của dãy A, mỗi phần tử cách nhau một dấu cách.

Kết quả ra ghi vào tệp TamGiac.OUT: số lượng bộ số tam giác.

Ví dụ:

TamGiac.INP	TamGiac.OUT	Giải thích
5 4 3 1 5 7	3	Ba bộ số tam giác gồm: (4, 3, 5), (4, 5, 7), (3, 5, 7).

Bài 3. Lược đồ Horner (5,0 điểm)

Để chia đa thức f(x) = a_nxⁿ + a_n-1x^n-1 + … + a₁x + a₀ cho nhị thức g(x) = x − c người ta thường sử dụng lược đồ Horner theo dạng bảng:

	an	an-1	an-2	…	a2	a1	a0
c	bn	bn-1	bn-2	…	b2	b1	b0

Trong đó:

b_n = a_n, b_n-1 = c·b_n + a_n-1, b_n-2 = c·b_n-1 + a_n-2, …, b₁ = c·b₂ + a₁, b₀ = c·b₁ + a₀

Hay ta viết: b_n = a_n, b_i = c·b_i+1 + a_i (i = 0..n−1).

Khi đó ta có biến đổi đa thức:

f(x) = (x − c)(b_nx^n-1 + b_n-1x^n-2 + … + b₁) + b₀

Từ đó ta có kết luận: x = c là nghiệm của đa thức f(x) nếu b₀ = 0.

Hãy lập chương trình nhập vào các hệ số a_i của đa thức f(x) và giá trị c, tính các hệ số b_i và cho biết c có là nghiệm của đa thức f(x) hay không.

Dữ liệu vào trong file Horner.INP có cấu trúc như sau:

• Dòng đầu chứa số tự nhiên n và số nguyên c (n < 100, |c| < 5000).
• n+1 dòng tiếp theo mỗi dòng chứa một số nguyên lần lượt là các hệ số a_i của đa thức f(x) với (|a_i| < 5000) được sắp xếp từ a_n đến a₀.

Dữ liệu ra là file Horner.OUT có cấu trúc như sau:

• Dòng đầu tiên là kết luận: “c la nghiem” hoặc “c khong la nghiem”.
• n+1 dòng tiếp theo, liệt kê các hệ số b_i sắp xếp từ b_n đến b₀.

Ví dụ:

Horner.INP	Horner.OUT
3 2 1 -2 3 -6	2 la nghiem 1 0 3 0
2 1 3 -2 1	1 khong la nghiem 3 1 2

Bài 4. Đường đi của quân cờ (5,0 điểm)

Bàn cờ là một bảng hình chữ nhật có M×N ô gồm M hàng, N cột. Quân cờ cần thực hiện lộ trình qua N ô xuất phát từ một ô bất kỳ của cột 1 và kết thúc ở một ô nào đó của cột N. Với mỗi bước đi quân cờ chỉ được đi sang 1 ô ở cột tiếp theo trên đường chéo (hình vẽ minh họa). Trên mỗi ô chứa một số nguyên là thời gian (tính bằng phút) mà quân cờ phải lưu lại tại ô đó.

Bạn hãy giúp tìm một lộ trình để quân cờ hoàn thành với ít thời gian nhất.

Dữ liệu vào là file QuanCo.INP có cấu trúc như sau:

• Dòng đầu gồm hai số nguyên dương M, N (0 < M, N < 300).
• M dòng tiếp theo, mỗi dòng gồm N số nguyên dương A_ij là giá trị tương ứng tại ô thuộc hàng i, cột j trong bảng (0 < A_ij < 1000).

Dữ liệu ra là file QuanCo.OUT có cấu trúc như sau:

• Dòng đầu là tổng thời gian mà quân cờ thực hiện lộ trình tốt nhất tìm được.
• N dòng tiếp theo, mỗi dòng gồm hai số nguyên chỉ tọa độ của N ô mà quân cờ thực hiện theo lộ trình để có kết quả tốt nhất.

Ví dụ:

QuanCo.INP	QuanCo.OUT
4 5 2 4 6 7 8 1 6 8 2 3 4 3 5 2 8 5 1 7 8 2	15 2 1 3 2 4 3 3 4 4 5