2002/Contest/金沢大会

Problem F : Shredding Company

問題概要

target number と呼ばれる数値と数字列の組が与えられる。与えられた数字列を適当な場所で区切ってそれらの数値の和をとった値のうち,target number を超えない最大の値とその区切り方を出力する。解が存在しないときは error,複数の解が存在するときは rejected をそれぞれ出力する。

数字列が 12346 で target number が 50 の場合。

  • 12 3 4 6 のように区切った場合,和は 12+3+4+6=25。
  • 1 2 3 46 のように区切った場合,和は 1+2+3+46=52。この区切り方は target number を超えているので不適切。

ちなみにこれに対する解は 43 で 1 2 34 6 のように区切ったとき。

解法

値が 6 桁しかないので,すべての区切り方を試すだけでよい。

Sample の 1104 は「1 1 04」と「1 1 0 4」の 2 通りではないかと思われる。このように 0 ではじまる数値についても考慮する必要があるが,0 ではじまる数値を含む区切り方は必ず一意にならないので(例えば 04 の場合は 0 4 と区切っても値は同じ),わざわざ文字列にする必要はない。(泉,2004/04/18)

議論・その他


ファイルを添付する

fileyoshioka_paper.cpp 548件 [詳細] fileterashima_paper.cpp 544件 [詳細] filenoda_paper.cpp 559件 [詳細] filetogami_Main.java 614件 [詳細] filepaper.txt 557件 [詳細] filefrankdock_F.c 624件 [詳細] filepaper_out.txt 532件 [詳細]
[添付ファイル一覧] [全ページの添付ファイル一覧]
アップロード可能最大ファイルサイズは 10,240KB です。

管理者パスワード:

添付ファイル: fileyoshioka_paper.cpp 548件 [詳細] fileterashima_paper.cpp 544件 [詳細] filenoda_paper.cpp 559件 [詳細] filetogami_Main.java 614件 [詳細] filepaper.txt 557件 [詳細] filefrankdock_F.c 624件 [詳細] filepaper_out.txt 532件 [詳細]

Last-modified: 2009-11-06 (金) 13:26:50 (3153d)