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

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

ĐỀ THI VÒNG SƠ KHẢO QUỐC GIA — BẢNG B - THCS
Phần thi Thực hành

Bài 1: Tam giác (100 điểm)

Cho n điểm trên mặt phẳng, không có ba điểm nào thẳng hàng, các điểm được đánh số từ 1 đến n. Người ta nối tất cả các cặp điểm (i,j) bằng sợi dây màu xanh hoặc màu vàng theo nguyên tắc: Nếu i+j là số nguyên tố thì hai điểm i nối với điểm j bằng sợi dây màu xanh, ngược lại nếu i+j không phải là số nguyên tố thì nối bằng sợi dây màu vàng. Sau đó người ta muốn khảo sát xem có bao nhiêu hình tam giác mà ba đỉnh là ba điểm trong n điểm được nối với nhau bằng các sợi dây cùng màu.

Yêu cầu: Cho n, hãy đếm số hình tam giác mà ba đỉnh là ba điểm trong n điểm được nối với nhau bằng các sợi dây cùng màu.

Input

Dòng đầu tiên ghi số nguyên dương T (T ≤ 10) là số lượng bộ dữ liệu. Tiếp đến là T dòng, mỗi dòng tương ứng với một bộ dữ liệu chứa một số nguyên n.

Output

Gồm T dòng, mỗi dòng chứa một số nguyên là số tam giác đếm được tương ứng với bộ dữ liệu vào.

Input	Output
2 3 5	0 1

Ràng buộc:

Subtask 1 (30%): n ≤ 100;
Subtask 2 (30%): n ≤ 1000;
Subtask 3 (40%): n ≤ 10⁶.

Bài 2: Dãy số (100 điểm)

Cho dãy gồm n số nguyên a_1, a_2, …, a_n và hai số nguyên dương 1 ≤ L ≤ R ≤ n. Hãy tìm một dãy con gồm các phần tử liên tiếp có độ dài s (L ≤ s ≤ R) có tổng các phần tử là lớn nhất.

Input

Dòng đầu tiên gồm ba số nguyên n, L, R (1 ≤ n ≤ 10⁵).
Dòng thứ hai chứa n số nguyên a_1, a_2, …, a_n (|a_i| ≤ 10⁹).

Output

Gồm một dòng chứa một số là tổng các phần tử lớn nhất của dãy con tìm được thoả mãn.

Input	Output
5 2 3 1 3 -1 5 -1	7

Ràng buộc:

Subtask 1 (30%): n ≤ 100;
Subtask 2 (30%): n ≤ 5000;
Subtask 3 (40%): Không có ràng buộc nào thêm.

Bài 3: Hàng cây (100 điểm)

Trên con đường dẫn vào thành phố du lịch nổi tiếng, có một hàng cây được trồng ven đường gồm n cây có chiều cao đánh số lần lượt từ 1 đến n theo chiều từ đầu đến cuối con đường, trong đó chiều cao cây thứ i là h_i. Để thu hút khách du lịch, chính quyền thành phố muốn cắt tỉa hàng cây sao cho hấp dẫn khách du lịch nhất. Chính quyền đưa ra các phương án cắt tỉa như sau: với mỗi phương án đưa ra hai số L, R, khi đó các cây có chiều cao nằm ngoài khoảng [L,R] sẽ bị loại bỏ và đánh giá phương án đó có khả thi hay không cần tính tổng chênh lệch chiều cao của các cây liên tiếp được giữ lại.

Yêu cầu: Cho biết chiều cao của n cây và q phương án, hãy lập trình đưa ra tổng chênh lệch chiều cao giữa hai cây liên tiếp còn giữ lại trong mỗi phương án.

Input

Dòng đầu chứa hai số nguyên n, q (1 ≤ n, q ≤ 2×10⁵).
Dòng thứ hai n số nguyên h_i (1 ≤ h_i ≤ 10⁹).
Tiếp theo là q dòng, dòng thứ j chứa hai số nguyên L_j, R_j (1 ≤ L_j ≤ R_j ≤ 10⁹) mô tả một phương án.

Output: Với mỗi phương án, đưa ra kết quả trên một dòng là tổng chênh lệch chiều cao giữa hai cây liên tiếp còn được giữ lại trong mỗi phương án.

Input	Output
5 5 3 1 5 2 4 2 5 1 4 1 3 3 5 4 5	7 5 3 3 1

Ràng buộc:

Subtask 1 (20%): n, q ≤ 5000;
Subtask 2 (20%): h_i ≤ 400;
Subtask 3 (20%): L_j ≤ L_(j+1), R_j ≤ R_(j+1);
Subtask 4 (20%): n, q ≤ 7×10⁴;
Subtask 5 (20%): Không có ràng buộc gì thêm.

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