Bảng B 2024 - Tỉnh Hà Tĩnh

HỘI THI TIN HỌC TRẺ TỈNH HÀ TĨNH Lần thứ XXVII - Năm 2024
ĐỀ CHÍNH THỨC (Đề thi có 02 trang, gồm 04 bài)

ĐỀ THI BẢNG B - KHỐI THCS Thời gian làm bài: 120 phút
Ngày thi: 19/05/2024

Tổng quan đề thi

Bài	Tên bài	Tệp chương trình	Tệp dữ liệu vào	Tệp kết quả
Bài 1	Chuyển đổi số	DIGITAL.*	DIGITAL.INP	DIGITAL.OUT
Bài 2	Dãy con cân bằng	BALANSEQ.*	BALANSEQ.INP	BALANSEQ.OUT
Bài 3	TEAMCHT	TEAMCHT.*	TEAMCHT.INP	TEAMCHT.OUT
Bài 4	Tích lớn nhất	PRODUCT.*	PRODUCT.INP	PRODUCT.OUT

Dấu * được thay thế bởi pas, cpp hoặc py của ngôn ngữ lập trình được sử dụng tương ứng là Pascal, C++ hoặc Python.

Hãy lập chương trình giải các bài toán sau đây:

Bài 1. Chuyển đổi số (6 điểm)

Chuyển đổi số và việc chuyển đổi giữa các hệ số là một phần quan trọng của cuộc cách mạng số hiện đại. Một trong những quá trình quan trọng nhất là chuyển đổi từ hệ thập phân sang hệ nhị phân. Hệ thập phân, cơ số 10, là cơ số mà chúng ta thường sử dụng trong cuộc sống hàng ngày. Nhưng trong thế giới của máy tính và công nghệ, hệ nhị phân (hệ cơ số 2) là ngôn ngữ mà các máy tính hiểu và sử dụng để thực hiện các phép toán và xử lý dữ liệu.

Hệ nhị phân chỉ dùng hai kí hiệu 0 và 1 để biểu diễn và xác định giá trị các số. Nguyên tắc chuyển đổi một số từ hệ cơ số 10 sang hệ cơ số 2 được thực hiện như sau: Cứ chia số đó cho 2 lấy phần dư, rồi tiếp tục chia phần nguyên cho 2 đến khi phần nguyên bằng 0 thì dừng lại. Kết quả chuyển đổi chính là số dư tìm được viết theo thứ tự ngược từ dưới lên.

Ví dụ: Xét số 9 ở hệ thập phân

9 chia 2 = 4 dư 1; 4 chia 2 = 2 dư 0; 2 chia 2 = 1 dư 0; 1 chia 2 = 0 dư 1

Kết quả bài toán: x = 9 ở hệ thập phân = 1001 ở hệ nhị phân.

Yêu cầu: Cho số nguyên dương n ≤ 10⁹. Thực hiện chuyển đổi số n sang hệ nhị phân.

Dữ liệu: Vào từ tệp văn bản DIGITAL.INP gồm một số nguyên dương n.

Kết quả: Ghi ra tệp văn bản DIGITAL.OUT kết quả bài toán.

Ví dụ:

DIGITAL.INP	DIGITAL.OUT
`9`	`1001`

Bài 2. Dãy con cân bằng (6 điểm)

Cho một dãy số A gồm n số nguyên a₁, a₂, …, aₙ, mỗi số có giá trị tuyệt đối không quá 10⁹.

Yêu cầu: Tìm dãy con dài nhất có số lượng số âm bằng số lượng số dương.

Dữ liệu: Vào từ tệp văn bản BALANSEQ.INP có cấu trúc:

Dòng đầu tiên ghi một số nguyên n (2 ≤ n ≤ 10⁶) là số phần tử trong dãy;
Dòng thứ hai ghi n số nguyên a₁, a₂, …, aₙ (|aᵢ| ≤ 10⁹, 1 ≤ i ≤ n);

Các số trên cùng dòng ghi cách nhau ít nhất một dấu cách.

Kết quả: Ghi ra file văn bản BALANSEQ.OUT một số nguyên duy nhất là độ dài dãy con tìm được.

