Bảng B 2024 - Tỉnh Nghệ An

HỘI THI TIN HỌC TRẺ TỈNH NGHỆ AN 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
1	Phép tính
2	Trò chơi
3	Xâu bất đối xứng
4	Tiều phu

Bài 1. Phép tính

Cho ba số nguyên a, b, c. Hãy xác định xem có thể xảy ra một trong bốn phương trình sau không, hay không thể xảy ra?

a + b = c.
a − b = c.
a × b = c.
a / b = c.

Dữ liệu

Dòng thứ nhất chứa một số nguyên dương T (1 ≤ T ≤ 10³) - số bộ dữ liệu.
T dòng tiếp theo, mỗi dòng chứa ba số nguyên a, b, c (1 ≤ a, b, c ≤ 10⁹).

Kết quả

Với mỗi bộ dữ liệu, đưa ra một dấu tương ứng với phương trình xảy ra, ưu tiên theo thứ tự phép cộng, trừ, nhân, chia hoặc đưa ra NONE nếu không xảy ra bất cứ trường hợp nào thỏa mãn.

Ví dụ

bàn phím	màn hình
`5` `3 2 5` `3 2 1` `3 2 6` `4 2 2` `4 3 2`	`+` `-` `*` `-` `NONE`

Bài 2. Trò chơi

Bạn chơi một trò chơi có n màn chơi, trong đó màn chơi thứ i có giá trị là aᵢ và điểm nhận được là bᵢ.

Bạn muốn chọn một dãy liên tiếp các màn chơi từ l đến r sao cho với mọi l ≤ i < r, aᵢ luôn chia hết cho aᵢ₊₁. Nếu bạn chọn dãy các màn chơi từ l đến r, số điểm bạn nhận được là bₗ + bₗ₊₁ + … + bᵣ. Tuy nhiên, do giới hạn của trò chơi, số điểm bạn nhận được không được phép vượt quá k (có nghĩa là nếu tổng điểm bạn nhận được bạn vượt quá k thì xem như thua cuộc).

Do muốn tận hưởng trò chơi lâu nhất có thể, bạn muốn tìm dãy liên tiếp gồm nhiều màn chơi nhất. Hỏi trò chơi của bạn có thể diễn ra trong bao nhiêu màn?

Dữ liệu

Dòng thứ nhất chứa hai số nguyên dương n, k (1 ≤ n ≤ 2 × 10⁵, 1 ≤ k ≤ 10⁹).
Dòng thứ hai chứa n số nguyên b₁, b₂, …, bₙ (1 ≤ bᵢ ≤ 10⁵).
Dòng thứ ba chứa n số nguyên a₁, a₂, …, aₙ (1 ≤ aᵢ ≤ 10⁹).

Kết quả

Gồm một dòng chứa một số nguyên duy nhất là dãy dài nhất thỏa mãn, hoặc đưa ra số 0 nếu không có dãy nào thỏa mãn.

Hạn chế

Subtask 1 (25% số điểm): n ≤ 10³.
Subtask 2 (25% số điểm): b₁ + b₂ + … + bₙ ≤ k.
Subtask 3 (25% số điểm): a₁ = a₂ = … = aₙ.
Subtask 4 (25% số điểm): không có ràng buộc gì thêm.

Ví dụ

bàn phím	màn hình
`4 8` `5 4 1 2` `6 2 3 1`	`2`

Bài 3. Xâu bất đối xứng

Bạn đã biết về “xâu đối xứng” rồi đúng không? Vậy hôm nay chúng ta sẽ định nghĩa về “xâu bất đối xứng” nhé.

Bạn được cho một xâu s gồm toàn các chữ cái in thường. Trong một thao tác, bạn được phép hoán đổi vị trí của hai kí tự bất kì của xâu s.

Một xâu s độ dài n được gọi là “xâu bất đối xứng” khi với mọi i (1 ≤ i ≤ n), sᵢ ≠ sₙ₋ᵢ₊₁. Ví dụ, xâu string, dukkichi là “xâu bất đối xứng”, nhưng xâu abacaba, aba, abcbd thì không phải.

Xác định số thao tác nhỏ nhất cần thực hiện để biến xâu s thành một “xâu bất đối xứng”, nếu không làm được đưa ra -1.

Dữ liệu

Dòng thứ nhất chứa một số nguyên dương n (1 ≤ n ≤ 2 × 10⁵) - độ dài xâu s.
Dòng thứ hai chứa xâu s độ dài n chỉ chứa các ký tự latin in thường.

Kết quả

Đưa ra một dòng là một số nguyên duy nhất thỏa mãn điều kiện đề bài, nếu không làm được đưa ra -1.

Hạn chế

Subtask 1 (30% số điểm): n ≤ 10³.
Subtask 2 (30% số điểm): xâu s chỉ gồm hai loại kí tự.
Subtask 3 (40% số điểm): không có ràng buộc gì thêm.

Ví dụ

bàn phím	màn hình
`6` `string`	`0`

Bài 4. Tiều phu

Thuận là một bác tiều phu lừng danh về tài năng chặt cây của mình. Hôm nay Thuận sẽ trồng và chặt một hàng cây gồm n cây để lấy gỗ xây nhà mới cho mình, các cây được đánh số từ 1 đến n từ trái qua phải. Ở vị trí thứ i, Thuận chỉ được phép trồng cây có độ cao không quá hᵢ.

Thuận muốn tìm một loại cây có độ cao là số nguyên k (k ≤ h₁, k ≤ hₙ) và trồng vào một số vị trí thích hợp, biết rằng cậu chắc chắn sẽ trồng cây vào vị trí thứ 1 và thứ n.

Nếu cây ở vị trí thứ i (i < n) bị đổ, nó sẽ làm các cây ở vị trí trong khoảng [i + 1, min(n, i + k)] đổ theo. Hãy giúp Thuận tính xem, độ cao k nhỏ nhất có thể là bao nhiêu, sao cho nếu Thuận chặt đổ cây ở vị trí thứ 1 thì cây ở vị trí thứ n cũng bị đổ theo.

Dữ liệu

Dòng đầu tiên chứa một số nguyên dương n (n ≤ 10⁷).
Dòng thứ hai chứa n số nguyên không âm h₁, h₂, …, hₙ (0 ≤ hᵢ ≤ n).

Dữ liệu bảo đảm tồn tại một đáp án hợp lệ.

Kết quả

In ra một số nguyên dương là kết quả của bài toán.

Hạn chế

Subtask 1 (20% số điểm): n ≤ 100.
Subtask 2 (20% số điểm): n ≤ 1000.
Subtask 3 (20% số điểm): n ≤ 10⁵.
Subtask 4 (20% số điểm): n ≤ 10⁶.
Subtask 5 (20% số điểm): không có ràng buộc gì thêm.

Ví dụ

bàn phím	màn hình
`10` `10 1 2 0 3 4 5 0 2 10`	`2`

Giải thích

Thuận trồng cây độ cao 2 ở các vị trí 1, 3, 5, 7, 9, 10.

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