【アルゴリズム問題】yukicoder no.12 限定された素数 by nmさん (level ☆☆☆)
閉じる
閉じる

新しい記事を投稿しました。シェアして読者に伝えましょう

×

【アルゴリズム問題】yukicoder no.12 限定された素数 by nmさん (level ☆☆☆)

2014-08-07 18:08
  • 2
'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
A1 ... Ai ... AN


1行目は、与えられる数字の数N(1<=N<=10)が与えられる。
2行目は、N個の与えられる数字Ai(0<=Ai<=9)が半角スペース区切りで与えられる。

sample1
1
5

ans1
2

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

sample2
5
1 2 3 4 5

ans2
158

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

sample3
2
0 3

ans3
-1

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

sample4
10
0 1 2 3 4 5 6 7 8 9

ans4
4999999

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

sample5
2
1 3

ans5
94

q
7
0 1 2 4 6 7 8


1st. なおさん C++
http://ideone.com/hLJNS6

2nd. デジネイさん D
http://melpon.org/wandbox/permlink/ZsjeiR7IghfozlET



広告
×
http://ideone.com/Al66fg
リストにいれるの0と5000001にすればよかったのかな
64ヶ月前
×
素数のリストを使う方法は想定外だったので、だれか強い人教えて><
64ヶ月前
コメントを書く
コメントをするには、
ログインして下さい。