| 第25回日本情報オリンピック 二次予選 |
|
|
2025年12月15日
情報オリンピック日本委員会
|
イタリアのチェゼナーティコ (Cesenatico) はアドリア海に面した港町であり，運河を持つことで知られている．運河には船が停泊しており，観光地としても知られている．ここで，現実を単純化した次のような状況設定を考えたい．
運河は直線状であり，その片側のみがアドリア海に通じている．また，運河には 1 から N までの番号が付けられた N 隻の船が停泊しており，船 i (1 ≦ i ≦ N) はアドリア海から距離 Ai 離れたところに停泊している．
ここで，番号が小さい船ほどアドリア海に近いところに停泊している．すなわち，A1 < A2 < … < AN が成立している．
あなたは町で行われる祭りのために船に色を塗ることにした．具体的にはそれぞれの船につき色 1 から色 N までの N 色の中から 1 色を選び，その色で船を塗る．ここで，以下の条件を満たしたい．
船の見栄えをより良くするために，以下で表される美しさを定義する．
船の情報が与えられたとき，条件を満たす船の塗り方が存在するかを判定し，存在する場合は美しさとしてありうる最大値を求めるプログラムを作成せよ．
入力は以下の形式で与えられる．
N
A1 A2 A3 … AN
条件を満たす船の塗り方が存在しない場合は -1 を出力せよ．存在する場合は美しさとしてありうる最大値を 1 行で出力せよ．
入力例 1
2
1 2
出力例 1
1
例えば，条件を満たさない船の塗り方として以下のようなものが考えられる．
この塗り方において，色 1 で塗られた船の数は 1 隻であるため条件を満たさない．
例えば，条件を満たす船の塗り方として以下のようなものが考えられる．
この塗り方において，色 1 で塗られた船は存在しないため，色 1 についての条件を満たす．また，色 2 で塗られた船のアドリア海からの距離を昇順に並べてできる列は (1, 2) であり，これは等差数列となるため，色 2 についての条件を満たす．したがって，この塗り方は条件を満たす．
この塗り方において，同じ色で塗られた 2 隻の組は船 1 と船 2 である．この 2 隻の間の距離は |A1 − A2| = |1 − 2| = 1 である．したがって，美しさは 1 である．
美しさを 2 以上にすることはできないため，1 を出力する．
この入力例はすべての小課題の制約を満たす．
入力例 2
3
1 10 100
出力例 2
-1
どの色についても，その色で塗られた船の数を 1 隻でないようにするには，船 1, 2, 3 を同じ色で塗る必要がある．
このとき，船 1 を塗った色で塗られた船のアドリア海からの距離を昇順に並べてできる列は (1, 10, 100) であり，これは等差数列でない．
したがって，条件を満たす船の塗り方が存在しないため，-1 を出力する．
この入力例は小課題 2, 3, 4, 5 の制約を満たす．
入力例 3
5
5 6 8 9 11
出力例 3
3
例えば，条件を満たす船の塗り方として以下のようなものが考えられる．
この塗り方において，同じ色で塗られた 2 隻の組は船 1 と船 3，船 1 と船 5，船 2 と船 4，船 3 と船 5 の 4 組である．これらの組における 2 隻の間の距離はそれぞれ 3, 6, 3, 3 である．したがって，美しさは 3 である．
美しさを 4 以上にすることはできないため，3 を出力する．
この入力例は小課題 2, 3, 4, 5 の制約を満たす．