HSG lớp 9 Vĩnh Phúc 2020-2021

SỞ GD&ĐT VĨNH PHÚC ĐỀ CHÍNH THỨC

KỲ THI CHỌN HỌC SINH GIỎI LỚP 9 NĂM HỌC 2020-2021 Đề thi môn: Tin học
Thời gian làm bài: 150 phút (không kể thời gian giao đề)
Đề thi gồm 02 trang

---

Tổng quan về đề thi

STT	Tên bài	Chương trình	Dữ liệu	Kết quả	Thời gian
1	Chia hết	DIVISIBLE.*	DIVISIBLE.INP	DIVISIBLE.OUT	1s/test
2	Đếm kí tự	APPEARSTR.*	APPEARSTR.INP	APPEARSTR.OUT	1s/test
3	Giảm cân	WEIGHTLOSS.*	WEIGHTLOSS.INP	WEIGHTLOSS.OUT	1s/test
4	Chọn mua sách	CHOOSE.*	CHOOSE.INP	CHOOSE.OUT	1s/test

Lưu ý: Thí sinh thay * trong tên chương trình thành PAS hoặc CPP tuỳ theo ngôn ngữ lập trình mà thí sinh sử dụng là Pascal hay C/C++.

Lập chương trình giải các bài toán sau đây:

Bài 1. Chia hết [DIVISIBLE]

Sau khi học xong bài “Dấu hiệu chia hết” ở trường, An đã biết cách xác định một số nguyên chia hết cho 9, cách đó là “Số chia hết cho 9 là số có tổng các chữ số cũng chia hết cho 9”.

Từ cách xác định trên, An đố bạn một bài toán như sau: Cho T số nguyên, hãy kiểm tra T số nguyên này chia hết cho 9 hay không.

Bạn hãy lập trình giải bài toán mà An đưa ra nhé!

Dữ liệu:

• Dòng 1: Một số nguyên T (1 ≤ T ≤ 20);
• T dòng tiếp theo, mỗi dòng ghi một số nguyên N (1 ≤ N ≤ 10¹⁰⁰⁰⁰⁰).

Kết quả:

• Gồm T dòng, dòng thứ i ghi “Yes” nếu số nguyên thứ i chia hết cho 9, ghi “No” nếu không chia hết cho 9 (1 ≤ i ≤ 20).

Subtasks:

• Subtask 1 (50% điểm): 1 ≤ T ≤ 20; 1 ≤ N ≤ 10¹⁸;
• Subtask 2 (50% điểm): 1 ≤ T ≤ 20; 1 ≤ N ≤ 10¹⁰⁰⁰⁰⁰.

Ví dụ:

DIVISIBLE.INP	DIVISIBLE.OUT
3 9 18 8	Yes Yes No

Bài 2. Đếm kí tự [APPEARSTR]

Xâu là dãy các kí tự trong bảng mã ASCII. Cho một xâu S chỉ gồm các kí tự là chữ số, chữ cái in hoa và in thường. Bạn hãy lập trình đếm số lần xuất hiện của từng kí tự có trong xâu S?

Dữ liệu:

• Một dòng duy nhất chứa xâu S khác rỗng (độ dài của S không quá 10⁷ kí tự).

Kết quả:

• Đối với mỗi kí tự xuất hiện trong xâu S, ghi trên một dòng gồm kí tự và số lần xuất hiện của kí tự đó trong xâu (các kí tự được liệt kê theo thứ tự từ điển).

Subtasks:

• Subtask 1 (50% điểm): Xâu chỉ chứa kí tự chữ cái in thường;
• Subtask 2 (50% điểm): Không có ràng buộc bổ sung.

Ví dụ:

APPEARSTR.INP	APPEARSTR.OUT
55faaAAA222	2 3 5 2 A 3 a 2 f 1

Bài 3. Giảm cân [WEIGHTLOSS]

Sau kì nghỉ Tết, mặc dù đã cố gắng giảm thiểu tối đa lượng chất béo hấp thụ, nhưng cân nặng của An vẫn tăng lên đáng kể. An không quá chăm chút về ngoại hình nhưng vẫn quyết định giảm cân để có một cơ thể khỏe mạnh. Vì thế An lên kế hoạch tập luyện để giảm cân.

Kế hoạch ban đầu được An đưa ra gồm N buổi tập luyện, buổi tập luyện thứ i có cường độ là Mᵢ (Mᵢ là số nguyên), buổi tập luyện sau luôn có cường độ tập luyện lớn hơn buổi trước nó. Gọi “độ khó” của bản kế hoạch là chênh lệch lớn nhất về cường độ tập luyện giữa hai buổi liền nhau bất kì.

Nhìn vào bản kế hoạch, An cảm thấy chưa hoàn hảo nên muốn cải thiện bằng cách chèn thêm K buổi tập luyện sao cho sau khi chèn vẫn đảm bảo buổi tập luyện sau luôn có cường độ tập luyện lớn hơn buổi tập trước và “độ khó” của bản kế hoạch là nhỏ nhất có thể.

Bạn hãy giúp An tìm “độ khó” của bản kế hoạch hoàn hảo.

Dữ liệu:

• Dòng 1: Hai số nguyên N, K. Trong đó, N là số buổi tập luyện (2 ≤ N ≤ 10⁵); K là số buổi cần chèn thêm (1 ≤ K ≤ 10⁵);
• Dòng 2: Ghi N số nguyên M₁, M₂, …, M_N với Mᵢ là cường độ tập luyện của buổi thứ i (1 ≤ Mᵢ ≤ 10⁹; 1 ≤ i ≤ N).

Kết quả:

• Một số nguyên duy nhất là “độ khó” của bản kế hoạch hoàn hảo.

Subtasks:

• Subtask 1 (50% điểm): K = 1; 2 ≤ N ≤ 300.
• Subtask 2 (50% điểm): Không có ràng buộc bổ sung.

Ví dụ:

WEIGHTLOSS.INP	WEIGHTLOSS.OUT	Giải thích
3 1 100 200 230	50	An sẽ chèn thêm một buổi tập để bản kế hoạch như sau: 100 150 200 230 Và độ khó là: max(150 − 100, 200 − 150, 230 − 200) = 50

Bài 4. Chọn mua sách [CHOOSE]

Trong một cửa hàng sách có bán N quyển sách được đánh số thứ tự từ 1 đến N. Quyển sách thứ i có giá đúng bằng i (∀i: 1 ≤ i ≤ N).

An muốn mua một số quyển sách sao cho tổng giá trị của chúng đúng bằng N.

Bạn hãy lập trình giúp An liệt kê tất cả các cách chọn mua sách. Các cách chọn sách là hoán vị của nhau thì chỉ tính là 1 cách.

Dữ liệu:

• Một dòng duy nhất số nguyên dương N (N < 100) là tổng giá trị của các quyển sách mà An mua.

Kết quả:

• Gồm nhiều dòng, mỗi dòng ghi một cách chọn mua sách có tổng giá trị bằng N. Các cách phải được liệt kê theo thứ tự từ điển.

Ví dụ:

CHOOSE.INP	CHOOSE.OUT
7	1 2 4 1 6 2 5 3 4 7

---

Thí sinh không được sử dụng tài liệu. Cán bộ coi thi không giải thích gì thêm.