HSG lớp 9 Đắk Nông 2021-2022

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

MÔN TIN HỌC 4 bài: CHUSO, BERTRAN, CAPSO, COINS

---

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. Chữ số tận cùng

Chữ số tận cùng của một số nguyên dương là phần dư tìm được sau khi lấy số nguyên dương đó chia cho 10. Giả sử số nguyên dương 357 thì chữ số tận cùng của số nguyên dương 357 là chữ số 7. Cho số nguyên dương n.

Yêu cầu: Em hãy lập trình tìm chữ số tận cùng của số n.

Dữ liệu vào: Cho trong tệp tin văn bản CHUSO.INP gồm một dòng chứa số nguyên dương n (1 ≤ n ≤ 10⁶).

Kết quả ra: Ghi ra tệp tin văn bản CHUSO.OUT gồm một số nguyên duy nhất là chữ số tận cùng tìm được.

Ví dụ:

CHUSO.INP	CHUSO.OUT
357	7

Bài 2. Số nguyên tố

Theo định đề Bertran thì với mọi số nguyên p ≥ 2 bao giờ cũng tìm thấy số nguyên tố n thỏa mãn p < n < 2p. Định đề này do nhà toán học Pháp Joseph Bertran đưa ra năm 1845 sau khi đã kiểm tra với mọi p ≤ 10⁶. Điều này đã được Tchebusep chứng minh năm 1850. Năm 1932 Erdoeus đã tìm được cách chứng minh mới đơn giản hơn.

Nay bạn đang là học sinh Trung học cơ sở, bạn được giao một nhiệm vụ rộng hơn một chút: với p cho trước, hãy liệt kê các số nguyên tố n và xác định số lượng số nguyên tố n thỏa mãn điều kiện p < n < 2p.

Yêu cầu: Em hãy lập trình tìm các số nguyên tố và xác định số lượng số nguyên tố n thỏa mãn điều kiện p < n < 2p.

Dữ liệu vào: Cho trong tệp tin văn bản BERTRAN.INP gồm một dòng chứa số nguyên dương p (1 ≤ p ≤ 10⁶).

Kết quả ra: Ghi ra tệp tin văn bản BERTRAN.OUT gồm:

• Dòng đầu chứa các số nguyên tố n. Các số trên một dòng được viết cách nhau ít nhất một dấu cách.
• Dòng tiếp theo chứa số lượng số nguyên tố n.

Ví dụ 1:

BERTRAN.INP	BERTRAN.OUT
2	3 1

Ví dụ 2:

BERTRAN.INP	BERTRAN.OUT
4	5 7 2

Bài 3. Cặp số hoàn hảo

Hai số nguyên được gọi là một “Cặp số hoàn hảo” nếu như tổng của chúng bằng giá trị s cho trước.

Hai bạn học sinh lúc ngồi nhàn rỗi nghĩ ra trò chơi sau đây để tăng khả năng tư duy toán học, cho dãy số a₁, a₂, …, aₙ, các bạn chọn trong dãy số gồm n số nguyên sao cho giá trị của hai số đã chọn aᵢ, aⱼ với i < j thỏa mãn aᵢ + aⱼ = s là cặp số hoàn hảo.

Cho một dãy số nguyên a₁, a₂, …, aₙ và số nguyên s.

Yêu cầu: Em hãy lập trình đếm xem trong dãy số đã cho có bao nhiêu cặp số hoàn hảo.

Dữ liệu vào: Cho trong tệp tin văn bản CAPSO.INP gồm:

• Dòng thứ nhất ghi số nguyên dương n (n ≤ 10⁵) và số nguyên s (|s| ≤ 10⁹).
• Các dòng tiếp theo lần lượt ghi các số a₁, a₂, …, aₙ (|aᵢ| ≤ 10⁹).

Kết quả ra: Ghi ra tệp tin văn bản CAPSO.OUT gồm một số nguyên duy nhất là số lượng cặp số hoàn hảo.

Ví dụ:

CAPSO.INP	CAPSO.OUT
10 7 5 2 5 3 4 3 1 6 4 0	7

Bài 4. Các đồng xu

Vào một ngày chủ nhật buồn, Nam ngồi học bài và nhâm nhi tách cà phê bên cửa sổ anh ta quan sát các hoạt động hàng ngày của lũ quạ thường bay về làm tổ trong vườn nhà mình. Chúng là loài chim thông minh, rất thích các vật lóng lánh và hay tha những thứ này về tổ. Hôm nay, không biết chúng kiếm được ở đâu, chúng tha về các đồng xu.

Theo sự quan sát của Nam thì lúc này có tất cả n con quạ. Con quạ thứ i đã mang về aᵢ đồng xu. Nhìn vào vị trí của tổ trên cành Nam hiểu rằng nếu có bᵢ đồng xu thì tổ của quạ thứ i sẽ bị lật rơi xuống đất và Nam sẽ nhặt được hết các đồng xu trong tổ. Nam đang có trong túi m đồng xu và anh ta có tài lẻ ném đâu trúng đó. Bây giờ chính là lúc cái tài lẻ này của anh phát huy tác dụng.

Yêu cầu: Em hãy lập trình xác định số tiền tối đa mà Nam sẽ có được.

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

• Dòng thứ nhất chứa hai số nguyên dương n, m (1 ≤ n, m ≤ 10⁵);
• Dòng thứ hai chứa n số a₁, a₂, …, aₙ (0 ≤ aᵢ ≤ 10⁵);
• Dòng thứ ba chứa n số b₁, b₂, …, bₙ (aᵢ < bᵢ ≤ 10⁵).

Kết quả ra: Ghi ra tập tin văn bản COINS.OUT gồm số tiền tối đa mà Nam sẽ có.

Ví dụ:

COINS.INP	COINS.OUT
2 3 1 2 4 6	6