Đề test ngày 14 - 05 - 2026
Đề 45 - Bài 1: Chia kẹo
Nộp bàiPoint: 5
Cô giáo có N túi kẹo, túi thứ i có A_i viên kẹo. Cô muốn chia N túi kẹo này cho 2 đội học sinh sao cho đội nào cũng nhận được kẹo (không ai bị nhận 0 túi), và mỗi đội phải nhận nguyên cả túi (không được bóc lẻ túi ra). Yêu cầu quan trọng nhất là chênh lệch tổng số viên kẹo giữa hai đội phải là nhỏ nhất có thể. Hãy tính độ chênh lệch nhỏ nhất đó.
Input:
Dòng 1: N (1 <= N <= 20).
Dòng 2: N số nguyên Ai (1 <= Ai <= 10^5).
Output: Chênh lệch nhỏ nhất giữa hai đội.
Ví dụ:
Input:
4
1 5 11 5
Output:
0
(Giải thích: Đội 1 nhận túi 11. Đội 2 nhận túi 1, 5, 5. Tổng mỗi đội là 11, chênh lệch bằng 0).
Đề 45 - Bài 2: Nối dây thừng
Nộp bàiPoint: 5
Bạn có N sợi dây thừng với độ dài khác nhau. Để nối 2 sợi dây thừng thành 1 sợi, bạn sẽ mất một mức năng lượng bằng tổng chiều dài của 2 sợi dây đó. Bạn cần nối tất cả N sợi dây lại thành 1 sợi duy nhất. Hãy tìm cách chọn thứ tự nối dây sao cho tổng mức năng lượng tiêu hao cho toàn bộ các lần nối là nhỏ nhất.
Input:
Dòng 1: N (1 <= N <= 10^5).
Dòng 2: N số nguyên Li là độ dài các sợi dây (1 <= Li <= 10^4).
Output: Tổng mức năng lượng tiêu hao nhỏ nhất.
Ví dụ:
Input:
4
4 3 2 6
Output:
29
(Giải thích: Nối 2+3=5 (năng lượng 5). Các dây còn 4, 5, 6. Nối 4+5=9 (năng lượng 9). Các dây còn 9, 6. Nối 9+6=15 (năng lượng 15). Tổng = 5 + 9 + 15 = 29).
Đề 45 - Bài 3: Giao điểm đoạn thẳng
Nộp bàiPoint: 5
Trên trục tọa độ Ox có N đoạn thẳng. Đoạn thẳng thứ i bắt đầu tại Li và kết thúc tại Ri. Hai đoạn thẳng được coi là có giao điểm nếu chúng có ít nhất một điểm chung (ví dụ đoạn [1, 3] và đoạn [3, 5] giao nhau tại 3). Bạn hãy đếm xem có tất cả bao nhiêu cặp đoạn thẳng có giao điểm với nhau.
Input:
Dòng 1: N (1 <= N <= 10^5).
N dòng tiếp theo: Mỗi dòng 2 số nguyên Li, Ri (1 <= Li <= Ri <= 10^9).
Output: Số lượng cặp đoạn thẳng giao nhau.
Ví dụ:
Input:
3
1 4
2 5
6 8
Output:
1
(Giải thích: Cặp (1, 4) và (2, 5) giao nhau).
Đề 45 - Bài 4: Dãy con xen kẽ
Nộp bàiPoint: 5
Cho dãy số nguyên dương A gồm N phần tử. Một dãy con được gọi là dãy con xen kẽ chuẩn nếu hai phần tử kề nhau bất kỳ trong dãy con đó có tính chẵn lẻ khác nhau, đồng thời dãy con này phải là dãy tăng ngặt (phần tử sau lớn hơn phần tử trước). Hãy tìm độ dài của dãy con xen kẽ chuẩn dài nhất có thể được trích xuất từ dãy A.
Input:
Dòng 1: N (1 <= N <= 10^5).
Dòng 2: N số nguyên Ai (1 <= Ai <= 10^9).
Output: Độ dài lớn nhất của dãy con thỏa mãn.
Ví dụ:
Input:
6
1 2 4 3 6 5
Output:
4
(Giải thích: Dãy con chọn là 1, 4, 5. Nhưng 4 chẵn, 5 lẻ, tăng. Hoặc 1 (lẻ), 2 (chẵn), 3 (lẻ), 6 (chẵn) -> độ dài 4. Đây là dãy tăng ngặt và chẵn lẻ đan xen).