No.12 限定された素数

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 112
作問者 : nmnmnmnmnmnmnmnmnmnmnmnmnmnm

0 ProblemId : 34 / 出題時の順位表

問題文

'\(0\)'から'\(9\)'までの数字が重複せず\(N\)個与えられる。

次に、\(1\)以上\(5000000\)以下の範囲から\(K\)以上\(L\)以下の範囲を選ぶ。
\(K\)以上\(L\)以下の範囲から素数のみをすべて取り出す。
すべての素数について使われている数字を調べる。
例えば、\(K\)以上\(L\)以下の範囲で\(10\)以上\(20\)以下の範囲を選んだとき、
すべての素数は"\(11\)"、"\(13\)"、"\(17\)"、"\(19\)"の\(4\)つ。
使われている数字は'\(1\)'と'\(3\)'と'\(7\)'と'\(9\)'の\(4\)つである。
この使われている数字と最初に与えられた数字を等しくしたい。
(すべて使われないといけない)
この時の\(K\)と\(L\)の差\(L-K\)の最大値を求めよ。
そのような場合がなければ\(-1\)を答えとせよ。

以下は無効な例
与えられた数字が\([3,5,7]\)の場合
\(4\)以上\(7\)以下の範囲での素数は \(5,7\)となるので\(3\)が含まれてないので無効な範囲である。
\(2\)以上\(10\)以下の範囲での素数は \(2,3,5,7\)となるので\(2\)が余計に含まれており無効な範囲である。

この場合、「\(3\)以上\(7\)以下」や「\(3\)以上\(10\)以下」などが有効な範囲である。

入力

\(N\)
\(A_1\ \dots\ A_i\ \dots\ A_N\)

\(1\)行目は、与えられる数字の数 \(N\ (1 \leq N \leq 10)\)が与えられる。
\(2\)行目は、\(N\)個の与えられる数字\(A_i\ (0 \leq A_i \leq 9)\)が半角スペース区切りで与えられる。
$i \neq j$の時は$N_i \neq N_j$である。

出力

\(K\)と\(L\)の差\(L-K\)の最大値を求めよ。
条件を満たすものがなければ\(-1\)を答えとせよ。
最後に改行すること。

サンプル

サンプル1
入力
1
5
出力
2

\(4\)以上\(6\)以下の範囲の素数をすべて抜き出すと '\(5\)'のみであり、
これは与えられた数字 と素数で使われている数字が一致する。
この時 \(6-4=2\)が\(L-K\)の最大値となる。
(\(5\)以外に \(5\)のみで構成される素数はない)

サンプル2
入力
5
1 2 3 4 5
出力
158

\(K=2354300\)、\(L=2354458\)のとき
すべての素数は
"\(2354311\)"と"\(2354351\)"と"\(2354353\)"と"\(2354413\)"の\(4\)つ。
これはちょうど'\(1\)'、'\(2\)'、'\(3\)'、'\(4\)'、'\(5\)'の数字を使う。
条件を満たす場合は他にもあるが、
この場合の\(2354458-2354300=158\)が最大値となる。

サンプル3
入力
2
0 3
出力
-1

ある範囲を選んだ時に\(0\)と\(3\)を使うような素数の範囲を選ぶことができないので\(-1\)を出力します。

サンプル4
入力
10
0 1 2 3 4 5 6 7 8 9
出力
4999999

\(1\)以上\(5000000\)以下のすべての範囲を選択することが可能。

サンプル5
入力
2
1 3
出力
94

提出ページヘ