問題一覧 > 通常問題

No.437 cwwゲーム

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 219
作問者 : 🍡yurahuna / テスター : moti
8 ProblemId : 1126 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2016-10-26 00:51:58

問題文

Cさんは数を使ったあるゲームに取り組んでいます。
このゲームではまず、ある正の数 N が与えられます。
ゲームの目的は、N からうまくいくつかの"cww数"を取り出し、それらの和をできるだけ大きくすることです。

詳細は以下の通りです。

  • cww数とは、10進表記で cww となる数である。ただし c0,cw とする。
    • 例: 355, 700はcww数であるが、123, 551, 099はcww数でない
  • ゲームは以下のように進行する。
N=a0a1aL1 (10進数表記)
I={0,1,...,L1}
score=0

while true:
	Iから異なる3つの要素i, j, kを選ぶ (i<j<k)
	x = a_i a_j a_k がcww数であるとき
		score += x
		Iからi, j, kを除く

	xがcww数となるようなi,j,kの選び方がなければ終了
Cさんが最終的に得られるscoreの最大値はいくつでしょうか?

入力

N

入力には正の整数 N (1N1012) が1行で与えられる。

出力

Cさんが得られるscoreの最大値を1行で出力し、最後に改行してください。

サンプル

サンプル1
入力
133144
出力
344

例えば最初の(i, j, k)として(2, 4, 5)を取るとcww数344を作れます。残りの部分からはcww数を作ることができません。これが最大のscoreとなります。
(i, j, k)として(0, 1, 2), (3, 4, 5)を順に取ると2つのcww数133, 144を作ることができますが、これらの和は277となり344よりも小さいです。

サンプル2
入力
11
出力
0

cww数を1つも作ることができないので、答えは0です。

サンプル3
入力
2718281828
出力
1821

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。