AtCoder Beginner Contest 023

A - 加算王

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

今回は 23 回目の AtCoder Beginner Contest です。今回のコンテストは 5 月に開かれています。

高橋君は 23 という整数を見て、十の位と一の位に分割して足し合わせることによって、2 + 3 = 5 と現在の月と等しい数となることに気が付きました。

このことに興味を持った高橋君は、手元にあった 2 桁の正整数 X の各位の和を計算することにしました。

あなたの課題は、正整数 X の各位の和を求めることです。

入力

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

1 行目には、2 桁の正整数 X (10 ≦ X ≦ 99) が与えられる。

出力

正整数 X の各位の和を 1 行に出力せよ。出力の末尾にも改行を入れること。

入力例1

出力例1

問題文の説明の通り、2 + 3 = 5 となります。

入力例2

出力例2

一の位が 0 となることもあります。

入力例3

出力例3

B - 手芸王

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君は趣味でアクセサリーを作っている。

アクセサリーは a, b, c のいずれか 1 文字が書かれたブロックを横 1 列に並べることで作成できる。

高橋君は、以下の手順でアクセサリーの作成を行う：

手順 0 : 高橋君は b 1 文字からなるアクセサリーを作成する。

以降の手順では、既にあるアクセサリーの両端にブロックを 1 つずつ追加することでアクセサリーを改造する。

手順 3n + 1 (n ≧ 0) : 手順 3n で完成したアクセサリーの左端に文字 a が書かれたブロックを、右端に文字 c が書かれたブロックを付け足す。
手順 3n + 2 (n ≧ 0) : 手順 3n+1 で完成したアクセサリーの左端に文字 c が書かれたブロックを、右端に文字 a が書かれたブロックを付け足す。
手順 3n (n ≧ 1) : 手順 3n-1 で完成したアクセサリーの左端に文字 b が書かれたブロックを、右端に文字 b が書かれたブロックを付け足す。

高橋君はアクセサリーの作成を好きな手順の直後に終了することができる。終了した場合、アクセサリーには、アクセサリーを構成するブロックに書かれた文字を左から右に読んだものと同じ名前が付けられる。

例えば、手順 0, 1, 2, 3 それぞれの直後にアクセサリーの作成を終了した場合、アクセサリーの名前は順に、b, abc, cabca, bcabcab となる。

文字列 S が与えられるので、その文字列がアクセサリーの名前として考えられるかを判定し、考えられるなら何番目の手順の直後にアクセサリーの作成を終了したのかを求めよ。

入力

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

N
S

1 行目には、文字列 S の長さを表す整数 N (1 ≦ N ≦ 100) が与えられる。
2 行目には、半角の小文字アルファベットのみからなる文字列 S が与えられる。

出力

文字列 S が手順 K の直後にアクセサリーの作成を終了したときのアクセサリーの名前と等しいような整数 K が存在する場合は整数 K を、いつアクセサリーの作成を終了してもアクセサリーの名前が S とならないときは -1 を 1 行に出力せよ。出力の末尾にも改行を入れること。

入力例1

3
abc

出力例1

手順 1 の直後にアクセサリーの作成を終了したときのアクセサリーの名前は abc となる。

入力例2

6
abcabc

出力例2

-1

文字列 abcabc はアクセサリーの名前として考えられない。

入力例3

7
atcoder

出力例3

-1

文字列 S には a, b, c 以外の文字が入ることがある。

入力例4

19
bcabcabcabcabcabcab

出力例4

C - 収集王

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君はある部屋に移動する予定です。

部屋は正方形のマスが縦に R 行、横に C 列並んだ形状をしています。このうち i (1 ≦ i ≦ R) 行目の j (1 ≦ j ≦ C) 列目にあるマスをマス (i,j) と呼ぶことにします。

これらのマスには飴が合計 N 個存在します。飴には 1 から N までの番号が付けられており、飴 i (1 ≦ i ≦ N) はマス (r_i,c_i) に置いてあります。これらのうちどの 2 つの飴も同一のマス上にありません。

高橋君はマスのうち任意の 1 マスに移動します。移動した後、高橋君は次に示すように飴を獲得します。

最初に、高橋君がいるマスと同じ行にあるすべてのマスについて、そのマスにある飴をすべて獲得する。
次に、高橋君がいるマスと同じ列にあるすべてのマスについて、そのマスにあるすべての飴を獲得する。

高橋君はこの行動以外には何も行動しません。

高橋君は獲得する飴の個数がちょうど K 個になるようにしたいです。このような移動先として考えられるマスの総数を求めてください。

入力

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

R C K
N
r_1 c_1
r_2 c_2
:
r_N c_N

