Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12041 - BFS (Binary Fibonacci String) (この記事を編集する[管理者用])

Source

Next generation Contest 6 (2011-06-25)
UVa 12041

問題概要

文字列として,
 BFS(0) = 0
 BFS(1) = 1
 BFS(n) = BFS(n-2) + BFS(n-1)
とする.+は文字列の連結.
BFS(n)のi文字目からj文字目を出力する問題.
n, i, jは2^31未満で,j-iは10000以下.

解法

一文字ずつ出力すれば良い.
最初にBFS(n)の文字数を求めておく.(フィボナッチ)
後,nがあまりに大きいと,明らかにf(n)のi文字目は,f(n-2)のi文字目なので,例えば,nが50以下になるまで,nを2の倍数だけ減らす.
再帰的に,i文字目は,BFS(n-2)に含まれるか,BFS(n-1)に含まれるか判定し,1つnの小さい問題に帰着させる.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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