スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

SRM 524 Div2 hard

昨日書けなかった分.

この問題は私は解けてませんが,人のコード見てわかった (つもり) なので一応書きます.


hard 問題

与えられる数値 N (1以上10000以下) に対して以下の条件を満たす最小値 x を求める.

1. x は N の倍数である.
2. x は別途定められた使用できない数字を含んでいない

x が存在しない場合は "IMPOSSIBLE" と出力せよ.
x が存在して,その桁数が9桁未満の場合は x を出力せよ.
x が存在して,その桁数が9桁以上の場合は,"abc...def(g digits)" と出力せよ.
abc は x の最初の3桁,def は x の最後の3桁,g は x の桁数である.


例:

N = 8
使用できない数字 2,3,4,5,6,7,8,9
この場合,条件を満たす値のうち最小値は 1000 (8*125)である.

N = 9
使用できない数字 1,3,4,5,6,7,8,9
この場合,条件を満たす値のうち最小値は 222222222 (9*24691358)である.
これは 9 桁以上なので "222...222(9 digits)" と出力する.

N = 10000
使用できない数字 0
この場合,条件を満たす値は存在しないので "IMPOSSIBLE" と出力する.


続きから解説.
条件を満たす数値がある場合は,単純に探してそれが 9 桁以上であるかどうかを判定すればよい.

問題は条件を満たす数値が存在しないことをどうやって知るか.

私はこれでつまった...

例として,与えられた数字が 12,使用できない数字が 0,1,2,3,4,6,8,9 の場合を考えてみる.

この時逆に使える数字は 5,7 であり,条件を満たす値があるとすれば,これらの値の組み合わせである.

ただ組み合わせは,5,7,55,57,75,77 … と無限に存在する.

ここでこのように組み合わせて作られる数値と,それを 12 で割った剰余に注目する.

この剰余が 0 であれば,その数字が条件を満たす x であることが分かる.

剰余が 0 でない場合はその数の末尾に数字を追加して新たな数字を作ってまた調べる.

この操作について考えてみよう.

例えば 77 と 557 の場合,それぞれの剰余は.

77 mod 12 = 5
557 mod 12 = 5

と同じである.

ここでそれぞれの数から作り出せる次の数字を考えてみる.

77 → 775,777
557 → 5575,5577

さらにこれらの剰余を考える.

775 mod 12 = 7 … ①
777 mod 12 = 9

5575 mod 12 = 7 … ②
5577 mod 12 = 9

というわけで,剰余が同じ数の末尾に同じ数字をつけた場合,①と②のように剰余は同じになるのである.

数学的に書いてみる.

最初の数を w,後ろにつける数を y,新しくできる数は z = w * 10 + y で w mod N = m とすると.

z mod N
 = (w * 10 + y) mod N
 = ((w * 10) mod N) + (y mod N)
 = (((w mod N) * 10) mod N) + (y mod N)
 = ((m * 10) mod N) + (y mod N)

このようになり,m と y が等しければ z mod N が等しいことがわかる.

つまり,剰余が同じ数が現れた時点で,その先に剰余 0 となる値が存在しないことがわかる.

プログラム的な実装方針の話をすると,探索を進めながら剰余の値を記録しておく.

新たに生成した数の剰余がすでに記録する場合は,それいこうの探索を行わない.

こうすることでその先に条件を満たす数が存在しないことがわかる.

最後に簡単に図示.丸の中が数字でその横が 12 で割った剰余.

探索を続けていくと,557 という剰余が 5 の数にたどり着くが,剰余が 5 の数は既に記録している (最初の5)

よってこの先を探索しても 5 から探索した場合と同じ結果しか得られないので,ここで探索は打ち切る.

SRM524_hard.png
スポンサーサイト

コメントの投稿

非公開コメント

お知らせ
相互リンクしてくださる方募集してます!!
Twitter 相互フォロワ―も募集してます!!
コメントも募集してます!!
感想でも質問でも気軽にどうぞ!!

ランキング参加してます!!
クリックお願いします!!

にほんブログ村 高校生日記ブログ 高専生へ
検索フォーム
最新コメント
リンク
admin
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。