yuki2006さん のコメント

userPhoto
yuki2006
素数のリストを使う方法は想定外だったので、だれか強い人教えて><
No.2
64ヶ月前
このコメントは以下の記事についています
'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