Bảng B 2023 - Chung kết thành phố Hà Nội

HỘI THI TIN HỌC TRẺ THÀNH PHỐ HÀ NỘI Vòng chung kết – Năm 2023

ĐỀ THI THỰC HÀNH BẢNG B – KHỐI TRUNG HỌC CƠ SỞ Thời gian: 90 phút (không kể thời gian phát đề)

Tổng quan bài thi

STT	Tên bài	Điểm
1	Chia hết	100
2	Đếm cặp	100
3	Số tuần hoàn	100
4	Dãy số đối xứng	100

Bài 1: Chia hết (100 điểm)

Cho hai số nguyên N và K.

Yêu cầu: Tìm số nguyên M nhỏ nhất sao cho N × M chia hết cho 10ᴷ.

Input: Gồm một dòng chứa hai số nguyên N, K (|N| ≤ 10⁹, 0 ≤ K ≤ 18).

Output: In ra một số nguyên duy nhất là kết quả của bài toán.

Chấm điểm:

Subtask 1 (70% số điểm): K ≤ 6.
Subtask 2 (30% số điểm): không có ràng buộc gì thêm.

Ví dụ:

Input	Output
`8 2`	`25`

Bài 2: Đếm cặp (100 điểm)

Cho dãy số nguyên A gồm N phần tử A₁, A₂, …, A_N và một số nguyên K.

Yêu cầu: Đếm số cặp số L, R (1 ≤ L ≤ R ≤ N) sao cho dãy con liên tiếp A_L, A_(L+1), …, A_R có hiệu giữa số lớn nhất và số nhỏ nhất không vượt quá K.

Input:

Dòng đầu tiên gồm hai số nguyên dương N, K (N ≤ 10⁵, K ≤ 10¹⁸).
Dòng thứ hai gồm N số nguyên A₁, A₂, …, A_N (|Aᵢ| ≤ 10⁹).

Output: In ra một số nguyên duy nhất là kết quả của bài toán.

Chấm điểm:

Subtask 1 (50% số điểm): N ≤ 100.
Subtask 2 (20% số điểm): N ≤ 5000.
Subtask 3 (30% số điểm): không có ràng buộc gì thêm.

Ví dụ:

Input	Output
`5 2` `2 -1 3 1 3`	`8`

Bài 3: Số tuần hoàn (100 điểm)

Số T được gọi là số tuần hoàn chu kì I nếu tồn tại một số B có I chữ số và có thể xếp các số B cạnh nhau để thu được số T. Ví dụ:

10101010 là số tuần hoàn chu kì 2 và cũng là số tuần hoàn chu kì 4, 8.
2023 là số tuần hoàn chu kì 4.
154154 là số tuần hoàn chu kì 3 và cũng là số tuần hoàn chu kì 6.

Yêu cầu: Tìm một số tuần hoàn chu kì N bất kì lớn hơn L và nhỏ hơn R.

Input: Gồm một dòng chứa ba số nguyên dương N, L, R (1 ≤ N ≤ 10⁵, 1 ≤ L ≤ R ≤ 10^(10⁷)).

Output: In ra một số nguyên là số tuần hoàn thoả mãn. Nếu không có kết quả thoả mãn, in ra −1.

Chấm điểm:

Subtask 1 (40% số điểm): R ≤ 10⁵.
Subtask 2 (20% số điểm): R − L ≤ 10⁵.
Subtask 3 (20% số điểm): R = 10^(10⁷).
Subtask 4 (20% số điểm): không có ràng buộc gì thêm.

Ví dụ:

Input	Output
`2 1234 9876`	`2222`

Bài 4: Dãy số đối xứng (100 điểm)

Dãy số B gồm M phần tử B₁, B₂, …, B_(M−1), B_M được gọi là dãy số đối xứng độ dài M khi viết dãy số theo thứ tự ngược lại vẫn thu được dãy số B. Ví dụ hai dãy số (3, 2, 3), (4, −1, −1, 4) là dãy số đối xứng độ dài 3 và 4.

Cho dãy số A gồm N phần tử A₁, A₂, …, A_(N−1), A_N và một số nguyên dương K.

Yêu cầu: Tìm cách bỏ đi ít phần tử nhất của dãy số A để thu được dãy số đối xứng có độ dài không vượt quá K.

Input:

Dòng đầu tiên gồm hai số nguyên dương N, K (1 ≤ N ≤ 10⁵, 1 ≤ K ≤ 100).
Dòng thứ hai gồm N số nguyên dương A₁, A₂, …, A_(N−1), A_N (1 ≤ Aᵢ ≤ 10⁵).

Output: In ra một số nguyên là độ dài của dãy số đối xứng thoả mãn đề bài.

Chấm điểm:

Subtask 1 (30% số điểm): N ≤ 20.
Subtask 2 (20% số điểm): N ≤ 10³.
Subtask 3 (20% số điểm): Aᵢ ≤ 10.
Subtask 4 (30% số điểm): không có ràng buộc gì thêm.

Ví dụ:

Input	Output
`5 4` `1 1 2 1 1`	`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