Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SPOJ 123 - Paying in Byteland [PAYING] (この記事を編集する[管理者用])

Source

SPOJ 123 [PAYING]

問題概要

nが与えられたとき,
 n=c[1]+c[2]+...+c[k]
として,
 c[1]円玉,c[2]円玉,…,c[k]円玉
を持ってる時,1円からn円までお釣りなしで支払う方法が存在するようなkの最小値を求める問題.
ただし,
 c[j] = 2の冪
でなければならない.
nは10^1000以下.

解法

nを2進数で書いたとき,(頭についているのは除いて) 0が現れないように変形していく.
例えばn=21=16+4+1なら
 10101 (c[0]=16, c[1]=4, c[2]=1)
  ↓
 10021 (c[0]=16, c[1]=2, c[2]=2, c[3]=1)
  ↓
 02021
  ↓
 01221
という感じ.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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