Entries

スポンサーサイト (この記事を編集する[管理者用])

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

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2354-8c4d4f10
この記事にトラックバックする(FC2ブログユーザー)

UVa 12505 - Searching in sqrt(n) (この記事を編集する[管理者用])

Source

The 8th Hunan Collegiate Programming Contest Semilive (2012-10-14)
UVa 12505

問題概要

20文字以下の0,1からなる文字列Xと,1000000以下の正整数nが与えられる.
nを2進数表示で,小数点以下を書いた時,Xが部分文字列として現れる最初の場所を答える問題.
答えが100以下であることは保証されている.

解法

120桁程度,2進数表示で小数点以下を求めれば良い.
2分探索みたいに,多倍長を使って,両辺2^pしながら,2乗してnを超えるかどうかを調べていくと1桁1桁決まっていく.

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2354-8c4d4f10
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。