HSG lớp 9 Cần Thơ 2021-2022

ĐỀ THI CHỌN HỌC SINH GIỎI LỚP 9 THÀNH PHỐ CẦN THƠ Năm học 2021 - 2022

MÔN TIN HỌC 4 bài: DEMSO, SOLE, KIEUMOI, QUANXE

---

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. Đếm số

Cho một dãy số gồm n số nguyên.

Yêu cầu: Hãy lập trình xác định số lượng các số chia hết cho 3 và không chia hết cho 9 trong dãy số đã cho.

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

• Dòng đầu ghi một số nguyên dương n (n ≤ 10⁶).
• Dòng thứ hai ghi n số nguyên cho biết dãy số, các số trong dãy có giá trị tuyệt đối không vượt quá 10⁹.

Kết quả: Ghi ra file văn bản DEMSO.OUT chứa một số nguyên là kết quả tìm được.

Ví dụ:

DEMSO.INP	DEMSO.OUT
6 1 2 3 15 816 18	4

Chú ý

Ví dụ trong bản đánh máy có vẻ bị lỗi: với dãy 1 2 3 15 816 18 chỉ có 3 số chia hết cho 3 mà không chia hết cho 9 (3, 15, 816). Giữ nguyên văn để đối chiếu với đề gốc.

Bài 2. Số lẻ

Nam có thói quen thường xuyên thực hiện các phép tính nhanh để rèn luyện khả năng tư duy. Những lần Nam di chuyển bằng xe buýt, nhìn qua cửa sổ xe buýt, Nam thoáng thấy một biển quảng cáo. Nam không chú ý tới nội dung mà chỉ nhớ trên đó có hai số nguyên dương a và b (a ≤ b). Nam có trí nhớ tốt và có khả năng tính nhanh cũng rất tốt, Nam đã tính được số lượng số nguyên trong đoạn [a; b] có tổng các chữ số là số lẻ. Khi về tới nhà, Nam kiểm tra trên máy tính đã xác định đúng số lượng số nguyên trong đoạn [a; b] có tổng các chữ số là số lẻ.

Yêu cầu: Hãy lập trình xác định kết quả mà Nam đã tính được.

Dữ liệu: Vào từ file văn bản SOLE.INP gồm một dòng chứa hai số nguyên a và b (1 ≤ a ≤ b ≤ 10⁹).

Kết quả: Ghi ra file văn bản SOLE.OUT chứa một số nguyên là kết quả Nam đã tính được.

Ví dụ:

SOLE.INP	SOLE.OUT	Giải thích
10 20	5	Trong ví dụ, các số có tổng các chữ số là số lẻ gồm: 10, 12, 14, 16, 18

Ràng buộc:

• Có ít nhất 70% số test ứng với 70% số điểm của bài thỏa mãn: 1 ≤ a ≤ b ≤ 10⁶.
• Có 30% số test còn lại ứng với 30% số điểm của bài thỏa mãn: 1 ≤ a ≤ b ≤ 10⁹.

Bài 3. Kiểu mới

Trong công ty ABC, văn bản gốc chứa các từ chỉ gồm chữ cái La tinh thường và dấu cách. Khi chuyển văn bản này sang chuẩn CamelCase: chữ cái đầu tiên của văn bản có thể bắt đầu bằng chữ cái thường hoặc hoa; chữ cái đầu tiên của mỗi từ tiếp theo được viết hoa và không có dấu cách. Khi Giám đốc điều hành cũ về hưu, Giám đốc điều hành mới quyết định sẽ lưu trữ văn bản theo chuẩn snake_case. Chuẩn snake_case được xây dựng theo quy tắc sau: giữa hai từ được cách nhau bởi dấu _, tất cả các chữ cái trong văn bản đều là chữ cái thường. Ví dụ, ở chuẩn CamelCase thông tin có dạng abCde thì sang chuẩn snake_case sẽ có dạng ab_cde.

Yêu cầu: Hãy lập trình đổi thông tin từ chuẩn CamelCase sang chuẩn snake_case.

Dữ liệu: Vào từ file văn bản KIEUMOI.INP gồm:

• Dòng đầu tiên chứa số nguyên n (1 < n ≤ 100).
• Trong n dòng tiếp theo, mỗi dòng chứa một xâu độ dài không quá 1000 ký tự theo chuẩn CamelCase.

Kết quả: Ghi ra file văn bản KIEUMOI.OUT các xâu đã cho dưới dạng chuẩn snake_case, mỗi xâu trên một dòng.

Ví dụ:

KIEUMOI.INP	KIEUMOI.OUT
4 CamelCase camelCase toBeOrNotToBe ABCDE	camel_case camel_case to_be_or_not_to_be a_b_c_d_e

Bài 4. Quân xe

Trên bàn có một bàn cờ là lưới ô vuông kích thước n × n. Các hàng được đánh số từ 1 đến n từ trên xuống dưới, các cột được đánh số từ trái qua phải bắt đầu từ 1. Người ta đặt n quân xe lên bàn cờ sao cho mỗi hàng có đúng một quân xe và mỗi cột cũng có đúng một quân xe. Mỗi quân xe được xác định trên bàn cờ có vị trí ở hàng x, cột y (với 1 ≤ x, y ≤ n). Khi mang bàn cờ này sang bàn khác, bàn cờ bị xoay đi một góc 90° theo chiều kim đồng hồ.

Yêu cầu: Hãy xác định vị trí (hàng, cột) của từng quân xe theo trạng thái mới của bàn cờ và đưa ra các vị trí tìm được theo chiều tăng dần của hàng.

Dữ liệu: Vào từ file văn bản QUANXE.INP gồm:

• Dòng đầu tiên chứa số nguyên n (1 ≤ n ≤ 10⁵).
• n dòng tiếp theo, mỗi dòng chứa hai số nguyên x và y là vị trí hàng x, cột y của mỗi quân xe trong bàn cờ lúc đầu.

Kết quả: Ghi ra file văn bản QUANXE.OUT chứa n dòng, mỗi dòng hai số nguyên là vị trí của quân xe theo trạng thái mới của bàn cờ.

Ràng buộc:

• Có ít nhất 70% số test ứng với 70% số điểm của bài thỏa mãn: 1 ≤ n ≤ 10³.
• Có 30% số test còn lại ứng với 30% số điểm của bài thỏa mãn: 1 ≤ n ≤ 10⁵.

Ví dụ:

QUANXE.INP	QUANXE.OUT
5 1 4 2 2 3 3 4 5 5 1	1 1 2 4 3 3 4 5 5 2