hotpepsiの練習帳

SRM 665

01:17

https://competitiveprogramming.info/topcoder/srm/round/16514/div/1

Div1 Easy (250) LuckySum

問題

• 4か7だけからなる数がラッキーナンバー
• ラッキーナンバー同士の和をラッキーサムとする
• 数値または?からなる文字列noteが与えられる
• ?は任意の数字、ただし先頭は0ではない
• noteの条件を満たす最小のラッキーサムを求める

方針

• (終了後)
• 上の桁と下の桁、7桁ずつに分割して考える
• 7桁までのラッキーナンバーを全列挙しておく
• 7桁以下ならテーブルひくだけ
• 下の桁で有効な和の組み合わせを全列挙する
• 上の桁で、有効な和の組み合わせを全列挙する
• その際、桁上がりの有無を両方試して、下の桁の有効なものと組み合わせる
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_665/LuckySum.cpp

結果

--- 0pt unrated

桁DPらしい。

テストケースの不備でdiv1はunrated。

http://togetter.com/li/859452