SuperCoders là đội tuyển huyền thoại của trường XYZ đã nhiều lần vô địch cuộc thi lập trình viên vũ trụ ACM Universe Final. Theo thể thức cuộc thi, mỗi đội tham dự chỉ có đúng 3 thành viên và được giao...

Ta có thể giải quyết bài toán này bằng cách sử dụng kỹ thuật "meet in the middle". Ý tưởng của kỹ thuật này là chia bài toán thành hai phần nhỏ hơn, giải quyết từng phần và kết hợp kết quả ở hai phần để tìm ra kết quả cuối cùng. Trong trường hợp này, ta có thể chia danh sách các bài thành hai phần bằng cách chọn 𝑛 bài đầu tiên cho Tí và 𝑛 bài cuối cùng cho Tèo. Ta có thể tính tổng thời gian lập trình của Tí và Tèo cho mỗi phần này và lưu trữ kết quả vào hai danh sách riêng biệt. Sau đó, ta sắp xếp danh sách thời gian lập trình của Tèo theo thứ tự tăng dần và duyệt qua từng phần tử trong danh sách thời gian lập trình của Tí. Với mỗi phần tử 𝑎𝑖 trong danh sách thời gian lập trình của Tí, ta tìm kiếm phần tử 𝑏𝑗 trong danh sách thời gian lập trình của Tèo sao cho tổng 𝑎𝑖 + 𝑏𝑗 là nhỏ nhất. Khi tìm được cặp phù hợp, ta cập nhật kết quả tìm được nếu tổng thời gian lập trình của cặp này là nhỏ hơn kết quả hiện tại. Độ phức tạp của thuật toán này là O(2^(2n) log(2n)) do ta cần duyệt qua tất cả các cặp bài và sắp xếp danh sách thời gian lập trình của Tèo. Tuy nhiên, với giá trị n nhỏ (n ≤ 4), thuật toán này vẫn có thể chạy nhanh chóng. Dưới đây là code Python của thuật toán này: n = int(input()) a = [] b = [] for i in range(2*n): ai, bi = map(int, input().split()) if i < n: a.append(ai) else: b.append(bi) # Tính tổng thời gian lập trình của Tí cho tất cả các phân hoạch sum_a = [0] for ai in a: sum_a += [x + ai for x in sum_a] # Tính tổng thời gian lập trình của Tèo cho tất cả các phân hoạch sum_b = [0] for bi in b: sum_b += [x + bi for x in sum_b] # Sắp xếp danh sách thời gian lập trình của Tèo sum_b.sort() # Duyệt qua từng phần tử trong danh sách thời gian lập trình của Tí # và tìm kiếm phần tử phù hợp trong danh sách thời gian lập trình của Tèo ans = float('inf') for i in range(len(sum_a)): j = bisect_left(sum_b, sum_a[i] + sum_b[0]) if j < len(sum_b): ans = min(ans, sum_a[i] + sum_b[j]) print(ans)