Skip to content
Sign in

究極の団子職人 (Ultimate Dango Maker)

Unrated
日本語

Language

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

Statement

JOI 君は団子職人である．団子には色 \(1\) から色 \(N\) までの \(N\) 色あり，JOI 君は色 \(i\) (\(1 \leqq i \leqq N\)) の団子を \(A_i\) 個持っている．

JOI 君は持っている団子から \(3\) 個選んで \(1\) 本の串団子を作ることができる．ただし，選んだ \(3\) 個の団子の色が \(c_1, c_2, c_3\) (\(1 \leqq c_1 \leqq N\)，\(1 \leqq c_2 \leqq N\)，\(1 \leqq c_3 \leqq N\)) であるとき，\(c_1\) と \(c_2\)，\(c_2\) と \(c_3\)，\(c_3\) と \(c_1\) の差はそれぞれ \(1\) 以下でなければならない．つまり以下の条件がすべて成り立つ必要がある．

  • \(|c_1 - c_2| \leqq 1\)
  • \(|c_2 - c_3| \leqq 1\)
  • \(|c_3 - c_1| \leqq 1\)

複数の串団子で同じ団子を共有して使うことはできない．JOI 君は持っている団子をうまく選んでできるだけ多くの串団子を作りたい．

JOI 君が持っている団子についての情報が与えられたとき，JOI 君が作ることのできる串団子の本数の最大値を求めるプログラムを作成せよ．

Constraints

  • \(1 \leqq N \leqq 200\,000\)．
  • \(0 \leqq A_i \leqq 10^9\) (\(1 \leqq i \leqq N\))．
  • 入力される値はすべて整数である．

Subtasks

  1. (\(6\) 点) \(N = 1\)．
  2. (\(9\) 点) \(N \leqq 2\)．
  3. (\(10\) 点) \(A_i\) は \(3\) の倍数である (\(1 \leqq i \leqq N\))．
  4. (\(17\) 点) \(A_i = 2\) (\(1 \leqq i \leqq N\))．
  5. (\(21\) 点) \(A_i \leqq 3\) (\(1 \leqq i \leqq N\))．
  6. (\(37\) 点) 追加の制約はない．

Input

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

\(N\)
\(A_1\) \(A_2\) \(\cdots\) \(A_N\)

Output

JOI 君が作ることのできる串団子の本数の最大値を \(1\) 行で出力せよ．

Examples

Sample input 1
3
3 1 2
Sample output 1
2

色 \(1\) の団子を \(3\) 個使った串団子を \(1\) 本と，色 \(2\) の団子を \(1\) 個と色 \(3\) の団子を \(2\) 個使った串団子を \(1\) 本の合計 \(2\) 本を作ることができる．\(1\) つ目の串団子は \(|1 - 1| = 0 \leqq 1\)，\(2\) つ目の串団子は \(|2 - 3| \leqq 1\)，\(|3 - 3| \leqq 1\) よりこの団子の選び方は条件を満たす．\(2\) 本より多くの串団子を作ることはできないため，\(2\) を出力する．

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

Sample input 2
1
99
Sample output 2
33

色 \(1\) の団子を \(3\) 個使った串団子を \(33\) 本作ることができる．\(33\) 本より多くの串団子を作ることはできないため，\(33\) を出力する．

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

Sample input 3
2
5 6
Sample output 3
3

色 \(1\) の団子を \(3\) 個使った串団子を \(1\) 本と，色 \(1\) の団子を \(2\) 個と色 \(2\) の団子を \(1\) 個使った串団子を \(1\) 本，色 \(2\) の団子を \(3\) 個使った串団子を \(1\) 本の合計 \(3\) 本を作ることができる．\(3\) 本より多くの串団子を作ることはできないため，\(3\) を出力する．

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

Sample input 4
6
0 2 2 3 1 2
Sample output 4
3

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

Sample input 5
1
0
Sample output 5
0

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

Notes

JOI 2026 · JCIOI · CC BY-SA 4.0

Tags

No tags yet

Source