HSG lớp 9 Quảng Nam 2023-2024

ĐỀ THI HỌC SINH GIỎI LỚP 9 CẤP TỈNH TỈNH QUẢNG NAM Năm học 2023 - 2024

MÔN TIN HỌC 4 bài: SONTTQ, SMTHU, MATMA, TTICH

---

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. Số nguyên tố Q

Cho một số nguyên dương N (N ≤ 5×10¹⁷). Tìm chữ số nhỏ thứ Q trong N và kiểm tra nó có phải là số nguyên tố hay không.

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

• Dòng đầu tiên chứa số N;
• Dòng thứ hai chứa số Q (0 < Q ≤ 9).

Kết quả: Ghi ra file văn bản SONTTQ.OUT gồm số nhỏ thứ Q và từ “Yes” nếu là số nguyên tố hoặc từ “No” nếu không phải là số nguyên tố. Trường hợp không tìm thấy chữ số nhỏ thứ Q thì ghi −1 (các giá trị cách nhau một khoảng trắng).

Ví dụ:

SONTTQ.INP	SONTTQ.OUT
924567 5	7 Yes
5568924 4	6 No
55557 5	-1

Ràng buộc:

• Có 60% test tương ứng 60% số điểm của bài với 0 < N ≤ 10⁶;
• Có 30% test tương ứng 30% số điểm của bài với 10⁶ < N ≤ 10⁹;
• Có 10% test tương ứng 10% số điểm của bài với 10⁹ < N ≤ 5×10¹⁷.

Bài 2. Sức mạnh

Để tạo sân chơi bổ ích cũng như tìm kiếm nguồn nhân tài cho cuộc thi lập trình game tại Ấn Độ sẽ diễn ra trong năm tới, ở vòng thi sơ loại, ban tổ chức mô phỏng trò chơi khá hấp dẫn. Yêu cầu trò chơi được ghi cụ thể như sau:

Trò chơi này chỉ dành cho một người tham gia, mà trong đó người chơi phải trải qua q lượt chơi khác nhau để tiêu diệt hết các con thú. Lượt chơi thứ i sẽ xuất hiện con thú thứ i có giá trị aᵢ và có chỉ số sức mạnh bằng tổng các ước nguyên dương của aᵢ (1 ≤ i ≤ q).

Là người đam mê lập trình, bạn hãy tính sức mạnh của q con thú đã xuất hiện trong trò chơi trên.

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

• Dòng thứ nhất chứa duy nhất số q;
• Dòng thứ hai lần lượt chứa q số: a₁, a₂, …, a_q.

Kết quả: Ghi ra file văn bản SMTHU.OUT gồm q số, số thứ i thể hiện sức mạnh của con thú thứ i (các giá trị cách nhau một khoảng trắng).

Ví dụ:

SMTHU.INP	SMTHU.OUT
3 2 4 5	3 7 6
4 10 34 16 45	18 54 31 78

Giải thích test 1: Gọi G(x) là tổng các ước của x. G(2) = 1 + 2 = 3; G(4) = 1 + 2 + 4 = 7; G(5) = 1 + 5 = 6.

Ràng buộc:

• Có 50% test tương ứng 50% số điểm của bài với q ≤ 10⁴; aᵢ ≤ 10³ (1 ≤ i ≤ q);
• Có 50% test tương ứng 50% số điểm của bài với q = 10; aᵢ ≤ 10⁹ (1 ≤ i ≤ q).

Bài 3. Mật mã

Trong cuộc chiến tranh chống Mỹ của Việt Nam, tổng chỉ huy quân sự Mỹ truyền đi bảng mật mã và đã bị quân ta lấy được. Mật mã của chúng là xâu ký tự bao gồm các chữ cái, chữ số (không phân biệt chữ hoa, chữ thường) và các khoảng trắng.

Cấp trên yêu cầu cho quân đội ta phải nhanh chóng dịch ra mật mã để phá huỷ kế hoạch tác chiến của địch. Mật mã sau khi chuyển đổi bao gồm:

• Khoá mở hòm tài liệu là tổng các chữ số trong bảng mật mã;
• Thông tin triển khai kế hoạch tác chiến của địch là dãy các từ sau khi đảo ngược các ký tự trong mỗi từ (không chứa ký tự số).

Dữ liệu vào: Từ file văn bản MATMA.INP gồm một dòng chứa xâu s cho trước (s không quá 10⁶ ký tự, giữa các từ có thể cách nhau một hoặc nhiều khoảng trắng).

Kết quả: Ghi ra file văn bản MATMA.OUT là mật mã sau khi chuyển đổi gồm khoá mở hòm tài liệu và thông tin triển khai kế hoạch tác chiến. (các giá trị cách nhau một khoảng trắng).

Ví dụ:

MATMA.INP	MATMA.OUT
4ob43 hn54ib0	20 bo binh
n6a5t02 gn6oc4 h3n2ahn	28 tan cong nhanh

Ràng buộc:

• Có 60% test tương ứng 60% số điểm của bài với độ dài xâu s không quá 255 ký tự;
• Có 40% test tương ứng 40% số điểm của bài với độ dài xâu s không quá 10⁶ ký tự.

Bài 4. Thành tích

Đầu tháng ba, Sở GDĐT tỉnh S có tổ chức giải thể thao năm học 2023 - 2024 cho học sinh phổ thông trên toàn tỉnh, nhằm tìm ra những học sinh có năng khiếu thể thao tạo nguồn tham gia Hội khoẻ Phù Đổng toàn quốc sắp đến. Tại cuộc thi, vì có rất nhiều đơn vị tham dự ở nhiều bộ môn nên có các đơn vị có thành tích bằng nhau.

Giả sử đơn vị A thi n môn, đơn vị B thi m môn, ban tổ chức quy định thành tích bằng nhau của hai đơn vị A, B khi và chỉ khi tích điểm n môn thi của đơn vị A tương ứng là a₁, a₂, …, aₙ bằng tích điểm m môn thi của đơn vị B tương ứng là b₁, b₂, …, b_m.

Yêu cầu: Với khả năng lập trình của bạn, hãy giúp Sở GDĐT tỉnh S kiểm tra thành tích của hai đơn vị cho trước có bằng nhau hay không.

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

• Dòng đầu tiên chứa số nguyên t là số bộ test cần kiểm tra;
• Tiếp theo là t nhóm dòng, mỗi nhóm dòng mô tả một bộ test bao gồm:
  • Dòng đầu tiên chứa hai số nguyên n và m (1 ≤ n, m ≤ 100);
  • Dòng thứ hai chứa n số nguyên dương a₁, a₂, …, aₙ (1 ≤ aᵢ < 10⁷);
  • Dòng thứ ba m số nguyên dương b₁, b₂, …, b_m (1 ≤ bᵢ < 10⁷).

Kết quả: Ghi ra file văn bản TTICH.OUT gồm t dòng, dòng thứ i ghi từ “YES” nếu thành tích hai đội bằng nhau, ngược lại ghi từ “NO” tương ứng bộ test thứ i.

Ví dụ:

TTICH.INP	TTICH.OUT
2 2 3 9 3 3 3 3 3 3 5 4 2 2 3 5	YES NO

Ràng buộc:

• Có 60% test tương ứng 60% số điểm của bài với t ≤ 10, 1 ≤ n, m ≤ 10, 1 ≤ aᵢ, bᵢ ≤ 10²;
• Có 40% test tương ứng 40% số điểm của bài với t = 5, 1 ≤ n, m ≤ 50, 1 ≤ aᵢ, bᵢ < 10⁷.