HSG lớp 9 TP. Vinh (Nghệ An) 2022-2023

UBND THÀNH PHỐ VINH PHÒNG GIÁO DỤC - ĐÀO TẠO Đề thi chính thức
(Đề thi gồm có 03 trang)

KỲ THI CHỌN HỌC SINH GIỎI LỚP 9 Năm học 2022 - 2023
Môn thi: Tin học
Thời gian: 150 phút, không kể thời gian giao đề

---

Ghi chú

Đây là đề thi học sinh giỏi cấp thành phố (Phòng GD&ĐT thành phố Vinh, tỉnh Nghệ An).

Tổng quan đề thi

Câu	Tên bài	File chương trình	File dữ liệu	File kết quả	Thời gian	Bộ nhớ
1	Các số có tổng chữ số bằng N	SUMDIGITS.*	SUMDIGITS.INP	SUMDIGITS.OUT	1 giây	1024MB
2	Số gần hoàn hảo	GHH.*	GHH.INP	GHH.OUT	1 giây	1024MB
3	Tìm chỗ đỗ xe	MINPLACES.*	MINPLACES.INP	MINPLACES.OUT	1 giây	1024MB
4	Phần thưởng	BONUS.*	BONUS.INP	BONUS.OUT	1 giây	1024MB

Dấu * được thay thế bởi PAS hoặc CPP, PY của ngôn ngữ lập trình sử dụng tương ứng là Pascal hoặc C/C++, Python.

Câu 1. Các số có tổng chữ số bằng N (6,0 điểm)

Nhập một số nguyên dương N. Hãy đếm số lượng tất cả các số có 4 chữ số và có tổng các chữ số bằng N.

Yêu cầu: 1 ≤ T ≤ 100; 1 ≤ N ≤ 36.

Dữ liệu vào: Vào từ file văn bản SUMDIGITS.INP:

Dòng đầu tiên chứa số nguyên T cho biết số bộ dữ liệu, các dòng tiếp theo mỗi bộ dữ liệu gồm một dòng chứa một số nguyên N.

Dữ liệu ra: Đưa ra file văn bản SUMDIGITS.OUT ứng với mỗi bộ dữ liệu in ra một dòng chứa số lượng các số thỏa mãn.

Ví dụ:

SUMDIGITS.INP	SUMDIGITS.OUT
1 35	4

Giải thích: Có 4 số có 4 chữ số và có tổng các chữ số bằng 35 là: 8999, 9899, 9989, 9998.

Câu 2. Số gần hoàn hảo (5,0 điểm)

Một số nguyên dương X được gọi là số “gần hoàn hảo” nếu thỏa mãn điều kiện: 2 × X ≤ T, với T là tổng các ước số dương của X.

Ví dụ số 12 là một số “gần hoàn hảo” vì điều kiện 2 × 12 ≤ 1 + 2 + 3 + 4 + 6 + 12 đúng.

Yêu cầu: Cho dãy số A có N phần tử nguyên dương A₁, A₂, …, A_N, hãy kiểm tra xem các phần tử của dãy số A có phải là các số “gần hoàn hảo” hay không?

Dữ liệu vào: Vào từ file văn bản GHH.INP có cấu trúc:

• Dòng 1: Ghi số nguyên dương N (N ≤ 10⁶);
• Dòng 2: Ghi N số nguyên dương A₁, A₂, …, A_N (Aᵢ ≤ 10⁶ với 1 ≤ i ≤ N). Các số trên cùng một dòng cách nhau bởi dấu cách.

Dữ liệu ra: Đưa ra file văn bản GHH.OUT gồm N dòng, dòng thứ i ghi số 1 nếu Aᵢ là số “gần hoàn hảo”, ngược lại ghi số 0, với i = 1, 2, …, N.

Ví dụ:

GHH.INP	GHH.OUT
3 6 16 12	1 0 1

Giới hạn:

