AtCoder Beginner Contest 031

A - ゲーム

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君は新しくゲームを買った。

高橋君のゲームキャラクターには攻撃力と防御力が定まっており、レベルが上がると攻撃力と防御力のうち好きなひとつを 1 だけ上げることができる。

高橋君はゲームキャラクターの攻撃力と防御力の積が最大となるように攻撃力か防御力のうちひとつを選んで上げる。もしもどちらを選んでもレベルアップ後の攻撃力と防御力の積が等しくなる場合、攻撃力を選んで上昇させる。

高橋君がゲームキャラクターをレベルアップさせた場合の、レベルアップ後の攻撃力と防御力の積を求めよ。

入力

入力は以下の形式で標準入力から与えられる。

A D

1 行目には、2 個の整数 A (1≦A≦200), D (1≦D≦200) が空白区切りで与えられる。これは、ゲームキャラクターの攻撃力が A で、防御力が D であることを表す。

出力

高橋君がゲームキャラクターをレベルアップさせた後の、ゲームキャラクターの攻撃力と防御力の積を 1 行に出力せよ。

出力の末尾にも改行を入れること。

入力例1

31 87

出力例1

高橋君のキャラクターは、レベルアップ前において攻撃力が 31、防御力は 87 である。

攻撃力を上昇させた場合、攻撃力と防御力の積は (31+1) × 87 ＝ 2784 である。
防御力を上昇させた場合、攻撃力と防御力の積は 31 × (87+1) ＝ 2728 である。

高橋君は攻撃力を上げる選択を取るので、レベルアップ後のキャラクターにおける攻撃力と防御力の積は 2784 である。

入力例2

101 65

出力例2

この場合、高橋君は防御力を上げる。

入力例3

3 3

出力例3

B - 運動管理

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君は AtCoder 社のマスコットキャラクターである。

マスコットキャラクターとしての魅力を維持するために、高橋君は適度な運動をすることになっている。高橋君は週の運動時間が L 分以上 H 分以下でなければならない。

しかしながら、青木君は最近、高橋君が運動しているところを見ていない。高橋君の運動状況が気になった青木君は、高橋君の過去 N 週間の運動時間が制限にあっているのか、そして足りないなら少なくともあと何分運動する必要があったのかを計算するプログラムを作成することにした。

入力

入力は以下の形式で標準入力から与えられる。

L H
N
A_1
A_2
:
A_N

1 行目には、2 個の整数 L, H (1≦L≦H≦10^4) が空白区切りで与えられる。これは、高橋君が週に L 分以上 H 分以下の運動をしなければならないことを表す。
2 行目には、整数 N (1≦N≦50) が与えられる。これは青木君が N 週分の運動時間について調べていることを表す。
3 行目からの N 行には、高橋君の運動状況を表す整数が与えられる。N 行の内 i (1≦i≦N) 行目には、整数 A_i (0≦A_i≦10^4) が与えられる。これは i 個前の週において高橋君が A_i 分運動したことを表す。

出力

出力は N 行からなる。i (1≦i≦N) 行目には、i 個前の週において高橋君が必要な分よりも多く運動している場合は -1 を、そうでない場合は追加で必要な運動時間の最小値を分単位で 1 行に出力せよ。

出力の末尾にも改行を入れること。

入力例1

出力例1

60
0
-1

青木君は 3 個の週について調査している。

1 個前の週において、高橋君は 240 分運動しており、これは運動時間の下限である 300 分に満たない。高橋君はあと 60 分追加で運動する必要があるため、1 行目には 60 を出力する。
2 個前の週において、高橋君は 350 分運動しており、これは運動時間の制限に適している。そのため、2 行目には 0 を出力する。
3 個前の週において、高橋君は 480 分運動しており、これは運動時間の上限である 400 分を越えており、運動しすぎである。そのため、3 行目には -1 を出力する。

入力例2

出力例2

C - 数列ゲーム

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君と青木君は長さ N の数列 S を用いたゲームを行う。

ゲームは高橋君の手番と青木君の手番 1 回ずつからなる。

ゲームは以下の要領で行われる。

最初に高橋君が数列の要素のうち 1 つに丸をつける。
次に青木君が数列の要素で高橋君が丸を付けなかったもののうち 1 つに丸をつける。
高橋君と青木君が丸を付けた 2 つの要素に対して、その 2 つの要素およびそれらの間にあるすべての要素を残して、それ以外の要素をすべて削除する。残った数列を T と置く。
数列 T のうち、数列 T 内で左から奇数番目の要素の合計が高橋君の得点、偶数番目の要素の合計が青木君の得点となる。

青木君は、丸を付けられる要素の中で、青木君が得点を最も多く得られる要素に丸を付ける。そのような要素が複数あるならばそれらのうち最も左側にある要素に丸を付ける。

高橋君は青木君の丸の付け方を知っている。高橋君が得られる得点として考えられる得点の最大値を求めよ。

入力

入力は以下の形式で標準入力から与えられる。

N
a_1 a_2 ... a_N

