Bảng B 2024 - Tài năng Tin học trẻ (YICT)

TÀI NĂNG TIN HỌC TRẺ (YICT) Năm học 2023-2024

ĐỀ THI BẢNG B – TRUNG HỌC CƠ SỞ

Tổng quan bài thi

Bài	Tên bài	Điểm
1	Tổng các số chẵn	100
2	Đếm kí tự
3	Chọn đoạn	100
4	Dò mìn	100

Bài 1. Tổng các số chẵn (100 điểm)

Cho số nguyên dương k, hãy tìm số nguyên n nhỏ nhất để tổng các số chẵn không vượt quá n sẽ lớn hơn k.

Dữ liệu:

Gồm một dòng chứa số nguyên k (1 ≤ k ≤ 10¹⁸)

Kết quả:

Đưa ra số n nhỏ nhất thoả mãn.

Ví dụ:

input	output
`11`	`6`

Subtask 1 (50 điểm): k ≤ 10⁹
Subtask 2 (50 điểm): k ≤ 10¹⁸

Bài 2. Đếm kí tự

Chuỗi nén có dạng: N = x₁C₁x₂C₂…xₖCₖ là mô tả chuỗi ban đầu S có x₁ kí tự C₁, sau đó x₂ kí tự C₂, …, xₖ kí tự Cₖ (1 ≤ xᵢ ≤ 10⁹; Cᵢ là các kí tự tiếng Anh từ A đến Z). Ví dụ: N = 1A5D2A thì chuỗi ban đầu S = ADDDDDAA.

Yêu cầu: Cho chuỗi nén N và hai số tự nhiên L, R. Hãy đếm xem từ vị trí L đến vị trí R của chuỗi kí tự S, kí tự xuất hiện nhiều nhất bao nhiêu lần? (Vị trí trong chuỗi kí tự S được đánh số từ 1 đến |S|, trong đó |S| là độ dài xâu S)

Dữ liệu:

Dòng đầu tiên chứa chuỗi kí tự N có độ dài không quá 10⁴;
Dòng thứ hai chứa số nguyên dương L;
Dòng thứ hai chứa số nguyên dương R.

Dữ liệu đảm bảo |S| ≤ 10¹²; L ≤ R ≤ |S|.

Kết quả: Ghi ra một số tự nhiên là kết quả của bài toán.

Ví dụ:

Dữ liệu	Kết quả	Giải thích
`1A5D2A` `6` `8`	`2`	Chuỗi kí tự ban đầu S = ADDDDDAA. Chuỗi kí tự từ 6 đến 8 là DAA. Vậy kí tự xuất hiện nhiều nhất là kí tự A, xuất hiện 2 lần.

Chấm điểm:

Có 40% số test tương ứng với 40% số điểm có điều kiện: xᵢ < 10;
30% số test khác tương ứng với 30% số điểm có điều kiện: |S| ≤ 10⁴;
30% số test còn lại tương ứng với 30% số điểm không có điều kiện gì thêm.

Bài 3. Chọn đoạn

Bạn tham gia vào một cuộc thi và đã phải đấu n trận, mỗi trận đấu nếu thắng bạn nhận được 1 điểm, ngược lại nếu thua bạn sẽ mất đi −1 điểm. Tuy nhiên, để đối mặt với sự dò hỏi của huấn luyện viên, bạn quyết định bịa ra rằng chỉ có một vài trận đấu là bạn thật sự nghiêm túc thi đấu.

Cụ thể, bạn sẽ chọn ra không quá k đoạn [l₁, r₁], [l₂, r₂], …, [lₓ, rₓ] (với 0 ≤ x ≤ k) sao cho 1 ≤ l₁ ≤ r₁ < l₂ ≤ r₂ < ⋯ < lₓ ≤ rₓ ≤ n và nói rằng bạn chỉ nghiêm túc trong những trận đấu có chỉ số thuộc một trong các đoạn trên. Mức độ hài lòng của huấn luyện viên phụ thuộc vào số điểm bạn nhận được trong các trận đấu mà bạn coi là nghiêm túc. Hãy tìm cách chọn ra tối đa k đoạn sao cho tổng số điểm của bạn là lớn nhất.

Dữ liệu:

Dòng đầu tiên chứa hai số nguyên n, k (1 ≤ k ≤ n ≤ 2 · 10⁵), tương ứng là số trận đấu và số lượng đoạn tối đa bạn sẽ chọn.
Dòng thứ hai chứa một xâu ký tự gồm n ký tự, ký tự thứ i tương ứng là trạng thái thắng hay thua của bạn ở ván đấu thứ i, là “W” nếu bạn thắng, và “L” nếu bạn thua.

Kết quả:

Ghi kết quả trên một dòng, là tổng số điểm lớn nhất bạn chọn được.

Ví dụ:

input	output
`4 1` `WLWW`	`2`

Subtask 1 (15 điểm): k = 1;
Subtask 2 (15 điểm): k = 2;
Subtask 3 (20 điểm): n ≤ 100;
Subtask 4 (20 điểm): n ≤ 500;
Subtask 5 (10 điểm): n ≤ 2000;
Subtask 6 (10 điểm): n ≤ 10⁴;
Subtask 7 (10 điểm): không có ràng buộc gì thêm.

Bài 4. Dò mìn (100 điểm)

Trên bảng A kích thước m × n, các hàng được đánh số từ 1 đến m (từ trên xuống dưới), các cột được đánh số từ 1 đến n (từ trái qua phải). Ô nằm ở hàng x (1 ≤ x ≤ m) cột y (1 ≤ y ≤ n) là ô (x, y). Trên mỗi ô (x, y) của bảng A có thể có một quả mìn hoặc không có quả mìn nào. Từ bảng A xây dựng bảng B có cùng kích thước m × n, trong đó, ô (x, y) của bảng B cho thông tin về số lượng ô (u, v) của bảng A có chứa mìn với |x − u| + |y − v| ≤ 2.

Yêu cầu: Cho bảng B, hãy tìm một trạng thái mìn của bảng A thỏa mãn.

Dữ liệu:

Dòng đầu chứa hai số nguyên m, n;
m dòng sau, mỗi dòng chứa n số, số nằm trên dòng x cột y là số cho biết thông tin về số lượng ô (u, v) có chứa mìn mà |x − u| + |y − v| ≤ 2.

Kết quả:

Ghi ra trên m dòng, mỗi dòng chứa n số, số thứ y trên dòng x bằng 0 (hoặc 1) cho biết ô (x, y) không có mìn (hoặc có mìn).

input	output
`4 4` `2 3 2 2` `2 3 3 2` `3 3 2 1` `3 2 2 1`	`0 0 1 1` `1 0 0 0` `0 0 0 0` `1 1 0 0`

Subtask 1 (50 điểm): m, n ≤ 4;
Subtask 2 (25 điểm): m, n ≤ 8;
Subtask 3 (25 điểm): m, n ≤ 16.

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