HSG lớp 9 2020-2021 (ngày thi 23/03/2021, chưa rõ tỉnh)

(bản chụp không thấy tên đơn vị ra đề)
ĐỀ CHÍNH THỨC

MÔN THI: TIN HỌC - LỚP 9 Năm học 2020 - 2021
Thời gian làm bài thi: 150 phút
Ngày thi: 23/03/2021
(Đề thi có 02 trang)

Bài 1. Bài toán cổ (8 điểm)

Tên file chương trình: MATHS.PAS

Chắc hẳn các bạn học sinh chúng ta ai cũng biết bài toán cổ về bàn cờ vua và hạt thóc. Và hôm nay các bạn sẽ được làm quen với một biến thể của nó: Cho một dãy ô vuông được đánh thứ tự từ trái qua phải là những số nguyên dương liên tiếp từ a tới b. Ô vuông đầu tiên có 2ᵃ hạt thóc, các ô vuông tiếp theo mỗi ô vuông có số hạt thóc gấp đôi ô vuông đứng liền kề trước nó.

Yêu cầu: Tính xem tổng số hạt thóc trong các ô vuông chia cho 127 sẽ dư bao nhiêu trong thời gian nhanh nhất có thể.

Dữ liệu vào: đọc từ file MATHS.INP gồm:

Dòng thứ nhất là số nguyên dương a (a ≤ 10¹⁸)
Dòng thứ hai là số nguyên dương b (b ≤ 10¹⁸)

Kết quả: ghi ra file MATHS.OUT một số nguyên là kết quả cần tìm.

Ví dụ:

MATHS.INP	MATHS.OUT
`1` `9`	`6`

Bài 2. Hình vuông (7 điểm)

Tên file chương trình: SQUARE.PAS

Nam vừa được tặng một bộ đồ chơi có n thanh gỗ, các thanh gỗ có độ dài là aᵢ (với i = 1, 2, …, n). Vốn yêu thích hình học nên Nam thường chọn các thanh gỗ bằng nhau để ghép thành các hình vuông. Nam tự hỏi mình có thể tạo được hình vuông có diện tích lớn nhất là bao nhiêu từ các thanh gỗ đang có. Để tăng độ khó, cậu ấy còn muốn biết thêm liệu có thể có bao nhiêu hình vuông như vậy?

Yêu cầu: Hãy giúp Nam thực hiện tính toán của cậu ấy.

Dữ liệu: Đọc vào từ file SQUARE.INP

Dòng đầu tiên chứa số nguyên dương n (n ≤ 10⁵) - số lượng thanh gỗ.
Trong n dòng tiếp theo sau, dòng thứ i chứa số nguyên dương aᵢ (aᵢ ≤ 10³) - độ dài của các thanh gỗ tương ứng.

Kết quả: Ghi ra file SQUARE.OUT một dòng duy nhất ghi 2 số nguyên lần lượt là diện tích lớn nhất của hình vuông và số lượng hình vuông tạo được (2 số cách nhau bởi 1 khoảng trắng). Nếu không có hình vuông nào tạo thành thì ghi ra −1.

Ví dụ:

SQUARE.INP	SQUARE.OUT
`7` `5` `3` `2` `3` `6` `3` `3`	`9 1`

Bài 3. Đếm số dãy con (5 điểm)

Tên file chương trình: SUMARR.PAS

Cho một dãy n số nguyên A = (a₁, a₂, …, aₙ). Ta định nghĩa dãy con của một dãy A cho trước là một dãy thu được bằng cách xóa đi một số phần tử của dãy A, các phần tử còn lại vẫn giữ đúng thứ tự.

Ví dụ: Cho dãy A = (8 6 5 2 7 4 9) với N = 7, dãy (6 5 4 9) là 1 dãy con của A.

Yêu cầu: Hãy cho biết có bao nhiêu dãy con của dãy thỏa mãn các phần tử có giá trị chẵn, lẻ hoặc lẻ, chẵn xen kẽ nhau?

Dữ liệu đọc vào từ file SUMARR.INP gồm:

Dòng đầu là giá trị của số nguyên dương n (n ≤ 20).
Dòng thứ 2 chứa n số nguyên aᵢ, mỗi số cách nhau một khoảng trắng (i = 1, 2, …, n; |aᵢ| < 10⁶).

Kết quả ghi ra file SUMARR.OUT một số nguyên duy nhất là số lượng dãy con thỏa mãn yêu cầu.

Ví dụ:

SUMARR.INP	SUMARR.OUT
`4` `2 -3 9 4`	`6`

Theo ví dụ trên dãy số 2 −3 9 4 → Có 6 dãy con thỏa mãn yêu cầu: 2 −3; 2 9; −3 4; 9 4; 2 −3 4; 2 9 4.

Th.S Trần Huy Phúc

Kỹ sư phần mềm @Adnovum & Bumbii Academy

Học Tiếng Anh với Bumbii English