Đề test ngày 25 - 05 - 2026
Đề 57 - Bài 1: Tầm nhìn vượt trội (Mã bài: LEFTMAX)
Nộp bàiPoint: 5
Trong một buổi diễu hành, có N người xếp thành một hàng dọc, người thứ i có chiều cao là H_i. Người đứng ở vị trí i được gọi là có "tầm nhìn vượt trội" nếu chiều cao của họ lớn hơn TẤT CẢ những người đứng trước họ (từ vị trí 1 đến i-1). Người đầu tiên luôn có tầm nhìn vượt trội. Hãy đếm số lượng người có tầm nhìn vượt trội trong hàng.
Input:
Dòng 1: N (1 <= N <= 10^5).
Dòng 2: N số nguyên Hi (1 <= Hi <= 10^9).
Output: Số lượng người thỏa mãn.
Ví dụ:
Input:
6
3 1 4 2 5 5
Output:
3
(Giải thích: Người thứ 1 (cao 3), người thứ 3 (cao 4), người thứ 5 (cao 5). Người thứ 6 cao 5 nhưng không LỚN HƠN người thứ 5 nên không được tính).
Đề 57 - Bài 2: Đồng bộ thiết bị (Mã bài: EQUALIZE)
Nộp bàiPoint: 5
Phòng máy có N chiếc máy tính, máy thứ i đang chạy ở xung nhịp A_i. Để thiết lập mạng máy tính song song, bạn cần đưa xung nhịp của tất cả N máy về CÙNG MỘT mức. Mỗi thao tác, bạn được phép chọn 1 máy tính và tăng hoặc giảm xung nhịp của nó đi 1 đơn vị. Hãy tính số thao tác ít nhất để đồng bộ toàn bộ N máy tính.
Input:
Dòng 1: N (1 <= N <= 10^5).
Dòng 2: N số nguyên Ai (1 <= Ai <= 10^9).
Output: Số thao tác ít nhất.
Ví dụ:
Input:
3
1 2 9
Output:
8
(Giải thích: Đồng bộ tất cả về mức 2. Máy 1 tăng 1, máy 2 không đổi, máy 3 giảm 7. Tổng số thao tác = 1 + 0 + 7 = 8).
Đề 57 - Bài 3: Chèn thêm cột sóng (Mã bài: INSERTK)
Nộp bàiPoint: 5
Trên đường thẳng có N cột sóng, cột thứ i đặt tại tọa độ X_i (đã được sắp xếp tăng dần). Vùng phủ sóng bị gián đoạn nếu khoảng cách giữa 2 cột liền kề quá xa. Bạn được cấp thêm K cột sóng mới và có thể chèn chúng vào bất kỳ tọa độ nào (kể cả số thập phân, nhưng tọa độ chèn phải hợp lệ để lấp khoảng trống). Hãy tìm cách chèn K cột sóng này sao cho "khoảng cách lớn nhất giữa 2 cột sóng liền kề bất kỳ" là nhỏ nhất có thể.
Input:
Dòng 1: N, K (2 <= N <= 10^5, 1 <= K <= 10^9).
Dòng 2: N số nguyên Xi (0 <= Xi <= 10^9).
Output: Khoảng cách lớn nhất nhỏ nhất có thể (in ra phần nguyên làm tròn lên, ví dụ 2.3 thì in 3, 4.0 in 4).
Ví dụ:
Input:
3 3
1 5 12
Output:
3
(Giải thích: Chênh lệch ban đầu: 5-1=4, 12-5=7. Chèn 1 cột vào giữa 1 và 5 (vd tại 3) -> chênh lệch thành 2. Chèn 2 cột vào giữa 5 và 12 (vd tại 7.33 và 9.66) -> chênh lệch lớn nhất là 2.33. Làm tròn lên là 3).
Đề 56 - Bài 3: Bao phủ tuyến đường (Mã bài: COVERSEG)
Nộp bàiPoint: 5
Tuyến đường từ thành phố A đến thành phố B được biểu diễn bằng một đoạn thẳng [0, M]. Có N trạm sửa chữa, trạm thứ i có thể hỗ trợ dải đường từ kilomet thứ Li đến kilomet thứ Ri. Bạn cần chọn ra một số lượng ít nhất các trạm sửa chữa sao cho toàn bộ đoạn đường từ 0 đến M đều được hỗ trợ.
Input:
Dòng 1: N, M (1 <= N <= 10^5, 1 <= M <= 10^9).
N dòng tiếp theo: Mỗi dòng 2 số nguyên Li, Ri (0 <= Li <= Ri <= 10^9).
Output: Số lượng trạm ít nhất cần chọn. Nếu không thể bao phủ toàn bộ [0, M], in ra -1.
Ví dụ:
Input:
3 10
0 5
4 8
7 10
Output:
3
(Giải thích: Chọn cả 3 trạm để phủ đoạn [0, 10]).