Đề số 14 - Ôn thi HSG Tin học THCS

BỘ ĐỀ ÔN THI HỌC SINH GIỎI TIN HỌC THCS Bumbii Academy

ĐỀ SỐ 14 Thời gian làm bài: 150 phút
4 bài, tổng 20 điểm

---

Tổng quan đề thi

Bài	Tên bài	File chương trình	File dữ liệu vào	File kết quả	Điểm
1	Hệ nhị phân	NHIPHAN.*	NHIPHAN.INP	NHIPHAN.OUT	4
2	Ước chung	UCCHUNG.*	UCCHUNG.INP	UCCHUNG.OUT	4
3	Dãy nguyên tố liên tiếp	DAYNT.*	DAYNT.INP	DAYNT.OUT	6
4	Ghép đôi chia hết	CAPCHIAK.*	CAPCHIAK.INP	CAPCHIAK.OUT	6

Dấu * được thay bằng py hoặc cpp tùy theo ngôn ngữ lập trình sử dụng.

Bài 1. Hệ nhị phân (4 điểm)

Yêu cầu: Cho số tự nhiên n, hãy viết n trong hệ nhị phân (hệ cơ số 2) và cho biết biểu diễn đó có bao nhiêu chữ số 1.

Dữ liệu vào: Từ file văn bản NHIPHAN.INP gồm một số tự nhiên n.

Kết quả: Ghi ra file văn bản NHIPHAN.OUT gồm hai dòng: biểu diễn nhị phân của n (không có chữ số 0 thừa ở đầu; n = 0 thì ghi 0) và số lượng chữ số 1.

Ví dụ:

NHIPHAN.INP	NHIPHAN.OUT	Giải thích
103	1100111 5	103 = 64 + 32 + 4 + 2 + 1.

Ràng buộc:

• Có 50% số test với n ≤ 10⁹.
• Có 50% số test với n ≤ 10¹⁸.

Bài 2. Ước chung (4 điểm)

Cho hai số nguyên dương m và n.

Yêu cầu: Tìm ước chung lớn nhất của m và n, cho biết m và n có bao nhiêu ước chung (dương) và tổng các ước chung đó.

Dữ liệu vào: Từ file văn bản UCCHUNG.INP gồm một dòng chứa hai số nguyên dương m, n.

Kết quả: Ghi ra file văn bản UCCHUNG.OUT gồm hai dòng: dòng thứ nhất ghi ƯCLN(m, n); dòng thứ hai ghi số lượng ước chung và tổng của chúng.

Ví dụ:

UCCHUNG.INP	UCCHUNG.OUT	Giải thích
12 30	6 4 12	Các ước chung là 1, 2, 3, 6.

Ràng buộc:

• Có 50% số test với m, n ≤ 10⁶.
• Có 50% số test với m, n ≤ 10¹².

Bài 3. Dãy nguyên tố liên tiếp (6 điểm)

Cho dãy n số nguyên dương a₁, a₂, …, a_n. Một đoạn nguyên tố là một đoạn các phần tử liên tiếp của dãy mà mọi phần tử đều là số nguyên tố.

Yêu cầu: Tìm đoạn nguyên tố dài nhất. Nếu có nhiều đoạn dài nhất thì chọn đoạn có tổng lớn nhất; nếu vẫn còn nhiều đoạn thì chọn đoạn xuất hiện đầu tiên.

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

• Dòng đầu tiên chứa số nguyên dương n.
• Dòng thứ hai chứa n số nguyên dương a₁, a₂, …, a_n.

Kết quả: Ghi ra file văn bản DAYNT.OUT: nếu dãy không có số nguyên tố nào thì ghi 0. Ngược lại, dòng thứ nhất ghi độ dài và tổng của đoạn tìm được, dòng thứ hai ghi các phần tử của đoạn.

Ví dụ:

DAYNT.INP	DAYNT.OUT	Giải thích
8 18 17 23 21 13 3 7 10	3 23 13 3 7
5 23 11 8 5 7	2 34 23 11	Hai đoạn dài 2 là (23, 11) tổng 34 và (5, 7) tổng 12.

Ràng buộc:

• Có 40% số test với n ≤ 1000, a_i ≤ 10⁴.
• Có 60% số test với n ≤ 10⁵, a_i ≤ 10⁶.

Bài 4. Ghép đôi chia hết (6 điểm)

Cô giáo có n tấm thẻ, tấm thẻ thứ i ghi số nguyên dương a_i. Cô muốn chọn ra hai tấm thẻ khác nhau sao cho tổng hai số ghi trên đó chia hết cho k.

Yêu cầu: Đếm số cách chọn (hai cách được coi là khác nhau nếu có ít nhất một tấm thẻ khác nhau).

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

• Dòng đầu tiên chứa hai số nguyên dương n và k (k ≤ 10⁹).
• Dòng thứ hai chứa n số nguyên dương a₁, a₂, …, a_n (a_i ≤ 10⁹).

Kết quả: Ghi ra file văn bản CAPCHIAK.OUT một số nguyên là số cách chọn.

Ví dụ:

CAPCHIAK.INP	CAPCHIAK.OUT	Giải thích
6 5 1 4 9 6 5 10	5	Các cặp (1, 4), (1, 9), (4, 6), (9, 6), (5, 10).

Ràng buộc:

• Có 40% số test với n ≤ 2000.
• Có 60% số test với n ≤ 2 × 10⁵.

Lời giải và bộ test của đề này (có phí)

Hướng dẫn giải chi tiết, code Python và C++ đã được kiểm chứng, cùng bộ test và công cụ chấm cham.py, có trong bộ tài liệu đầy đủ (có phí).

Thầy cô và các em muốn mua bộ tài liệu vui lòng liên hệ tác giả qua Zalo 0972465159 hoặc Facebook.

Muốn xem trước cách trình bày lời giải, hãy xem Đề số 01 (có lời giải miễn phí).

Do số lượng đề bài, bài giải và bộ test rất nhiều nên tác giả đang kiểm tra từng bước. Thầy cô và các em học sinh nếu thấy sai sót xin vui lòng liên hệ tác giả qua Facebook hoặc Zalo (0972465159). Xin chân thành cảm ơn.