HSG lớp 9 Nam Định 2021-2022

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

MÔN TIN HỌC 4 bài: DEMUOC, SODEP, DAQUY, VANBAN

---

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 ước

Nếu số tự nhiên a chia hết cho số tự nhiên b thì ta nói b là ước số của a. Ví dụ: 20 có các ước số là 1, 2, 4, 5, 10, 20; số lượng ước của 20 là 6. Như vậy 20 có số lượng ước là chẵn.

Yêu cầu: Cho số tự nhiên n và dãy số tự nhiên x₁, x₂, …, xₙ. Đếm xem có bao nhiêu số có số lượng các ước là chẵn, bao nhiêu số có số lượng các ước là lẻ.

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

• Dòng 1: ghi số tự nhiên n (1 ≤ n ≤ 100).
• n dòng tiếp theo: mỗi dòng ghi một số tự nhiên xᵢ (1 ≤ xᵢ ≤ 10¹⁸).

Kết quả: Đưa ra tệp văn bản DEMUOC.OUT gồm 2 dòng:

• Dòng 1: ghi số lượng các số có số ước là chẵn.
• Dòng 2: ghi số lượng các số có số ước là lẻ.

Ví dụ:

DEMUOC.INP	DEMUOC.OUT	Giải thích
4 2 3 4 5	3 1	có 3 số có số lượng ước chẵn là 2, 3, 5; và 1 số có số lượng ước lẻ là 4

Bài 2. Số đẹp

Số nguyên dương N được gọi là đẹp nếu thỏa mãn hai điều kiện sau:

• N là số lẻ.
• N và (N + 1)/2 là số nguyên tố.

Ví dụ: N = 5 là số đẹp vì 5 là số lẻ, N = 5 và (N + 1)/2 = 3 là số nguyên tố.

Yêu cầu: Cho Q câu hỏi, câu hỏi thứ i gồm hai số nguyên Lᵢ, Rᵢ, cho biết có bao nhiêu số đẹp trong các số từ Lᵢ đến Rᵢ.

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

• Dòng 1 chứa số nguyên Q (1 ≤ Q ≤ 10⁵).
• Q dòng sau: dòng thứ i gồm hai số nguyên Lᵢ, Rᵢ (1 ≤ Lᵢ ≤ Rᵢ ≤ 10⁶).

Kết quả: Đưa ra tệp văn bản SODEP.OUT gồm Q dòng, dòng thứ i là kết quả câu hỏi thứ i.

Ví dụ:

SODEP.INP	SODEP.OUT
2 3 7 9 10	2 0

Bài 3. Đá quý

Công ty kinh doanh đá quý DQ có 26 loại đá quý khác nhau. Mỗi loại được kí hiệu bằng một chữ cái viết hoa trong bảng chữ cái tiếng Anh. Từ các loại đá trên người ta tạo ra các chuỗi đá quý khác nhau và lưu cấu trúc của chúng vào máy tính. Vì mỗi chuỗi có thể rất dài nên để tiết kiệm không gian lưu trữ người ta nén chuỗi như sau:

• Đọc lần lượt các kí tự trong chuỗi từ trái sang phải, nếu xâu con X có độ dài m xuất hiện liên tiếp k lần trong chuỗi thì thay bằng 3 giá trị: m, X, k.

Ví dụ: chuỗi MMPNQPNQABABM có thể nén lại như sau:

4 1 M 2 3 PNQ 2 2 AB 2 1 M 1

• Khi đọc lần lượt các kí tự từ trái sang phải: chuỗi gồm 4 đoạn, đoạn có độ dài 1 là M lặp lại 2 lần, đoạn có độ dài 3 là PNQ lặp lại 2 lần, đoạn có độ dài 2 là AB lặp lại 2 lần, đoạn có độ dài 1 là M lặp lại 1 lần.

