HSG lớp 9 Đà Nẵng 2023-2024

ĐỀ THI CHỌN HỌC SINH GIỎI LỚP 9 THÀNH PHỐ ĐÀ NẴNG Năm học 2023 - 2024

MÔN TIN HỌC 4 bài: TONG, GAME, CHUMDEN, TANGQUA

---

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. Tính tổng

Cho một dãy số nguyên dương có N phần tử và một chỉ số K. Hãy tính tổng K phần tử lớn nhất trong dãy số nguyên dương đã cho.

Dữ liệu vào: Đọc từ file văn bản TONG.INP:

• Dòng đầu tiên chứa hai số nguyên dương N và K.
• Dòng thứ 2 chứa N số nguyên dương lần lượt là giá trị các phần tử trong dãy số.

Kết quả: Ghi vào file văn bản TONG.OUT số nguyên theo yêu cầu đề bài.

Ví dụ:

TONG.INP	TONG.OUT
10 3 1 2 3 4 5 6 7 8 9 10	27

Ràng buộc:

• Có 40% test tương ứng với K = 2, n ≤ 10;
• Có 30% test tương ứng với K = 3, n ≤ 100;
• Có 30% test tương ứng với n ≤ 10⁵.

Bài 2. Oẳn tù xì

Nhân dịp Tết cổ truyền, Đức và Nhi được bố mẹ cho rất nhiều kẹo, vì được nghỉ học nên Đức và Nhi bày ra một trò chơi như sau: Hai bạn chơi oẳn tù xì với nhau, ai thắng có thể lấy 1 viên kẹo. Để ghi lại kết quả Đức sử dụng các kí tự để ghi chú, nếu Đức thắng sẽ dùng kí tự D, nếu Nhi thắng sẽ dùng kí tự N, nếu hòa sẽ dùng kí tự H.

Yêu cầu: Hãy cho biết số lượng kẹo của Đức và Nhi là bao nhiêu sau khi kết thúc trò chơi.

Dữ liệu vào: Đọc từ file văn bản GAME.INP, chuỗi kí tự dùng để ghi lại kết quả.

Kết quả: Ghi vào file văn bản GAME.OUT, 2 số nguyên lần lượt là số kẹo của Đức và Nhi.

Ví dụ:

GAME.INP	GAME.OUT	Giải thích
HDNDNNNDDNN	4 6	Hai bạn chơi 11 ván, trong đó Đức thắng 4 ván, Nhi thắng 6 ván và 1 ván hòa.

Ràng buộc:

• Có 40% chuỗi kí tự có độ dài tối đa 200 kí tự;
• Có 60% chuỗi kí tự có độ dài tối đa 10³ kí tự.

Bài 3. Chùm đèn

Dọc theo khu vườn nhà Tí được trang trí bởi n chùm bóng đèn a₁, a₂, …, aₙ, chùm bóng đèn thứ i có aᵢ bóng. Để chuẩn bị cho buổi tiệc sinh nhật của mình, Tí quyết định chọn một dãy các chùm đèn liên tiếp trong khu vườn để bố trí khu vực chụp hình cho khách mời đến dự tiệc. Ngoài ra, để khu vực chụp hình không quá đơn điệu, Tí muốn dãy các chùm đèn được chọn có đúng k chùm đèn có số bóng là số lẻ. Vì có nhiều cách chọn, Tí đang rất phân vân không biết nên chọn như thế nào.

Bạn là một trong những người bạn thân của Tí, hãy giúp Tí đếm số cách chọn các chùm đèn trong khu vườn thỏa mãn yêu cầu Tí đặt ra.

Dữ liệu vào: Đọc từ tệp văn bản CHUMDEN.INP:

• Dòng thứ nhất chứa hai số nguyên n và k (1 ≤ k ≤ n ≤ 10⁶).
• Dòng thứ hai chứa n số nguyên a₁, a₂, …, aₙ (1 ≤ aᵢ ≤ 10⁶), các số cách nhau một khoảng trắng.

Kết quả: Ghi ra tệp văn bản CHUMDEN.OUT, số nguyên duy nhất là kết quả của bài toán.

Ví dụ:

CHUMDEN.INP	CHUMDEN.OUT	Giải thích
4 2 1 3 2 3	3	Có 3 cách chọn thỏa mãn ở các vị trí bắt đầu và kết thúc là (1, 2); (1, 3) và (2, 4)

Ràng buộc:

• Có 30% số test đầu với 1 ≤ n ≤ 100;
• Có 30% số test tiếp theo với 100 < n ≤ 5×10³;
• Có 40% số test còn lại không ràng buộc gì thêm.

Bài 4. Tặng quà

Bố Tí là một người rất giàu có. Ông có rất nhiều đất đai và các món đồ quý hiếm. Đặc biệt, ông có bộ sưu tập gồm n món đồ cổ được đánh số thứ tự từ 1 đến n có giá trị cao. Ông đã nhờ các chuyên gia về đồ cổ định giá cho từng món đồ cổ của mình. Sau khi định giá, các chuyên gia đã đưa ra giá trị của món đồ cổ thứ i là aᵢ (∀i = 1..n). Tí là đứa con duy nhất nên ông đã quyết định tặng cho Tí một số món từ bộ sưu tập đồ cổ của mình để làm vốn riêng. Ông cho Tí được tự ý lựa chọn các món đồ, tuy nhiên có một yêu cầu cho Tí là các món chọn sau phải có số thứ tự và giá trị cao hơn món chọn trước đó.

Yêu cầu: Hãy giúp Tí tính xem phải chọn những món đồ trong bộ sưu tập đồ cổ như thế nào để số món đồ không được chọn là ít nhất.

Dữ liệu vào: Đọc từ tệp văn bản TANGQUA.INP:

• Dòng thứ nhất chứa số nguyên dương n (n ≤ 10⁵) là số lượng các món đồ cổ.
• Dòng thứ hai ghi n số nguyên a₁, a₂, …, aₙ (1 ≤ aᵢ ≤ 10⁹), là giá trị của từng món đồ.

Kết quả: Ghi ra tệp văn bản TANGQUA.OUT một số nguyên duy nhất là số món đồ cổ Tí không chọn.

Ví dụ:

TANGQUA.INP	TANGQUA.OUT	Giải thích
5 1 3 3 2 8	2	Tí được chọn 3 món đồ trong 5 món ở các vị trí lần lượt là (1, 3, 5)

Ràng buộc:

• Có 40% số test đầu với n ≤ 25;
• Có 30% số test tiếp theo với 25 < n ≤ 2000;
• Có 30% số test còn lại không có ràng buộc gì thêm.