JOI 2025 - Softcream
Xem PDFAlice và Bob đến cửa hàng kem tươi JOICE. Tại đây, khách hàng đặt một cây kem bằng cách chọn đúng một hương vị, một loại ốc quế và một loại đồ phủ.
- Có \(X\) hương vị, với giá lần lượt là \(A_1, A_2, \ldots, A_X\).
- Có \(Y\) loại ốc quế, với giá lần lượt là \(B_1, B_2, \ldots, B_Y\).
- Có \(Z\) loại đồ phủ, với giá lần lượt là \(C_1, C_2, \ldots, C_Z\).
Giá của cây kem là tổng giá của hương vị, ốc quế và đồ phủ đã chọn. Với số nguyên \(P\) cho trước, điểm số của cây kem là giá trị tuyệt đối của hiệu giữa giá cây kem và \(P\).
Alice và Bob định cùng đặt một cây kem, nhưng mong muốn của hai người hoàn toàn trái ngược nhau: Alice muốn điểm số lớn nhất có thể, còn Bob muốn điểm số nhỏ nhất có thể. Vì vậy, họ quyết định chọn hương vị, ốc quế và đồ phủ theo thứ tự sau:
- Đầu tiên, Alice chọn hương vị.
- Tiếp theo, Bob chọn loại ốc quế.
- Cuối cùng, Alice chọn loại đồ phủ.
Cho thông tin về các hương vị, loại ốc quế, loại đồ phủ và số nguyên \(P\), hãy tìm điểm số của cây kem được đặt cuối cùng nếu cả hai người đều lựa chọn tối ưu ở mỗi lượt.
Dữ liệu vào
Dữ liệu vào có dạng:
X Y Z P
A_1 A_2 ... A_X
B_1 B_2 ... B_Y
C_1 C_2 ... C_Z
Dữ liệu ra
In trên một dòng điểm số của cây kem được đặt cuối cùng.
Ràng buộc
- \(1 \le X \le 200\,000\).
- \(1 \le Y \le 200\,000\).
- \(1 \le Z \le 200\,000\).
- \(0 \le P \le 3 \times 10^8\).
- \(0 \le A_i \le 10^8\) (\(1 \le i \le X\)).
- \(0 \le B_j \le 10^8\) (\(1 \le j \le Y\)).
- \(0 \le C_k \le 10^8\) (\(1 \le k \le Z\)).
- Tất cả các giá trị trong dữ liệu vào đều là số nguyên.
Chấm điểm
- \(7\) điểm: \(X = 1\), \(Y = 1\), \(Z \le 100\).
- \(17\) điểm: \(X = 1\), \(Y \le 100\), \(Z \le 100\).
- \(21\) điểm: \(X \le 100\), \(Y \le 100\), \(Z \le 100\).
- \(22\) điểm: \(X \le 4000\), \(Y \le 4000\), \(Z \le 4000\).
- \(33\) điểm: Không có ràng buộc bổ sung.
Ví dụ
Ví dụ 1
Input
1 1 3 22
5
10
9 2 3Output
5Giải thích
Có \(3\) cách chọn hương vị, ốc quế và đồ phủ như sau:
- Giá lần lượt là \(5, 10, 9\): tổng giá là \(24\), nên điểm số là \(|24 - 22| = 2\).
- Giá lần lượt là \(5, 10, 2\): tổng giá là \(17\), nên điểm số là \(|17 - 22| = 5\).
- Giá lần lượt là \(5, 10, 3\): tổng giá là \(18\), nên điểm số là \(|18 - 22| = 4\).
Đầu tiên, Alice chọn hương vị có giá \(5\), rồi Bob chọn loại ốc quế có giá \(10\).
Cuối cùng, vì Alice muốn điểm số lớn nhất có thể, lựa chọn tối ưu là loại đồ phủ có giá \(2\), để điểm số bằng \(5\).
Vì vậy, khi cả hai lựa chọn tối ưu, điểm số là \(5\).
Ví dụ này thỏa mãn ràng buộc của tất cả các bài toán con.
Ví dụ 2
Input
1 2 2 100
11
33 44
40 60Output
15Giải thích
Có \(4\) cách chọn hương vị, ốc quế và đồ phủ như sau:
- Giá lần lượt là \(11, 33, 40\): tổng giá là \(84\), nên điểm số là \(|84 - 100| = 16\).
- Giá lần lượt là \(11, 33, 60\): tổng giá là \(104\), nên điểm số là \(|104 - 100| = 4\).
- Giá lần lượt là \(11, 44, 40\): tổng giá là \(95\), nên điểm số là \(|95 - 100| = 5\).
- Giá lần lượt là \(11, 44, 60\): tổng giá là \(115\), nên điểm số là \(|115 - 100| = 15\).
Đầu tiên, Alice chọn hương vị có giá \(11\).
Tiếp theo, Bob chọn một trong hai loại ốc quế có giá \(33\) và \(44\). Tùy theo lựa chọn của Bob, Alice sẽ thực hiện như sau để điểm số lớn nhất có thể:
- Nếu Bob chọn loại ốc quế có giá \(33\), Alice chọn loại đồ phủ có giá \(40\), để điểm số bằng \(16\).
- Nếu Bob chọn loại ốc quế có giá \(44\), Alice chọn loại đồ phủ có giá \(60\), để điểm số bằng \(15\).
Vì Bob muốn điểm số nhỏ nhất có thể, lựa chọn tối ưu là loại ốc quế có giá \(44\), để điểm số bằng \(15\).
Vì vậy, khi cả hai lựa chọn tối ưu, điểm số là \(15\).
Ví dụ này thỏa mãn ràng buộc của các bài toán con \(2, 3, 4, 5\).
Ví dụ 3
Input
2 2 2 0
15 23
5 16
23 45Output
73Giải thích
Khi \(P = 0\), điểm số chính là tổng giá của hương vị, ốc quế và đồ phủ đã chọn. Vì vậy, lựa chọn tối ưu của Alice là hương vị và loại đồ phủ có giá cao hơn, còn lựa chọn tối ưu của Bob là loại ốc quế có giá thấp hơn.
Do đó, giá của hương vị, ốc quế và đồ phủ được chọn lần lượt là \(23, 5, 45\), và điểm số là \(73\).
Ví dụ này thỏa mãn ràng buộc của các bài toán con \(3, 4, 5\).
Ví dụ 4
Input
3 3 3 50
12 5 5
2 19 37
10 5 15Output
14Giải thích
Lưu ý rằng có thể tồn tại các hương vị, các loại ốc quế hoặc các loại đồ phủ có cùng giá.
Ví dụ này thỏa mãn ràng buộc của các bài toán con \(3, 4, 5\).
Nguồn
Bản dịch tiếng Việt từ đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.
Kỳ thi:
- JOI 2025 - Vòng loại 2 (8 Tháng 12., 2024)
Bình luận