Ràng buộc:

Có 40% số test ứng với 40% số điểm của bài có n ≤ 10³;
60% số test còn lại ứng với 60% số điểm không có ràng buộc gì thêm.

Ví dụ:

BALANSEQ.INP	BALANSEQ.OUT
`6` `1 -3 -2 1 3 1`	`4`

Bài 3. TEAMCHT (6 điểm)

Sau khi dành cú đúp giải nhất học sinh giỏi quốc gia môn tin học hai năm liên tiếp với tiền khoáng hậu, mang về thành tích vẻ vang cho Hà Tĩnh, Mạnh Hùng muốn truyền cảm hứng cho các em nhỏ đam mê tin học bằng câu đố như sau: cho dãy A gồm n số nguyên a₁, a₂, …, aₙ và số nguyên k.

Hãy đếm xem có bao nhiêu cách chọn các số liên tiếp aᵢ, aᵢ₊₁, …, aⱼ (1 ≤ i ≤ j ≤ n) để có tổng đúng bằng k. Phần thưởng cho những bạn giải đúng là được anh kết nạp vào câu lạc bộ Tin học CHT do anh sáng lập.

Dữ liệu: Vào từ tệp văn bản TEAMCHT.INP có cấu trúc:

Dòng đầu là hai số nguyên n, k (0 < n ≤ 10⁶, k ≤ 10¹⁴);
Dòng thứ 2 gồm n số nguyên a₁, a₂, …, aₙ (0 < aᵢ ≤ 10⁹, ∀i = 1, 2, …, n).

Các số trên cùng một dòng ghi cách nhau bởi dấu cách.

Kết quả: Ghi ra tệp văn bản TEAMCHT.OUT một số nguyên duy nhất là số cách chọn theo yêu cầu trên.

Ràng buộc:

Có 60% số test ứng với 60% số điểm thỏa mãn: 0 < aᵢ ≤ 10⁹; n ≤ 10³;
Có 20% số test ứng với 20% số điểm thỏa mãn: 0 < aᵢ ≤ 10⁹; n ≤ 10⁶;
Có 20% số test còn lại ứng với 20% số điểm không có ràng buộc gì thêm.

Ví dụ:

TEAMCHT.INP	TEAMCHT.OUT	Giải thích
`5 8` `1 1 3 5 8`	`2`	Có 2 cách chọn các số liên tiếp có tổng bằng 8 đó là: 3, 5 và 8

Bài 4. Tích lớn nhất (2 điểm)

Cho hai dãy số nguyên dương A, B. Dãy số A gồm n số nguyên dương a₁, a₂, …, aₙ và dãy B gồm n số nguyên dương b₁, b₂, …, bₙ.

Yêu cầu: Tìm cặp chỉ số (i, j) mà (1 ≤ i, j ≤ n, i ≠ j) sao cho tích nhỏ nhất của aᵢ · aⱼ và bᵢ · bⱼ hay min(aᵢ · aⱼ, bᵢ · bⱼ) có giá trị lớn nhất, in ra giá trị đó.

Dữ liệu: Vào từ tệp văn bản PRODUCT.INP có cấu trúc:

Dòng đầu tiên ghi một số nguyên n (2 ≤ n ≤ 10⁵) là số phần tử trong dãy;
Dòng thứ hai ghi n số nguyên dương a₁, a₂, …, aₙ (aᵢ ≤ 10⁹, 1 ≤ i ≤ n);
Dòng thứ ba ghi n số nguyên dương b₁, b₂, …, bₙ (bᵢ ≤ 10⁹, 1 ≤ i ≤ n).

Các số trên cùng dòng ghi cách nhau ít nhất một dấu cách.

Kết quả: Ghi ra tệp văn bản PRODUCT.OUT một số nguyên duy nhất là kết quả bài toán.

Ràng buộc:

Có 40% số test ứng với 40% số điểm của bài có n ≤ 10³;
Có 60% số test còn lại ứng với 60% số điểm không có ràng buộc gì thêm.

Ví dụ:

PRODUCT.INP	PRODUCT.OUT
`4` `9 7 1 4` `1 4 6 5`	`20`

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