問題一覧 > 通常問題

No.12 限定された素数

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 227
作問者 : nmnmnmnmnmnmnmnmnmnmnmnmnmnm
3 ProblemId : 34 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-03-19 16:10:29

問題文

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

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

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

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

入力

N
A1  Ai  AN

1行目は、与えられる数字の数 N (1N10)が与えられる。
2行目は、N個の与えられる数字Ai (0Ai9)が半角スペース区切りで与えられる。
ijの時はAiAjである。

出力

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

サンプル

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

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

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

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

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

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

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

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

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

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。