Vì chuỗi hạt hình tròn nên có thể bắt đầu từ một vị trí bất kì theo hướng bất kì. Ta có thể có nhiều cách ghi khác nhau đối với mỗi chuỗi. Chuỗi trên cũng có thể được viết là MMMBABAQNPQNP và được nén như sau: 3 1 M 3 2 BA 2 3 QNP 2.

Yêu cầu: Cho 2 dòng mô tả chuỗi đá quý đã được nén. Kiểm tra 2 dòng này có mô tả cùng một chuỗi hay không?

Dữ liệu: Vào từ tệp văn bản DAQUY.INP gồm 2 dòng, mỗi dòng là mô tả về một chuỗi đá quý đã nén. Các phần trên 1 dòng cách nhau bởi 1 dấu cách, dữ liệu vào đảm bảo chiều dài của chuỗi ban đầu không quá 10⁴ kí tự.

Kết quả: Ghi vào tệp văn bản DAQUY.OUT gồm 2 dòng:

• Dòng 1: ghi xâu kí tự ‘CO’ nếu hai dòng mô tả cùng một chuỗi đá quý, ngược lại thì ghi xâu kí tự ‘KHONG’.
• Dòng 2: đưa ra độ dài của 2 chuỗi sau khi đã giải nén theo thứ tự đọc vào, mỗi số cách nhau 1 dấu cách.

Ví dụ:

DAQUY.INP	DAQUY.OUT
4 1 M 2 3 PNQ 2 2 AB 2 1 M 1 3 1 M 3 2 BA 2 3 QNP 2	CO 13 13
2 2 XY 3 1 K 6 1 2 CB 5	KHONG 12 10

Bài 4. Soạn văn bản

Đúng lúc An hào hứng làm bài tập tin học nhất thì bàn phím lại bị hỏng: chỉ gõ được các ký tự chữ cái. Nhiệm vụ của An là soạn thảo một văn bản chỉ sử dụng n từ trong một danh sách cho trước. An quyết định vẫn làm bài tập trên máy của mình, sau đó copy sang máy của một bạn khác trong lớp và chèn thêm dấu cách vào giữa các từ, giữa hai từ sẽ chèn đúng một dấu cách. Như vậy ít ảnh hưởng đến thời gian sử dụng máy của bạn nhất.

Ví dụ: với n = 5 và danh sách các từ cho trước là an, anh, han, tin, hoc; An soạn sẵn dòng anhanhoctin, sau đó mang sang máy của bạn và chèn thêm dấu cách thành anh an hoc tin.

Tuy nhiên khi bắt tay vào chèn dấu cách, An mới nhận thấy rằng vấn đề cũng không đơn giản vì có thể có nhiều cách, thậm chí có thể không có cách chèn nếu gõ văn bản sai. Ví dụ: với dòng anhanhoctin ta có một cách đặt dấu cách khác thỏa mãn là: an han hoc tin.

Yêu cầu: Cho n, danh sách các từ được sử dụng (mỗi từ có thể được sử dụng trong văn bản nhiều lần hoặc không dùng lần nào) và văn bản không có dấu cách. Hãy xác định số cách chèn kí tự trắng (dấu cách) để được một văn bản chỉ gồm các từ có trong n từ đã cho.

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

• Dòng đầu tiên chứa số nguyên n (1 < n ≤ 100).
• n dòng sau: mỗi dòng chứa một từ được sử dụng (mỗi từ không quá 20 ký tự, các từ khác nhau từng đôi một).
• Dòng cuối cùng chứa văn bản An đã gõ chứa không quá 100 kí tự.

Kết quả: Đưa ra tệp văn bản VANBAN.OUT một số nguyên xác định số cách chèn dấu cách.

Ví dụ:

VANBAN.INP	VANBAN.OUT
5 anh an han hoc tin anhanhoctin	2

(Giải thích: Hai cách đặt dấu cách là: anh an hoc tin; an han hoc tin)