HSG lớp 9 Thừa Thiên Huế 2020-2021

SỞ GIÁO DỤC VÀ ĐÀO TẠO THỪA THIÊN HUẾ ĐỀ THI CHÍNH THỨC
(Đề thi gồm 03 trang)

KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH LỚP 9 THCS Năm học 2020 - 2021
Môn thi: Tin học
Thời gian làm bài: 150 phút (không kể thời gian giao đề)

---

I. Cấu trúc bài thi

Bài	Tên bài	File nguồn	File dữ liệu vào	File kết quả
Bài 1	NGUYÊN TỐ SINH ĐÔI	TWIN.*	TWIN.INP	TWIN.OUT
Bài 2	SẮP XẾP SỐ	CURIOUS.*	CURIOUS.INP	CURIOUS.OUT
Bài 3	GHÉP BÌA	BUILD.*	BUILD.INP	BUILD.OUT
Bài 4	THAM QUAN	VISIT.*	VISIT.INP	VISIT.OUT

II. Yêu cầu: Thí sinh lập trình giải quyết các bài toán sau.

Bài 1. Nguyên tố sinh đôi (4.0 điểm)

Số nguyên tố là số chỉ có đúng hai ước số là 1 và chính nó. Trong lý thuyết số học, hai số nguyên tố p và q được gọi là cặp số nguyên tố sinh đôi nếu p − q = 2. Cho trước số tự nhiên n (1 < n ≤ 100000).

Yêu cầu: Tìm tất cả các cặp số nguyên tố sinh đôi có giá trị không vượt quá n.

Dữ liệu vào: Cho bởi file TWIN.INP chứa số n.

Kết quả: Ghi ra file TWIN.OUT tất cả các cặp số nguyên tố sinh đôi có giá trị không vượt quá n.

Ví dụ:

TWIN.INP	TWIN.OUT
15	1: [3,5] 2: [5,7] 3: [11,13]

Bài 2. Sắp xếp số (5.0 điểm)

Cho ma trận kích thước 2×n.

Yêu cầu: Hãy tìm cách điền các số từ 1 đến 2×n vào các ô sao cho tổng giá trị các số trên mỗi dòng đều bằng nhau, tổng giá trị các số trên mỗi cột đều bằng nhau.

Dữ liệu vào: Cho bởi file CURIOUS.INP chứa số n (1 < n ≤ 35) nguyên dương.

Kết quả: Ghi ra file CURIOUS.OUT ma trận có kích thước 2×n chứa các số từ 1 đến 2×n được sắp xếp thỏa mãn yêu cầu trên.

• Dòng cuối ghi giá trị tổng của mỗi dòng.
• Nếu không tìm được cách sắp xếp các số theo yêu cầu thì ghi “No Solution”.

Ví dụ:

CURIOUS.INP	CURIOUS.OUT
4	1 7 6 4 8 2 3 5 18

Bài 3. Ghép bìa (5.0 điểm)

Để rèn luyện tư duy toán học cho học sinh, cô giáo cắt nhiều mảnh bìa màu xanh và màu đỏ có kích thước lần lượt bằng 1×1 và 1×2 rồi yêu cầu các em học sinh ghép chúng thành những tấm bảng có kích thước bằng 1×n (1 ≤ n ≤ 100).

Yêu cầu: Hãy cho biết với mỗi giá trị của i (i = 1..n) thì các em học sinh sẽ có bao nhiêu cách để ghép các mảnh bìa có màu sắc, kích thước như trên thành tấm bảng có kích thước tương ứng theo cô giáo yêu cầu.

Dữ liệu vào: Cho bởi file BUILD.INP chứa số n.

Kết quả: Ghi ra file BUILD.OUT gồm n dòng, dòng thứ i chứa giá trị i và một số nguyên thể hiện số cách ghép bìa tương ứng với kích thước tấm bảng được yêu cầu.

Ví dụ:

BUILD.INP	BUILD.OUT
3	1: 1 2: 2 3: 3

Bài 4. Tham quan (6.0 điểm)

VMschools là hệ thống trường song ngữ đào tạo liên thông từ cấp Tiểu học đến Trung học phổ thông trong một môi trường giáo dục toàn diện “Đức - Trí - Thể - Mỹ”.

Nhân dịp kỉ niệm 10 năm ngày thành lập trường, trường muốn tổ chức cho các em học sinh đi tham quan tại một số địa điểm.

Trường có m khối, mỗi khối có n lớp, mỗi lớp có k (1 < k < 200) học sinh đăng kí tham gia.

Ban đại diện cha mẹ học sinh của trường, của các lớp đều có cử ít nhất một người tham gia để hỗ trợ nhà trường quản lý các em học sinh nhằm đảm bảo an toàn cho chuyến đi.

Căn cứ vào số lượng học sinh đăng ký tham gia, trường đã hợp đồng hai chiếc xe du lịch loại lớn để phục vụ tất cả các em.

Yêu cầu: Hãy phân chia, bố trí học sinh giữa các khối, các lớp ngồi ở hai xe phù hợp để số lượng học sinh giữa hai xe chênh lệch nhau ít nhất và cho biết mỗi xe sẽ chở bao nhiêu em?

Dữ liệu vào: Cho bởi file VISIT.INP bao gồm:

• Dòng thứ nhất chứa 2 số m, n (1 < m ≤ 15, 1 < n ≤ 20) lần lượt là số khối và số lớp trong mỗi khối.
• m dòng tiếp theo, mỗi dòng gồm n số thể hiện số học sinh mỗi lớp đăng ký tham gia chuyến đi, các số cách nhau một khoảng trắng.

Kết quả: Ghi ra file VISIT.OUT bao gồm:

• m dòng đầu, mỗi dòng gồm n số 1 và 0 kí hiệu xe thứ nhất, xe thứ hai sẽ phục vụ các em học sinh của các khối lớp tương ứng đã đăng ký tham gia.
• Dòng cuối cùng ghi lần lượt tổng số học sinh sẽ ngồi lên xe thứ nhất và xe thứ hai.

Ví dụ:

VISIT.INP	VISIT.OUT
4 3 12 0 9 4 10 3 12 8 0 0 7 6	1 0 0 1 1 1 0 0 1 0 0 1 35 36