問題一覧 > 通常問題

No.437 cwwゲーム

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

問題文

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

詳細は以下の通りです。

  • cww数とは、10進表記で $cww$ となる数である。ただし $c \neq 0, c \neq w$ とする。
    • 例: 355, 700はcww数であるが、123, 551, 099はcww数でない
  • ゲームは以下のように進行する。
$N = a_0 a_1 \dots a_{L-1}$ (10進数表記)
$I = \{0, 1, ..., L-1\}$
$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$ ($1 \leq N \leq 10^{12}$) が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もしくは右上の雲マークをクリックしてアカウントを作成してください。