JOI 2023 - JOI04 - LQDOJ: Le Quy Don Online Judge

JOI 2023 - JOI04

Dạng bài

Ngôn ngữ cho phép

Assembly, Awk, C, C#, C++, Clang, Cobol, D, ~~Groovy~~, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, ~~Swift~~

Điểm: 1300 (p) Thời gian: 3.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Trường trung học cơ sở JOI có \(4N\) học sinh năm thứ nhất, được chia thành bốn lớp. Thông tin về các lớp như sau:

Lớp A có \(N\) học sinh, với chiều cao lần lượt là \(A_1, A_2, \ldots, A_N\).
Lớp B có \(N\) học sinh, với chiều cao lần lượt là \(B_1, B_2, \ldots, B_N\).
Lớp C có \(N\) học sinh, với chiều cao lần lượt là \(C_1, C_2, \ldots, C_N\).
Lớp D có \(N\) học sinh, với chiều cao lần lượt là \(D_1, D_2, \ldots, D_N\).

Tháng tới, trường tổ chức hội thao với nhiều nội dung như chạy tiếp sức, đấu kỵ mã và kéo đổ cột. Trong đó, tiết mục nhảy của từng khối là nội dung được mong đợi, được ví như điểm nhấn của hội thao.

Khối năm thứ nhất quyết định chọn đúng một học sinh đại diện từ mỗi lớp để tạo thành nhóm bốn người biểu diễn. Để tiết mục trông đẹp mắt nhất có thể, nhóm được chọn cần có độ chênh lệch chiều cao nhỏ nhất có thể.

Cho chiều cao của các học sinh, hãy tìm giá trị nhỏ nhất có thể của hiệu giữa chiều cao lớn nhất và chiều cao nhỏ nhất trong nhóm bốn người được chọn.

Dữ liệu vào

Dữ liệu vào có dạng:

N
A_1 A_2 ... A_N
B_1 B_2 ... B_N
C_1 C_2 ... C_N
D_1 D_2 ... D_N

Dữ liệu ra

In trên một dòng giá trị nhỏ nhất có thể của hiệu giữa chiều cao lớn nhất và chiều cao nhỏ nhất trong nhóm bốn người được chọn.

Ràng buộc

\(1 \le N \le 75\,000\).
\(1 \le A_i \le 10^9\) (\(1 \le i \le N\)).
\(1 \le B_j \le 10^9\) (\(1 \le j \le N\)).
\(1 \le C_k \le 10^9\) (\(1 \le k \le N\)).
\(1 \le D_l \le 10^9\) (\(1 \le l \le N\)).
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: \(N = 1\).
\(23\) điểm: \(N \le 30\).
\(14\) điểm: \(N \le 2000\) và \(A_i, B_i, C_i, D_i \le 10\) với mọi \(1 \le i \le N\).
\(20\) điểm: \(N \le 2000\) và \(A_i, B_i, C_i, D_i \le 2000\) với mọi \(1 \le i \le N\).
\(13\) điểm: \(N \le 2000\).
\(23\) điểm: Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Vì \(N = 1\), phải chọn tất cả học sinh để tạo thành nhóm bốn người. Khi đó, chiều cao lớn nhất là \(200\), chiều cao nhỏ nhất là \(152\), và hiệu của chúng là \(200 - 152 = 48\). Vì vậy, in ra \(48\).

Ví dụ này thỏa mãn ràng buộc của các bài toán con \(1, 2, 4, 5, 6\).

Ví dụ 2

Input

7
7 9 9 4 6 3 5
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1

Output

Giải thích

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, 6\).

Ví dụ 3

Input

7
1 1 1 1 2 1 1
1 2 1 1 1 1 1
1 1 1 1 2 1 1
1 1 1 1 1 1 2

Output

Giải thích

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, 6\).

Ví dụ 4

Input

5
287 690 413 420 138
813 873 223 415 907
261 330 361 747 787
958 672 544 126 345

Output

Giải thích

Ví dụ này thỏa mãn ràng buộc của các bài toán con \(2, 4, 5, 6\).

Ví dụ 5

Input

10
1682 2008 1135 1576 2450 1362 1518 1925 2212 1275
1993 1945 1312 1401 2027 1705 1086 2333 1787 1654
2257 1548 1219 1031 2613 2171 1866 1532 2800 1497
1062 1175 1984 1870 2059 1639 2107 1335 1289 2494

Output

Giải thích

Ví dụ này thỏa mãn ràng buộc của các bài toán con \(2, 5, 6\).

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.

Bình luận

Tải bình luận...

Không có bình luận nào.

Kỳ thi:

JOI 2023 - Vòng loại 2 (11 Tháng 12., 2022)