Skip to content
Sign in

ジョイ四人組 (JOI04)

Unrated
日本語

Language

Contribute a translation
Time limit
3000 ms
Memory limit
1024 MB
Submissions
0
Correct
0
Solved by
0
AC rate
—

Statement

JOI 中学校には \(4N\) 人の一年生が在籍しており，\(4\) つのクラスに分かれている．各クラスの情報は以下の通りである．

  • 1 年 A 組： \(N\) 人の生徒がいる．それぞれの生徒の身長は \(A_1, A_2, \ldots, A_N\) である．
  • 1 年 B 組： \(N\) 人の生徒がいる．それぞれの生徒の身長は \(B_1, B_2, \ldots, B_N\) である．
  • 1 年 C 組： \(N\) 人の生徒がいる．それぞれの生徒の身長は \(C_1, C_2, \ldots, C_N\) である．
  • 1 年 D 組： \(N\) 人の生徒がいる．それぞれの生徒の身長は \(D_1, D_2, \ldots, D_N\) である．

来月，JOI 中学校では体育祭が開催されることになった．体育祭には，リレー，騎馬戦，棒倒しなどの様々な種目があるが，各学年が踊るダンスは「体育祭の華」とも呼ばれる注目の種目である．

ここで一年生は，各クラスから代表を \(1\) 人ずつ選び，\(4\) 人でダンスをすることになった．ダンスの見栄えをできるだけ良くするため，身長の差ができるだけ小さくなるように \(4\) 人組を選ぶことにした．

一年生の身長が与えられるとき，「\(4\) 人の身長の最大値」と「\(4\) 人の身長の最小値」の差として考えられる最小の値を求めるプログラムを作成せよ．

Constraints

  • \(1 \leqq N \leqq 75\,000\)．
  • \(1 \leqq A_i \leqq 10^9\) (\(1 \leqq i \leqq N\))．
  • \(1 \leqq B_j \leqq 10^9\) (\(1 \leqq j \leqq N\))．
  • \(1 \leqq C_k \leqq 10^9\) (\(1 \leqq k \leqq N\))．
  • \(1 \leqq D_l \leqq 10^9\) (\(1 \leqq l \leqq N\))．
  • 入力される値はすべて整数である．

Subtasks

  1. (\(7\) 点) \(N = 1\)．
  2. (\(23\) 点) \(N \leqq 30\)．
  3. (\(14\) 点) \(N \leqq 2\,000\)，\(A_i \leqq 10\) (\(1 \leqq i \leqq N\))，\(B_j \leqq 10\) (\(1 \leqq j \leqq N\))，\(C_k \leqq 10\) (\(1 \leqq k \leqq N\))，\(D_l \leqq 10\) (\(1 \leqq l \leqq N\))．
  4. (\(20\) 点) \(N \leqq 2\,000\)，\(A_i \leqq 2\,000\) (\(1 \leqq i \leqq N\))，\(B_j \leqq 2\,000\) (\(1 \leqq j \leqq N\))，\(C_k \leqq 2\,000\) (\(1 \leqq k \leqq N\))，\(D_l \leqq 2\,000\) (\(1 \leqq l \leqq N\))．
  5. (\(13\) 点) \(N \leqq 2\,000\)．
  6. (\(23\) 点) 追加の制約はない．

Input

入力は以下の形式で与えられる．

\(N\)
\(A_1\) \(A_2\) \(\cdots\) \(A_N\)
\(B_1\) \(B_2\) \(\cdots\) \(B_N\)
\(C_1\) \(C_2\) \(\cdots\) \(C_N\)
\(D_1\) \(D_2\) \(\cdots\) \(D_N\)

Output

「\(4\) 人の身長の最大値」と「\(4\) 人の身長の最小値」の差として考えられる最小の値を \(1\) 行で出力せよ．

Examples

Sample input 1
1
169
173
152
200
Sample output 1
48

\(N = 1\) なので，全員の生徒を選んで \(4\) 人組を作らなければならない．このとき，\(4\) 人の身長の最大値は \(200\)，最小値は \(152\) となり，その差は \(200 - 152 = 48\) である．よって，\(48\) を出力する．

この入力例は小課題 \(1, 2, 4, 5, 6\) の制約を満たす．

Sample input 2
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
Sample output 2
2

この入力例は小課題 \(2, 3, 4, 5, 6\) の制約を満たす．

Sample input 3
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
Sample output 3
0

この入力例は小課題 \(2, 3, 4, 5, 6\) の制約を満たす．

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

この入力例は小課題 \(2, 4, 5, 6\) の制約を満たす．

Sample input 5
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
Sample output 5
79

この入力例は小課題 \(2, 5, 6\) の制約を満たす．

Notes

JOI 2023 · JCIOI · CC BY-SA 4.0

Tags

No tags yet

Source