Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12414 - Calculating Yuan Fen (この記事を編集する[管理者用])

Source

Rujia Liu's Present 5: Developing simplified softwares (2012-01-15)
UVa 12414

問題概要

4文字以上,10文字以下の文字列が与えられる.
Aを整数STに,BをST+1に,…,ZをST+25に置き換えて,数字からなる文字列を作る.
連続する2文字を,全部同時に,その和 mod 10に置き換えるという処理を3文字以下になるまで行う.
3文字になった時,100になるような,最小のSTを求める問題.
10000以下にそのようなSTが存在しないならそれを指摘し,求めなくて良い.

解法

愚直に全部試す.
シミュレーションはO(length^2)かけても大丈夫だけど,
最後に何が残るかは,各数字が最終的に何回足されるかは2項計数で計算できるので,コンビネーションをかけながら足していけば良く,O(length)でもできる.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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