Lv.1 ロールプレイングゲーム

リソース制約

問題文

CCS部員であるあなたは、ドラクエ風のゲームの戦闘システムを組むことになった。
戦闘では、味方（自分含む）、相手はそれぞれHPと呼ばれるステータスを持っており、
この値が0以下になると戦闘不能となる。

HPがhpである者に、攻撃力atkの攻撃を与えると、新しいHPは次のように計算される。

(新しいHP) = hp - atk

現在、あなたは「敵の攻撃によって、味方が戦闘不能となるかどうか」を調べているところである。
情報として、敵の攻撃の攻撃力と、味方4人のHPが与えられる。
敵がそれぞれの味方に攻撃した場合、その味方が戦闘不能となるかならないかをそれぞれ出力せよ。

入力

入力は2行からなる。

ATK
HP1 HP2 HP3 HP4

1行目には、敵の攻撃の攻撃力が与えられる。
2行目には、それぞれの味方のHPが与えられる。（固定で4つ与えられる）

出力

ISDEAD1
ISDEAD2
ISDEAD3
ISDEAD4

攻撃力ATKの攻撃が、HP1〜HP4の味方に当たった場合、
その味方が死ぬかどうかを4行にわたって出力せよ。 1行目がHP1の味方、2行目がHP2の味方、3行目がHP3の味方、4行目がHP4の味方に攻撃が当たった場合の出力を表す。

それぞれの行で、戦闘不能であれば、

DEAD

そうでなければ、

ALIVE

を出力せよ。
また、末尾に改行を出力すること。

制約

• $1≦HP1≦255$
• $1≦HP2≦255$
• $1≦HP3≦255$
• $1≦HP4≦255$
• $1≦ATK≦255$

サンプル

入力1

30
10 20 30 40

出力1

DEAD
DEAD
DEAD
ALIVE

「0以下」が戦闘不能なので、HPが0になると戦闘不能になります。

Lv.2 音楽ゲーム

リソース制約

問題文

T君は、大学の講義の帰りにゲームセンターに通い、ある音ゲーを練習している。
T君の練習している音ゲーの仕様は以下である。

• 譜面は 縦$N$行・横$M$列 の記号の2次元配列で表される
  • 文字「*」は単発押しのノーツを表す
  • 文字「+」は長押しのノーツを表す
  • 文字「_」はそこにノーツが無いことを表す
• 譜面は上から下の行に向かって順番に流れて行く。
  • このとき、一番下の行に到達したノーツの列に対応するボタンを押すことで得点が得られる。
• 同じ列に並んだ*は、その列のボタンをその度に押し直さなければ得点にならない。
  • 一つの*について10点が与えられる。
• 同じ列に並んだ+は、+が続く間その列のボタンを押し続けることで得点が得られる。
  • （長さに関わらず）100点が与えられる。
• この音ゲーでは、どのような操作をしたとしても減点されることは無い。
• 最初の持ち点は0点である。

練習に熱心なT君は、与えられた譜面に対して、T君が得ることができる最大の得点の理論値はいくらであるかを計算したくなった。
そこで、T君は優秀なプログラマーであるあなたに、これを計算するプログラムを書いて欲しいと頼んだ。
譜面の情報が与えられるので、最大の得点の理論値はいくらであるかを出力するプログラムを書け。

なお、T君は超人的な練習を積んでいるので、100列の同時押し等、
通常の人間には不可能と思われる譜面も問題なく処理することができる。

入力

N M
S(11)S(12)…S(1M)
S(21)S(22)…S(2M)
…
S(N1)S(N2)…S(NM) 

1行目には譜面の行数$N$、列数$M$が半角スペース区切りで与えられる。
2行目以降には譜面の情報$S(ab)$が$N$行に渡って区切り文字なしで与えられている。
$S(ab)$は譜面のa行b列目のノーツの種類を表す。
また、$S(ab)$は*、+、_のどれかの文字から構成されている。

出力

T君が取ることができる最大の得点の理論値を1行に出力せよ。
末尾に改行を出力すること。

制約

• $1≦N≦1000$
• $1≦M≦1000$

サンプル

入力1

8 4
__*+
_*_+
*__+
*_*_
_*_+
__*+
___*
__*+

出力1

390

単発押し(10点)が9回、長押し(100点)が3回あるので、理論値は9*10+3*100=390点となります。

入力2

8 8
*___*_+*
_*_*_*+*
*+*_*+_*
_*****_*
*_*_*__*
_*+*+*_*
*****_+*
_*_*_*+*

出力2

950

どんなに複雑な譜面でもT君はこなすことができます。

Lv.3 シューティングゲーム

リソース制約

問題文

CCSの部員であるあなたは、あるシューティングゲームのボスを作成することになった。
今回作るボスは以下の仕様を満たす。

• ボスは、通し番号がつけられている「節」と「足」の2種類の部品（複数個）から構成される。
  • 中心に節があり、その番号は0番とする。
  • 番号0番以外の節、及び足は、他の節1つを接続先として繋がっている。
  • それぞれの足には得点が設定されている。
