Ba chiếc túi
Đề bài
Mô tả
Bạn có ba chiếc túi. Mỗi túi chứa một tập hợp (đa tập, cho phép lặp) các số nguyên dương.
Bạn được thực hiện một số thao tác. Trong một thao tác, bạn chọn hai chiếc túi khác rỗng bất kì, rồi chọn một số từ mỗi túi đó. Giả sử bạn chọn số ở túi thứ nhất và số ở túi thứ hai. Khi đó bạn xoá khỏi túi thứ hai và thay trong túi thứ nhất bằng . Nếu có nhiều bản sao giống nhau thì mỗi thao tác chỉ tác động lên đúng một bản sao.
Bạn phải thực hiện các thao tác sao cho cuối cùng chỉ còn lại đúng một số nằm trong đúng một túi (hai túi còn lại rỗng). Người ta chứng minh được rằng luôn tồn tại cách để đạt được cấu hình như vậy. Trong tất cả các cách, hãy tìm cách cho ra số còn lại lớn nhất.
Dữ liệu vào
- Dòng đầu chứa ba số nguyên là số lượng phần tử trong ba túi.
- Dòng thứ trong ba dòng tiếp theo chứa số nguyên là các số trong túi thứ .
Dữ liệu ra
In ra một số nguyên duy nhất: giá trị lớn nhất có thể đạt được ở cuối cùng.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 4 1 1 2 6 3 4 5 5 |
20 | Tổng tất cả các số là . Ta có thể để toàn bộ túi thứ nhất mang dấu trừ và mọi số còn lại mang dấu cộng, thu được . |
| 3 2 2 7 5 4 2 9 7 1 |
29 | Tổng là . Chỉ cần trừ đi hai lần phần tử nhỏ nhất của túi hai () và túi ba (): . |
Bình luận