AT_tenka1_2012_final_c Code Art Online

[problemUrl]: https://atcoder.jp/contests/tenka1-2012-final/tasks/tenka1_2012_final_c Code Art Online は符号《コード》の世界のRPGです。 プレーヤーは符号《コード》を生成して戦います。 符号《コード》は文字《グラム》を連ねることで生成します。 このゲームには、あなたの操作する プレーヤー と、プレーヤーに立ちはだかる 敵 という2種類のキャラクターが登場します。 $ 1 $ ターンは、敵の攻撃、プレーヤーの攻撃、敵の回復、プレーヤーの回復の順に行われます。 ゲーム開始時のプレーヤーの HP（体力）は $ 100 $ であり、これが $ 0 $ 以下になるとゲームオーバーです。 あなたは、プレーヤーを以下の3種類の文字《グラム》を使って操作することができます。 - `A` : 敵の HP に $ 5 $ ダメージを与える - `B` : `B` が連続した数だけ敵の HP にダメージを与える - `C` : プレーヤーの HP を $ 50 $ 回復する 例えば、`BBB` と操作すると、$ 1 $ ターン目に $ 1 $ ダメージ、$ 2 $ ターン目に $ 2 $ ダメージ、$ 3 $ ターン目に $ 3 $ ダメージを敵の HP に与えます。 プレーヤーの最大 HP は $ 100 $ であり、これを超えて回復しようとした場合には HP は $ 100 $ となります。 同一ターン内の被ダメージ処理と回復処理は被ダメージ処理の方が先に行われるので、被ダメージ処理が終わった段階で HP が $ 0 $ 以下になった場合、その時点でゲームオーバーとなります。 敵には最大 HP と攻撃力と回復力のパラメーターがあります。 敵の HP は現れた時には最大 HP と同じ値です。 毎ターンに攻撃力の値だけプレーヤーの HP にダメージを与え、回復力の値だけ HP を回復します。 ただし、最大 HP を超えて回復しようとした場合は、HP は最大 HP と同じ値になります。 敵の回復処理はプレーヤーと同じく被ダメージ処理の後に行われるので、被ダメージ処理が終わった段階で HP が $ 0 $ 以下になった場合、回復は行われずその敵は倒れます。 敵が複数存在する場合、戦っている敵を倒すと自動的に次の敵が現れ、次のターンにはその敵と戦うことになります。 例えば、敵が $ 2 $ 体いて、$ 1 $ 体目の敵の HP が $ 10 $、攻撃力が $ 15 $、回復力が $ 1 $ であり、$ 2 $ 体目の敵の HP が $ 20 $、攻撃力が $ 10 $、回復力が $ 2 $ であるとします。 この時、`AAACBBBBBB` という符号《コード》で戦えば、次のように $ 2 $ 体の敵を倒すことができます。 ``` ターン 符号 プレーヤーHP 敵HP 1 A 85 6 2 A 70 2 3 A 55 0 # 一体目の敵を撃破 4 C 95 20 # プレーヤーは10ダメージを受けた後に50回復する 5 B 85 20 # 敵は1ダメージ受けた後に1回復する 6 B 75 20 # 敵は2ダメージ受けた後に2回復する 7 B 65 19 8 B 55 17 9 B 45 14 10 B 35 10 11 B 25 5 12 B 15 0 ``` 敵の数とそれぞれの敵の HP、攻撃力、回復力を与えるので、すべての敵をゲームオーバーせずに最短ターン数で倒す符号《コード》の長さを答えなさい。 入力は以下の形式で標準入力から与えられる。 > $ N $ $ a_1 $ $ b_1 $ $ c_1 $ : $ a_N $ $ b_N $ $ c_N $ - $ 1 $ 行目には敵の数 $ N $ ($ 1\ \leq\ N\ \leq\ 30 $) が与えられます。 - $ 2 $ 行目から $ N+1 $ 行目までには、それぞれの敵の HP $ a_i $ ($ 1\ \leq\ a_i\ \leq\ 100 $)、攻撃力 $ b_i $ ($ 0\ \leq\ b_i\ \leq\ 100 $)、回復力 $ c_i $ ($ 0\ \leq\ c_i\ \leq\ 100 $) がスペース区切りで与えられます。 ゲームオーバーせずに最短ターン数で倒す符号《コード》の長さを出力せよ。 敵を倒すことが不可能であれば、 `-1` を出力せよ。 なお、行の終端には改行が必要である。

N/A

N/A