1 行目には、3 つの整数 R (1 ≦ R ≦ 100,000), C (1 ≦ C ≦ 100,000), K (1 ≦ K ≦ 100,000) が空白区切りで書かれている。これは、部屋を構成する正方形マスが縦 R 行、横 C 列あることを表す。K は高橋君が獲得したい飴の個数である。
2 行目には、飴の個数を表す整数 N (K ≦ N ≦ 100,000) が与えられる。
3 行目から N 行には、飴に関する情報が与えられる。N 行のうち i (1 ≦ i ≦ N) 行目には、2 つの整数 r_i (1 ≦ r_i ≦ R), c_i (1 ≦ c_i ≦ C) が空白区切りで書かれている。これは飴 i がマス (r_i,c_i) にあることを表す。
i≠j のとき、(r_i,c_i)≠(r_j,c_j) となる。

部分点

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

R ≦ 50 かつ C ≦ 50 かつ N ≦ 50 を満たすデータセット 1 に正解した場合は、30 点が与えられる。
追加制約のないデータセット 2 に正解した場合は、上記とは別に 70 点が与えられる。

出力

獲得する飴の個数がちょうど K 個になるような移動先の総数を 1 行に出力せよ。出力の末尾にも改行を入れること。

入力例1

出力例1

例えば、マス (3,2) に高橋君が移動した場合を考えます。

飴 1 は、マス (1,2) にあります。このマスはマス (3,2) と同じ列にあるので、高橋君は飴 1 を獲得します。
飴 2 は、マス (2,1) にあります。このマスはマス (3,2) と同じ行にも同じ列にもないので、高橋君は飴 2 を獲得しません。
飴 3 は、マス (2,5) にあります。このマスはマス (3,2) と同じ行にも同じ列にもないので、高橋君は飴 3 を獲得しません。
飴 4 は、マス (3,2) にあります。このマスはマス (3,2) と同じマス (同じ行かつ同じ列) にあるので、高橋君は飴 4 を獲得します。
飴 5 は、マス (3,5) にあります。このマスはマス (3,2) と同じ行にあるので、高橋君は飴 5 を獲得します。

以上より、飴 1, 4, 5 のちょうど 3 個だけ飴を獲得するので、マス (3,2) は獲得する飴の個数がちょうど K 個になるような移動先です。

他にもマス (1,5), (2,5), (3,1), (3,5) が条件をみたすので答えとして 5 を出力します。

入力例2

出力例2

どのように移動先を指定しても、獲得する飴の個数をちょうど 1 個にすることはできません。

入力例3

出力例3

D - 射撃王

Time Limit: 5 sec / Memory Limit: 256 MB

問題文

高橋君は最近、射撃にハマっている。

高橋君は N 個の風船すべてを射撃で割り、得られる得点をできるだけ小さくする競技に参加している。

風船には 1 から N までの番号が付けられていて、風船 i (1 ≦ i ≦ N) は競技開始時に高度 H_i のところにあり、1 秒経過するにつれて高度が S_i だけ増加する。

高橋君は競技開始時に 1 個風船を割ることができ、そこから 1 秒ごとに 1 個の風船を割ることができる。どの順番で風船を割るのかは高橋君が自由に決定できる。

どの風船についても、その風船を割ることによるペナルティが発生する。ペナルティはその風船が割られたときの高度と等しい整数値となる。高橋君が最終的に得る得点は N 個の風船のペナルティのうちの最大値となる。

高橋君が得ることのできる得点として考えられる最小値を求めよ。

入力

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

N
H_1 S_1
H_2 S_2
:
H_N S_N

1 行目には、風船の個数を表す整数 N (1 ≦ N ≦ 100,000) が書かれている。
2 行目から N 行には、風船に関する情報が与えられる。N 行のうち i (1 ≦ i ≦ N) 行目には、2 つの整数 H_i (1 ≦ H_i ≦ 1,000,000,000), S_i (1 ≦ S_i ≦ 1,000,000,000) が空白区切りで与えられる。これは、風船 i が競技開始時に高度 H_i にあり、1 秒経過するにつれて高度が S_i ずつ上昇していくことを表す。

部分点

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

N ≦ 50 かつ H_i ≦ 100,000 かつ S_i ≦ 2,000 を満たすデータセット 1 に正解した場合は、30 点が与えられる。
追加制約のないデータセット 2 に正解した場合は、上記とは別に 70 点が与えられる。

出力

高橋君が得ることのできる得点として考えられる最小値を 1 行に出力せよ。出力の末尾にも改行を入れること。

入力例1

出力例1

例えば、以下に示す順番で風船を割ります。

競技開始直後に風船 3 を割ります。風船 3 のペナルティは 14 + 7 × 0 = 14 です。
競技開始から 1 秒後に風船 4 を割ります。風船 4 のペナルティは 21 + 2 × 1 = 23 です。
競技開始から 2 秒後に風船 2 を割ります。風船 2 のペナルティは 12 + 4 × 2 = 20 です。
競技開始から 3 秒後に風船 1 を割ります。風船 1 のペナルティは 5 + 6 × 3 = 23 です。

以上より高橋君の得点は 23 となり、これが最小値となります。

入力例2