1 行目には、整数 N (2≦N≦50) が与えられる。N は数列 S の要素数である。
2 行目には、N 個の整数 a_1, a_2, ... , a_N (-50≦a_i≦50, 1≦i≦N) が与えられる。整数 a_i は数列 S の左から i 番目の要素を表す。

出力

高橋君が得られる得点の最大値を 1 行に出力せよ。

出力の末尾にも改行を入れること。

入力例1

6
1 -3 3 9 1 6

出力例1

高橋君は左から 2 番目の要素を選ぶのが最適である。この場合、青木君は左から 5 番目の要素を選ぶことになり、得られる数列 T は左から順に -3, 3, 9, 1 となる。高橋君は 6 の得点を、青木君は 4 の得点を得ることができる。

入力例2

3
5 5 5

出力例2

青木君にとってどの要素を選んでも得られる得点が 5 であることには変わりがないが、得られる得点が最大となる選び方が複数ある場合にその中で最も左を選ぶので、高橋君の得点は 10 になりうる。

入力例3

8
-1 10 -1 2 -1 10 -1 0

出力例3

-1

D - 語呂合わせ

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

日本には数字と短い文字列を対応させる語呂合わせの文化がある。

このことに興味を持った高橋君は、1 以上 K 以下の数字のみからなる正整数 v_1, v_2, ... , v_N とそれぞれの正整数に対応する文字列 w_1, w_2, ... , w_N の組 (v_1, w_1), (v_2, w_2), ... , (v_N, w_N) から、どの数字がどの文字列に対応しているかを推論することにした。

すなわち、以下の条件を満たす K 個の文字列 s_1, s_2, ... , s_K を求めたい。

1≦i≦K を満たす任意の整数 i に対して、1≦|s_i|≦3 を満たす。
1≦i≦N を満たす任意の整数 i に対して、整数 v_i を桁ごとに分解した際に得られる数字が上から順に d_1, d_2, ... , d_l としたとき、文字列 s_{d_1}, s_{d_2}, ... , s_{d_l} をこの順に連結した文字列が w_i に等しい。

K 個の文字列 s_1, s_2, ... , s_K を出力するプログラムを作成せよ。

入力

入力は以下の形式で標準入力から与えられる。

K N
v_1 w_1
v_2 w_2
:
v_N w_N

1 行目には、整数 K (1≦K≦9) と N (1≦N≦50) が空白区切りで与えられる。
2 行目から N 行には、数字と文字列の組に関する情報が与えられる。N 行のうち i (1≦i≦N) 行目には 1 以上 K 以下の数字のみからなる整数 v_i (1≦v_i≦10^9) と半角小文字英字のみからなる文字列 w_i (1≦|w_i|≦27) が空白区切りで与えられる。
1 以上 K 以下のどの数字も v_1, v_2, ... , v_N のうち 1 つ以上に登場する。
与えられる入力では、条件を満たす K 個の文字列 s_1, s_2, ... , s_K は必ず存在する。

部分点

この問題には部分点が設定されている。

K ≦ 3 かつ w_1 から w_N までのどの文字列も a, b, c のいずれかのみで構成されているデータセット 1 に正解した場合は、40 点が与えられる。
追加制約のないデータセット 2 に正解した場合は、上記とは別に 60 点が与えられる。

出力

出力は K 行からなる。K 行のうち i (1≦i≦K) 行目には文字列 s_i を出力せよ。

条件を満たす K 個の文字列の組み合わせが複数存在する場合は、それらの組み合わせのうちどの 1 つを出力してもよい。

出力の末尾にも改行を入れること。

入力例1

6 4
356 migoro
461 yoroi
2 ni
12 ini

出力例1

i
ni
mi
yo
go
ro

この入力例では、s_1 = i, s_2 = ni, s_3 = mi, s_4 = yo, s_5 = go, s_6 = ro と置くことによって題意を満たす K 個の文字列とすることができる。実際に、

v_1 = 356 を桁ごとに分解した場合に 3, 5, 6 が得られ、s_3 = mi, s_5 = go, s_6 = ro をこの順に連結した文字列 migoro は w_1 に等しい。
v_2 = 461 を桁ごとに分解した場合に 4, 6, 1 が得られ、s_4 = yo, s_6 = ro, s_1 = i をこの順に連結した文字列 yoroi は w_2 に等しい。
v_3 = 2 を桁ごとに分解した場合に 2 が得られ、s_2 = ni は w_3 に等しい。
v_4 = 12 を桁ごとに分解した場合に 1, 2 が得られ、s_1 = i, s_2 = ni をこの順に連結した文字列 ini は w_4 に等しい。

なお、この入力例はデータセット 1 の条件を満たさないことに注意せよ。

入力例2

3 4
21 aaa
12 aaa
123 aaaaaa
13 aaaa

出力例2

a
aa
aaa

入力例3

2 3
12211 abcaaaaabcabc
2121 aaabcaaabc
222221 aaaaaaaaaaabc

出力例3

abc
aa

入力例4

2 1
12 abcab

出力例4

ab
cab