HSG lớp 9 Hà Nội 2015-2016

SỞ GIÁO DỤC VÀ ĐÀO TẠO HÀ NỘI ĐỀ CHÍNH THỨC

KỲ THI HỌC SINH GIỎI LỚP 9 CẤP THÀNH PHỐ Năm học 2015 - 2016
Môn thi: Tin học - Ngày thi: 14/4/2016
Thời gian làm bài: 150 phút
(Đề thi gồm 02 trang)

---

Câu 1. Tích lấy dư (6 điểm)

Tên tệp chương trình: CAU1.*

Cho ba số nguyên dương a, b, c.

Yêu cầu: Tìm số dư của phép chia tích các số nguyên trong đoạn [a..b] cho số c.

Dữ liệu: Vào từ tệp văn bản CAU1.INP chứa ba số a, b, c (1 ≤ a < b ≤ 10⁴, 1 < c ≤ 10⁹).

Kết quả: Ghi ra tệp văn bản CAU1.OUT số dư tìm được.

Ví dụ:

CAU1.INP	CAU1.OUT	Giải thích
5 10 11	5	Ta có: 5 × 6 × 7 × 8 × 9 × 10 mod 11 = 5

Câu 2. Điểm thưởng (5 điểm)

Tên tệp chương trình: CAU2.*

Trong cuộc thi Tin học trẻ, mỗi thí sinh phải trả lời n câu hỏi. Để tăng tính hấp dẫn của cuộc thi, ban tổ chức quyết định đưa ra n số điểm thưởng a₁, a₂, …, aₙ. Theo thể lệ của cuộc thi, thí sinh trả lời đúng k câu hỏi (1 ≤ k ≤ n) sẽ nhận được số điểm thưởng bằng số lớn nhất trong các số a₁, a₂, …, aₖ.

Yêu cầu: Xác định số điểm thưởng của thí sinh tương ứng với mỗi giá trị k từ 1 đến n.

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

• Dòng đầu chứa số nguyên dương n không vượt quá 30000;
• Dòng thứ hai chứa n số nguyên dương a₁, a₂, …, aₙ, mỗi số không vượt quá 10³.

Kết quả: Ghi ra tệp văn bản CAU2.OUT một dòng gồm n số là điểm thưởng cho thí sinh trả lời đúng lần lượt 1, 2, …, n câu hỏi.

Ví dụ:

CAU2.INP	CAU2.OUT	Giải thích
3 6 1 7	6 6 7	Thí sinh trả lời đúng 1 câu sẽ nhận điểm thưởng là 6; trả lời đúng 2 câu sẽ nhận điểm thưởng là 6, trả lời đúng 3 câu sẽ nhận điểm thưởng là 7.

Câu 3. Tìm xâu (5 điểm)

Tên tệp chương trình: CAU3.*

Cho trước xâu kí tự s độ dài n chỉ chứa các chữ cái tiếng Anh. Bắt đầu từ xâu s, thực hiện phép hoán vị vòng quanh các kí tự sẽ nhận được một dãy gồm m xâu khác nhau (m ≤ n). Sau khi sắp xếp m xâu trong dãy nhận được theo thứ tự từ điển, xâu kí tự s ban đầu có vị trí thứ k.

Ví dụ: Với s = BCA khi hoán vị vòng quanh các kí tự nhận được 3 xâu khác nhau: BCA, CAB, ABC. Sắp xếp theo thứ tự từ điển có dãy các xâu lần lượt là: ABC, BCA, CAB; xâu s ban đầu đứng ở vị trí thứ k = 2.

Yêu cầu: Cho biết xâu x là một trong m xâu nhận được từ s bằng cách hoán vị vòng quanh các kí tự và vị trí k của xâu s. Xác định xâu s.

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

• Dòng đầu chứa số nguyên dương k;
• Dòng thứ hai chứa xâu x có độ dài n (k ≤ n ≤ 100).

Kết quả: Ghi ra tệp văn bản CAU3.OUT xâu s tìm được. Trong trường hợp không xác định được s thì ghi số -1.

Ví dụ:

CAU3.INP	CAU3.OUT	Giải thích
2 ABC	BCA	Từ xâu s = ‘BCA’ bằng cách hoán vị vòng quanh các kí tự sẽ xuất hiện xâu ‘ABC’ và xâu s có số thứ tự k = 2 khi sắp xếp các xâu nhận được theo thứ tự từ điển.

Câu 4. Di chuyển cây (4 điểm)

Tên tệp chương trình: CAU4.*

Thành phố ZXY có một vườn bách thảo được mô tả dưới dạng bản đồ hình chữ nhật gồm m dòng và n cột. Trong vườn có k loại cây khác nhau, đánh số từ 1 đến k (k ≤ 100). Mỗi ô của bản đồ chứa duy nhất số nguyên dương i (i ≤ k) nếu tại ô này có trồng một cây loại i, hoặc số 0 nếu ô này không có cây. Chính quyền thành phố muốn chỉnh trang khu vườn cho đẹp hơn bằng cách giữ lại những hàng cây có ít nhất t cây liền nhau, thuộc cùng một loại cây, nằm trên cùng một dòng hoặc cùng một cột. Những cây không thuộc hàng cây nào đó sẽ được di chuyển đến vị trí khác phù hợp hơn.

Yêu cầu: Cho trước bản đồ vườn cây như trên, hãy đếm số lượng cây cần phải di chuyển.

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

• Dòng đầu chứa ba số nguyên dương m, n và t (1 < m, n, t ≤ 100);
• Trong m dòng tiếp theo, mỗi dòng chứa n số tự nhiên mô tả bản đồ vườn bách thảo.

Kết quả: Ghi ra tệp văn bản CAU4.OUT số lượng cây cần phải di chuyển.

Ví dụ:

CAU4.INP	CAU4.OUT
5 6 3 1 3 3 3 3 4 1 2 3 2 0 4 3 2 2 2 4 4 1 0 0 2 4 0 1 2 3 0 4 4	10

Giải thích: Những số gạch chân dưới đây biểu thị những cây cần phải di chuyển:

1 3 3 3 3 4
1 2 3 2 0 4
3 2 2 2 4 4
1 0 0 2 4 0
1 2 3 0 4 4

Số lượng cây phải di chuyển là 10.

---

Chú ý:

• Cán bộ coi thi không giải thích gì thêm;
• Các tệp dữ liệu vào là đúng đắn không cần kiểm tra;
• Làm bài với các tên tệp đúng như quy định trong đề, trong đó dấu * là phần mở rộng mặc định theo ngôn ngữ lập trình mà thí sinh sử dụng (ví dụ: CAU1.PAS, CAU1.CPP, …).