• Có 15/25 test, tương ứng 3 điểm với N ≤ 10³;
• Có 10/25 test, tương ứng 2 điểm với 10³ < N ≤ 10⁶.

Câu 3. Tìm chỗ đỗ xe (5,0 điểm)

Nam được tuyển dụng về làm việc tại bến xe Bắc Vinh phụ trách mảng Tin học. Ngày đầu tiên đi làm, Nam được giao nhiệm vụ hãy lập trình tính toán tìm số chỗ đỗ xe tối thiểu cần có trên sân để không có xe khách nào phải chờ đợi khi vào bến xe, trong đó Nam được cung cấp thông tin thời điểm rời bến và thời điểm đến của mỗi chuyến xe.

Yêu cầu:

• 1 ≤ T ≤ 100; 1 ≤ N ≤ 10⁴
• 0000 ≤ A[i] ≤ B[i] ≤ 2359, i = 1..N.

Dữ liệu vào: Vào từ file văn bản MINPLACES.INP

Dòng đầu tiên chứa số nguyên T là số bộ dữ liệu, mỗi bộ dữ liệu gồm:

• Dòng đầu chứa số nguyên N
• Dòng thứ 2 chứa N số nguyên, mỗi số cách nhau một dấu cách, trong đó số thứ i là A[i] cho biết thời điểm đến của xe thứ i.
• Dòng thứ 3 chứa N số nguyên, mỗi số cách nhau một dấu cách, trong đó số thứ i là B[i] cho biết thời điểm rời bến của xe thứ i.

Thời gian đến và rời bến của mỗi xe được biểu diễn bằng một số nguyên dương có 4 chữ số cho biết giờ (dạng 24h) và phút (60). Ví dụ: 0935 (9 giờ 35 phút).

Dữ liệu ra: Đưa ra file văn bản MINPLACES.OUT gồm:

Ứng với mỗi bộ dữ liệu test in ra một dòng, chứa số chỗ đỗ xe tối thiểu cần bố trí trên sân để không có xe nào phải chờ đợi.

Ví dụ:

MINPLACES.INP	MINPLACES.OUT
2 6 0900 0940 0950 1100 1500 1800 0910 1200 1120 1130 1900 2000 3 0900 1100 1235 1000 1200 1240	3 1

(Đề gốc ghi điều kiện là “0000 < A[i] < B[i] ≤ 2359”.)

Câu 4. Phần thưởng (4 điểm)

Trong phần chơi thi đấu GARA STEM của ngày hội Stem cấp thành, phần thưởng cho đội thắng cuộc là tổng trọng số của tất cả các dãy con liên tiếp trong dãy số A cho trước.

Định nghĩa trọng số của một dãy số nguyên là độ chênh lệch giữa phần tử lớn nhất và phần tử nhỏ nhất trong dãy.

Yêu cầu: Cho dãy số nguyên dương A = (a₁, a₂, …, aₙ). Hãy tìm phần thưởng cho đội thắng cuộc.

Ví dụ với A = (1, 2, 3), những dãy con gồm các phần tử liên tiếp trong A là:

• Dãy rỗng và các dãy có 1 phần tử (1), (2), (3) đều có trọng số 0;
• Dãy (1, 2) và dãy (2, 3) đều có trọng số 1;
• Dãy (1, 2, 3) có trọng số 2.

Phần thưởng cho đội thắng cuộc bằng 0 + 1 + 1 + 2 = 4.

Dữ liệu vào: Vào từ file văn bản BONUS.INP

• Dòng 1: Ghi số nguyên dương n (n ≤ 10⁶);
• Dòng 2: Ghi n số nguyên dương a₁, a₂, …, aₙ có giá trị không vượt quá 10⁶.

Dữ liệu ra: Đưa ra file văn bản BONUS.OUT một số nguyên duy nhất là kết quả tìm được.

Ví dụ:

BONUS.INP	BONUS.OUT
3 1 2 3	4
4 3 1 7 2	31