HSG lớp 9 Quảng Trị 2019-2020

ĐỀ THI CHỌN HỌC SINH GIỎI LỚP 9 TỈNH QUẢNG TRỊ Năm học 2019 - 2020

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. Kiểm tra số nguyên tố

Số nguyên tố là số tự nhiên chỉ có hai ước là 1 và chính nó.

Yêu cầu: Kiểm tra xem số nguyên n có phải là số nguyên tố hay không.

Dữ liệu vào: Đọc từ tệp văn bản CAU1.INP có cấu trúc như sau: dòng đầu ghi T là số lượng các số cần kiểm tra (1 ≤ T ≤ 100), trong T dòng tiếp theo, mỗi dòng ghi một số nguyên n.

Kết quả: Ghi ra tệp văn bản CAU1.OUT gồm T dòng, mỗi dòng ghi kết quả tương ứng của từng số được kiểm tra; nếu n là số nguyên tố thì ghi 1, ngược lại ghi 0.

Ví dụ:

CAU1.INP	CAU1.OUT
2 4 2	0 1

Ràng buộc:

• Có 50% số test 1 ≤ n ≤ 30000;
• Có 30% số test 30000 < n ≤ 10⁷;
• Có 20% số test |n| ≤ 10⁹.

Bài 2. Tìm mật khẩu

Mật khẩu để mở khóa phần mềm là một dãy gồm 6 kí tự số trong hệ thập phân. Nhà sản xuất đã mã hóa mật khẩu đó thành một xâu kí tự S gồm các kí tự trong bảng mã ASCII. Để xác định mật khẩu này, ta tính tổng các chữ số trong xâu S, nếu tổng này chưa đủ 6 chữ số thì thêm các số 0 vào phía bên trái tổng đó sao cho đủ 6 kí tự.

Yêu cầu: Cho xâu chứa mật khẩu S, hãy xác định mật khẩu tìm được từ trong xâu S.

Dữ liệu vào: Đọc từ tệp văn bản CAU2.INP ghi xâu kí tự S.

Kết quả: Ghi ra tệp văn bản CAU2.OUT mật khẩu tìm được.

Ví dụ:

CAU2.INP	CAU2.OUT
Tin 2019-2020	000016

Ràng buộc:

• Có 80% số test xâu S có không quá 255 kí tự;
• Có 20% số test xâu có nhiều hơn 255 và không quá 10⁵ kí tự.

Bài 3. Trò chơi

Khu du lịch có n trò chơi khác nhau được đánh chỉ số từ 1 đến n. Tại mỗi lượt chơi, người chơi được quyền chọn tham gia một hoặc nhiều trò chơi liên tiếp nhau, mỗi trò chơi chỉ được chơi đúng một lần.

Đối với Nam, trò chơi thứ i có độ yêu thích aᵢ (1 ≤ i ≤ n; |aᵢ| ≤ 10⁹). Nam luôn chọn cách chơi sao cho tổng độ yêu thích thu được sau khi kết thúc lượt chơi lớn nhất.

Yêu cầu: Tính tổng độ yêu thích lớn nhất có thể thu được biết rằng Nam chỉ tham gia một lượt chơi và chơi ít nhất một trò chơi.

Dữ liệu vào: Đọc từ tệp văn bản CAU3.INP có cấu trúc như sau:

• Dòng đầu tiên ghi số nguyên dương n.
• Dòng thứ hai ghi lần lượt a₁, a₂, …, aₙ, cách nhau một dấu cách.

Kết quả: Ghi ra tệp văn bản CAU3.OUT một số duy nhất là tổng độ yêu thích lớn nhất mà Nam có thể thu được sau khi kết thúc lượt chơi.

Ví dụ:

CAU3.INP	CAU3.OUT	Giải thích
5 2 -5 4 -2 3	5	Nam chọn chơi các trò 3, 4, 5 có tổng độ yêu thích là 4 + (−2) + 3 = 5

Ràng buộc:

• Có 50% số test n ≤ 500;
• Có 30% số test 500 < n ≤ 5000;
• Có 20% số test 5000 < n ≤ 2×10⁵.

Bài 4. Tập trận

Trong đợt tập trận trên biển, tàu ngầm GMII thực hiện bắn n quả đạn pháo, quả thứ i (1 ≤ i ≤ n) bắn trúng mục tiêu ở vị trí có tọa độ (xᵢ, yᵢ). Một mục tiêu có thể bị nhiều quả đạn pháo bắn trúng.

Yêu cầu: Xác định số lượng cặp quả đạn pháo cùng bắn trúng một mục tiêu.

Dữ liệu vào: Đọc từ tệp văn bản CAU4.INP có cấu trúc như sau:

• Dòng đầu ghi số nguyên dương n;
• Dòng thứ i trong n dòng tiếp theo ghi hai số nguyên xᵢ, yᵢ cách nhau một dấu cách.

Kết quả: Ghi ra tệp văn bản CAU4.OUT một số duy nhất là số lượng cặp đạn pháo cùng bắn trúng một mục tiêu.

Ví dụ:

CAU4.INP	CAU4.OUT	Giải thích
6 1 1 2 2 1 1 1 1 2 1 2 2	4	Các cặp quả đạn pháo cùng bắn trúng một mục tiêu là: (1,3); (1,4); (3,4) và (2,6).

Ràng buộc:

• Có 50% số test 1 ≤ n ≤ 10³; 0 ≤ |xᵢ|, |yᵢ| ≤ 10³;
• Có 30% số test 10³ < n ≤ 10⁵; 0 ≤ |xᵢ|, |yᵢ| ≤ 10³;
• Có 20% số test 10³ < n < 2×10⁵; 0 ≤ |xᵢ|, |yᵢ| ≤ 10⁹.