HSG lớp 9 Thanh Hóa 2023-2024

ĐỀ THI CHỌN HỌC SINH GIỎI LỚP 9 TỈNH THANH HÓA Năm học 2023 - 2024

MÔN TIN HỌC 4 bài: CAU1 - CAU4

---

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. Chuẩn hoá xâu

Lam đặt tên các biến trong mã nguồn chương trình của mình theo chuẩn PropCase. Chuẩn PropCase quy ước như sau:

• Tên biến gồm các chữ cái Latinh ‘A’..‘Z’, ‘a’..‘z’ và chữ số ‘0’..‘9’;
• Chữ cái đầu tiên của tên biến không bắt đầu bằng chữ số ‘0’..‘9’;
• Chữ cái đầu tiên của mỗi từ tiếp theo trong tên biến được viết in hoa;

Ví dụ: DiemTbHk1, lop9A10, …

Lam muốn tải mã nguồn của mình lên Github với các biến được đặt tên theo chuẩn join_case có quy ước:

• Tên biến gồm các chữ cái Latinh ‘a’..‘z’, chữ số ‘0’..‘9’ và dấu gạch nối ‘_’;
• Không bắt đầu bằng chữ số ‘0’..‘9’ hoặc dấu gạch nối ‘_’;
• Hai từ trong tên biến được tách nhau bởi dấu ‘_’;

Ví dụ: diem_tb_hk1, lop9_a10, …

Yêu cầu: Hãy giúp Lam đổi tên biến từ chuẩn PropCase sang chuẩn join_case.

Dữ liệu: Vào từ tệp CAU1.INP gồm một xâu độ dài n (1 ≤ n ≤ 1000) là một tên biến đặt theo chuẩn PropCase.

Kết quả: Ghi ra tệp CAU1.OUT một xâu là tên biến đặt lại theo chuẩn join_case.

Ví dụ:

CAU1.INP	CAU1.OUT
DiemTbHk1	diem_tb_hk1
lop9A10	lop9_a10

Bài 2. Gà và chó

Đếm số cách mua một con gà và một con chó sao cho tổng số tiền phải trả để mua cả hai con không vượt quá n (3 ≤ n ≤ 2×10⁹). Biết số tiền mua gà luôn ít hơn số tiền mua chó. Số tiền mua gà và mua chó là các số nguyên dương.

Dữ liệu: Vào từ tệp CAU2.INP gồm một dòng ghi số nguyên dương n.

Kết quả: Ghi ra tệp CAU2.OUT gồm một dòng ghi một số nguyên là đáp số của bài toán.

Ví dụ:

CAU2.INP	CAU2.OUT	Giải thích
5	4	Có 4 cách mua cặp (gà, chó) phải trả tổng số tiền không quá 5 là: (1,2); (1,3); (1,4); (2,3).

Ràng buộc:

• Có 70% số test ứng với 70% số điểm của bài có n ≤ 10³;
• Có 20% số test ứng với 20% số điểm của bài có n ≤ 10⁶;
• Có 10% số test ứng với 10% số điểm của bài có n ≤ 2×10⁹.

Bài 3. Số đặc biệt

Một số tự nhiên được gọi là số đối xứng nếu viết các chữ số của nó theo chiều ngược lại thì vẫn thu được chính nó. Ví dụ, các số 88, 858 là những số đối xứng.

Một số được coi là số đặc biệt nếu nó là số đối xứng và có từ 3 ước số nguyên tố khác nhau trở lên. Ví dụ: 858 là số đặc biệt vì nó là số đối xứng và có 4 ước nguyên tố khác nhau là 2, 3, 11, 13; còn số 88 không là số đặc biệt vì nó đối xứng nhưng chỉ có 2 ước nguyên tố khác nhau là 2, 11.

Yêu cầu: Cho 2 số nguyên dương a, b. Tính tổng các số đặc biệt trong đoạn từ a đến b.

Dữ liệu: Vào từ tệp CAU3.INP chứa hai số nguyên dương a, b (1 ≤ a < b ≤ 10⁷).

Kết quả: Ghi ra tệp CAU3.OUT một số duy nhất là tổng tìm được.

Ví dụ:

CAU3.INP	CAU3.OUT
88 858	11605

Ràng buộc:

• Có 60% số test ứng với 60% số điểm của bài có 1 ≤ a < b ≤ 10³;
• Có 20% số test ứng với 20% số điểm của bài có 10³ < a < b ≤ 10⁶;
• Có 20% số test ứng với 20% số điểm của bài có 10⁶ < a < b ≤ 10⁷.

Bài 4. Đường thẳng

Trên cùng một mặt phẳng toạ độ cho n đường thẳng phân biệt đánh số từ 1 tới n. Đường thẳng i có dạng y = aᵢx + bᵢ (1 ≤ i ≤ n).

Yêu cầu: Đếm số cặp đường thẳng song song trong n đường thẳng trên.

Dữ liệu: Vào từ tệp CAU4.INP gồm:

• Dòng đầu tiên là số nguyên n (2 ≤ n ≤ 3×10⁶);
• n dòng sau, mỗi dòng ghi 2 số nguyên aᵢ, bᵢ biểu diễn đường thẳng thứ i (|aᵢ|, |bᵢ| ≤ 10⁹; 1 ≤ i ≤ n).

Kết quả: Ghi ra tệp CAU4.OUT một số nguyên là đáp số của bài.

Ví dụ:

CAU4.INP	CAU4.OUT
3 1 2 1 -2 0 2	1
3 1 2 1 -2 1 -4	3

Ràng buộc:

• Có 50% số test ứng với 50% số điểm của bài có 2 ≤ n ≤ 10³; |aᵢ|, |bᵢ| ≤ 10⁵;
• Có 25% số test ứng với 25% số điểm của bài có 10³ < n ≤ 10⁵; |aᵢ|, |bᵢ| ≤ 10⁵;
• Có 25% số test ứng với 25% số điểm của bài có 10⁵ < n ≤ 3×10⁶; |aᵢ|, |bᵢ| ≤ 10⁹.