• ある節を攻撃して消した時、接続先が消えた節及び足が連鎖的に全て消える。
  • 消えた足の得点の合計の点数を得ることができる。
  • 番号0番の節には接続先が存在しないが、直接攻撃されない限り消えることはない。

ボスの情報として、中心を除く節の個数($N$)、足の個数($M$)と得点、
そして節や足の接続先の情報（ボスのカタチ）が与えられる。
番号$T$番の節を攻撃して消した時、得られる得点を求めるプログラムを作れ。

入力

入力は以下からなる。

N M T
A(1)
A(2)
… 
A(N)
B(1) C(1) 
B(2) C(2)
… 
B(M) C(M)

$N$は、中心以外の節の数
$M$は、足の数
$T$は、攻撃して消す節の番号を表す。
$A_i$($1≦i≦N$)は、番号i番の節の接続先の節の番号を表す。
$B_i$($1≦i≦M$)は、番号i番の足の接続先の節の番号を表す。
$C_i$($1≦i≦M$)は、番号i番の足の得点を表す。

出力

番号$T$番の節を攻撃して消した時、得られる得点（消える足の得点の合計）を求めるプログラムを作れ。

制約

• $0≦N≦100000$
• $0≦M≦100000$
• $0≦T≦N$
• $0≦A_i≦N$かつ$A_i ≠ i$
• $0≦B_i≦N$
• $0≦C_i≦100000$
• ある節から、接続先をたどっていったとき、元の節に到達することはない。（閉路はない）

部分点制約

この問題には部分点が設定されている。 - 70%分のテストケースについて、$0≦N≦1000$かつ$0≦M≦1000$を満たす。

サンプル

入力1

3 5 1
0
0
1
0 1
1 1
2 1
3 1
3 1

出力1

3

以下のようになるので、得られる得点は3点です。

入力2

3 5 0
0
0
1
0 1
1 1
2 1
3 1
3 1

出力2

5

先ほどの図で、0番（つまり中心の節）を攻撃した場合です。

Lv.4 胡瓜一閃

リソース制約

問題文

ここに、「きゅうり」と「ちくわ」が$N$組ある。
$i(1≦i≦N)$組目のそれぞれの長さは「きゅうり」が$A_i$cm、「ちくわ」が$B_i$cmで表される。

CCS新入生のK君は、「ちくわ」は円筒状であり「きゅうり」を「ちくわ」の中に差し込むことができることに気がついた。
そこで、それぞれの組の「きゅうり」を対応する「ちくわ」の中に$C_i$cm
（ただし、$C_i < A_i$かつ$C_i < B_i$を満たす）だけ差し込み完全に固定することで、$N$組のパーツを作った。
このパーツを「ユニット」と呼び、きゅうりの頭が出ている方を「ユニットの頭」、もう一方を「ユニットの穴」と呼ぶことにしよう。

さらに、K君はある「ユニット」の頭を、別の「ユニット」の穴に差し込む
ということを繰り返すことで1つの巨大な「棒」を作り上げる。
また、差し込む時は下図の示すように物理的に差し込めるところまで
(ちくわとちくわ、またはきゅうりときゅうりがぶつかるまで)詰めて差し込む。

K君は「ユニット」を差し込む順番によって、最終的に出来上がる巨大な「棒」の長さが異なることに気がついた。
作れる巨大な「棒」の最小の長さ$L_{min}$と最大の長さ$L_{max}$を出力するプログラムを書け。
なお、「棒」の長さとは、一番端の「ちくわ」の末端から、一番端で飛び出ている「きゅうり」の末端までの長さとする。

入力

N
A1 B1 C1
A2 B2 C2
…
AN BN CN

1行目には「きゅうり」と「ちくわ」の組数（ユニット数）$N$、
$i + 1$行目$(1≦i≦N)$には、$i$組目のユニットに関する情報$A_i$、$B_i$、$C_i$が半角スペース区切りで書かれている。

• $A_i$は「きゅうり」の長さ
• $B_i$は「ちくわ」の長さ
• $C_i$は「ユニット」を作るときに差し込んだ長さ

を表す。

出力

K君が作ることができる巨大な棒の最小の長さ$L_{min}$と最大の長さ$L_{max}$を次のように半角スペース区切りで1行に出力せよ。

L(min) L(max)

末尾に改行を出力すること。

制約

• $1≦N≦15$
• $2≦A_i≦100$
• $2≦B_i≦100$
• $1≦C_i≦99$
• $C_i < A_i$ かつ $C_i < B_i$を満たす
• $A_i$、$B_i$、$C_i$は自然数である

部分点制約

この問題には部分点が設定されている。 - 50%のテストケースについて、$1≦N≦8$を満たす。

サンプル

入力1

2
5 5 2
5 4 3

出力1

12 13

入力2

8
5 5 2
5 4 3
5 3 2
9 8 5
6 9 5
2 3 1
8 8 7
8 7 2

出力2

50 60