Bảng B 2022 - Vòng sơ khảo quốc gia

HỘI THI TIN HỌC TRẺ TOÀN QUỐC
Năm 2022

ĐỀ THI BẢNG B – TRUNG HỌC CƠ SỞ - VÒNG THI SƠ KHẢO (QUỐC GIA)
Thời gian làm bài: 1 giờ mỗi bài

Bài 1. Dãy cấp số nhân (100 điểm)

Cho dãy gồm n số nguyên dương a₁, a₂, …, aₙ.

Dãy số b₁, b₂, …, b_k được gọi là dãy cấp số nhân công bội q khi và chỉ khi b_(i+1) = b_i × q với mọi 1 ≤ i < k.

Yêu cầu: Cho số nguyên q, với mỗi k (1 < k ≤ n), hãy đếm số dãy con (không nhất thiết liên tiếp) độ dài k của dãy a₁, a₂, …, aₙ là dãy cấp số nhân công bội q.

Input: Dữ liệu vào từ thiết bị vào chuẩn có khuôn dạng:

Dòng đầu tiên gồm hai số nguyên n, q (1 ≤ n ≤ 10⁵; 2 ≤ q ≤ 10⁹).
Dòng thứ hai chứa n số nguyên a₁, a₂, …, aₙ (1 ≤ aᵢ ≤ 10⁹).

Output: Ghi ra một dòng gồm n − 1 số nguyên, số thứ s (1 ≤ s < n) là số dãy con độ dài (s + 1) là dãy cấp số nhân công bội q, chia dư cho (10⁹ + 7).

Ràng buộc:

Có 25% số test ứng với 25% số điểm của bài thỏa mãn: n ≤ 20;
25% số test khác ứng với 25% số điểm của bài thỏa mãn: n ≤ 100;
25% số test khác ứng với 25% số điểm của bài thỏa mãn: n ≤ 1000;
25% số test còn lại ứng với 25% số điểm của bài không có ràng buộc gì thêm.

Ví dụ:

Input	Output
`5 2` `1 2 8 4 2`	`3 1 0 0`

Bài 2. Bảng kí tự (100 điểm)

Cho bảng chữ kích thước m×n, mỗi ô chứa một kí tự ‘A’ hoặc ‘B’. Một hình chữ nhật con của bảng được gọi là bảng đẹp bậc k nếu số lượng kí tự ‘A’ và số lượng kí tự ‘B’ trong bảng con chênh lệch không quá k.

Yêu cầu: Cho bảng chữ kích thước m×n và số nguyên k, hãy tìm bảng con là bảng đẹp lớn nhất.

Dữ liệu: Vào từ thiết bị vào chuẩn có khuôn dạng:

Dòng đầu chứa số nguyên T (T ≤ 5) là số bộ dữ liệu;
T nhóm dòng sau, mỗi dòng mô tả một bộ dữ liệu có dạng:
- Dòng đầu chứa ba số nguyên m, n, k;
- m dòng tiếp theo, mỗi dòng chứa một xâu kí tự độ dài n chỉ gồm kí tự A hoặc B.

Kết quả: Ghi ra thiết bị ra chuẩn T dòng, mỗi dòng chứa một số là số lượng ô trong bảng tìm được tương ứng với dữ liệu vào.

Ràng buộc:

Có 25% số test ứng với 25% số điểm của bài có m×n ≤ 100;
Có 25% số test khác ứng với 25% số điểm của bài có m×n ≤ 2000;
Có 25% số test khác ứng với 25% số điểm của bài có m×n ≤ 40000; k=0;
Có 25% số test còn lại ứng với 25% số điểm của bài có m×n ≤ 60000.

Ví dụ:

Dữ liệu vào	Kết quả ra
`2` `3 4 0` `AAAA` `BBBB` `BAAA` `3 4 1` `AAAA` `BBBB` `BAAA`	`8` `9`

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