HSG lớp 9 Quảng Trị 2021-2022

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

MÔN TIN HỌC 4 câu: 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).

Câu 1. Số đối lập

Ta gọi số ngược của một số là số tạo ra bằng cách viết các chữ số của số đã cho theo chiều từ phải qua trái (ví dụ: số 123 có số ngược là 321).

Một số nguyên X được gọi là số đối lập nếu X cùng với số ngược của nó là những số nguyên tố cùng nhau (tức có ước số chung lớn nhất bằng 1). Ví dụ: số 123 là một số đối lập vì có ước số chung lớn nhất của 123 và 321 bằng 1. Nhiệm vụ của bạn là lập trình để xác định một số nguyên dương đã cho có phải số đối lập hay không?

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

• Dòng 1: Số nguyên dương N (N ≤ 10³).
• Trong N dòng tiếp theo, mỗi dòng chứa một số nguyên dương aᵢ (aᵢ ≤ 2×10⁹).

Kết quả: ghi vào tệp CAU1.OUT

• Chứa N dòng, dòng thứ i ghi số 1 nếu số aᵢ tương ứng là số đối lập, ngược lại ghi 0.

Ví dụ:

CAU1.INP	CAU1.OUT
3 123 201 2021	1 0 1

Ràng buộc:

• Có 50% số test cho N ≤ 10² và aᵢ ≤ 2×10⁶;
• Có 20% số test cho N ≤ 10³ và aᵢ ≤ 2×10⁶;
• Có 30% số test cho N ≤ 10³ và aᵢ ≤ 2×10⁹.

Câu 2. Giải mật thư

Trong một trò chơi Teambuilding, nhóm của bạn nhận được một bức mật thư, đó là một bảng số có kích thước M×N, trên mỗi ô của bảng số chứa một số nguyên. Cùng với bức mật thư đó bạn cũng nhận được một nét vẽ hình xoắn ốc theo chiều kim đồng hồ. Bằng phán đoán của mình, bạn cùng nhóm của mình biết rằng để đọc được mật thư đó thì phải sắp xếp lại các ô số trong đó theo thứ tự tăng dần và theo chiều hình xoắn ốc như trong hình vẽ. Nhiệm vụ của bạn là lập trình thực hiện giải bức mật thư để giúp cả nhóm giành chiến thắng.

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

• Dòng 1: Chứa hai số nguyên dương M và N (M, N ≤ 1000).
• Trong M dòng tiếp theo, mỗi dòng chứa N số nguyên dương không lớn hơn 1000.

Kết quả: ghi vào tệp văn bản CAU2.OUT với cấu trúc như sau:

• Gồm M dòng, trên mỗi dòng chứa N số nguyên thể hiện bảng số kết quả giải bức mật thư (các số liền nhau trên cùng dòng được đặt cách nhau một dấu cách).

Ví dụ:

CAU2.INP	CAU2.OUT
4 5 2 5 1 7 9 1 12 2 5 6 0 3 3 1 8 4 11 4 2 3	0 1 1 1 2 5 6 7 8 2 5 12 11 9 2 4 4 3 3 3

Ràng buộc:

• Có 30% số test cho M, N ≤ 10;
• Có 40% số test cho M, N ≤ 100;
• Có 30% số test cho M, N ≤ 1000.

Câu 3. Số may mắn

Tại một diễn đàn Tin học, để tạo không khí vui vẻ người ta tổ chức cho những người tham gia trò chơi bốc thăm để có cơ hội nhận được những phần quà từ Ban tổ chức, cách thức như sau: Đầu tiên mỗi người tham gia được bốc thăm một mảnh giấy trong đó ghi một số nguyên dương N (N ≤ 10¹⁰⁰). Sau đó Ban tổ chức sẽ bốc thăm ngẫu nhiên một con số M (1 ≤ M ≤ 9). Mỗi người chơi sẽ cộng các chữ số của số N để được số N1, tiếp tục cộng các chữ số của N1 để được số N2 … quá trình cho đến khi nhận được một số có một chữ số. Nếu kết quả bằng M thì người chơi may mắn nhận được phần quà. Em hãy lập trình để giúp những người chơi xác định ai là người may mắn trúng thưởng.

Dữ liệu vào: tệp văn bản CAU3.INP, trong đó:

• Dòng đầu tiên chứa hai số K và M cách nhau một dấu cách, trong đó K là số người bốc thăm (K ≤ 1000).
• Trong số K dòng tiếp theo, dòng thứ i ghi một số N là con số mà người chơi thứ i bốc được.

Kết quả: ghi vào tệp văn bản CAU3.OUT, như sau: gồm K dòng trong đó dòng thứ i ghi số 1 tương ứng với người chơi bốc được số may mắn, ngược lại ghi 0.

Ví dụ:

CAU3.INP	CAU3.OUT
3 6 12345 6 123456789	1 1 0

Ràng buộc:

• Có 50% số test cho K ≤ 10² và N ≤ 10⁶;
• Có 20% số test cho K ≤ 10³ và N ≤ 10⁹;
• Có 30% số test cho K ≤ 10³ và N ≤ 10¹⁰⁰.

Câu 4. Tích cực đại

Nam rất yêu thích các con số lớn, vì vậy từ những số nguyên N mà Nam gặp, bạn ấy thường tìm cách sinh ra những số nguyên lớn nhất có thể được bằng cách biểu diễn N thành tổng các số hạng sao cho tích M của các số hạng đó là lớn nhất. Em hãy lập trình để giúp Nam tìm ra số nguyên lớn đó.

Dữ liệu vào: cho bởi tệp văn bản CAU4.INP gồm 1 dòng chứa số nguyên dương N (N ≤ 10000).

Kết quả: ghi vào tệp văn bản CAU4.OUT gồm 1 dòng chứa số M tìm được.

Ví dụ:

CAU4.INP	CAU4.OUT	Giải thích
5	6	5 = 2 + 3; 2 × 3 = 6
9	27	9 = 3 + 3 + 3; 3 × 3 × 3 = 27
13	108	13 = 3 + 3 + 3 + 4; 3 × 3 × 3 × 4 = 108

Ràng buộc:

• Có 40% số test cho N ≤ 50;
• Có 30% số test cho N ≤ 100;
• Có 30% số test cho N ≤ 10000.