A - 暗証番号

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

あなたはゲーム開発メンバーの一員です。 現在、あなたはプレイヤーがゲームをプレイするために必要な暗証番号を決めさせる部分を実装しています。

この暗証番号は 4 桁 であり、それぞれの桁は 0 以上 9 以下の数字のいずれかです。暗証番号が 0 で始まる可能性もあります。

安全上の関係で、 4 桁とも同じ数字である暗証番号は認めないことにしました。プレイヤーが入力した 4 桁の数 N が与えられるので、 これが 4 桁とも全て同じ数字であるかどうかを判定してください。

入力

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

N
  • 1 行目には、N が与えられる。N は 4 文字の 0 から 9 の数字からなる。
  • N が 0 で始まることもある。

出力

N が 4 桁とも全て同じ数字であるなら SAME を、そうでないなら DIFFERENT を 1 行に出力せよ。

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

入力例 1

2222

出力例 1

SAME

4 桁とも同じ数です。

入力例 2

1221

出力例 2

DIFFERENT

4 桁とも同じ数ではありません。

入力例 3

0000

出力例 3

SAME

N が 0 から始まることもあります。

B - 町の合併

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

N 個の町が合併し、1 つの新しい市になることになりました。合併前の i (1 ≦ i ≦ N) 番目の町は名称が S_i で、人口が P_i 人です。 新しい市の名称を、以下のように決めようとしています。

  • N 個の町の人口の合計の過半数以上の人口を有する町が存在するならば、新しい市の名称はその町の名称を引き継ぐことにする。
  • そのような町が存在しないならば、新しい市の名称は atcoder とする。

それぞれの町の名称と人口が与えられるので、合併後の新しい市の名称を出力してください。

入力

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

N
S_1 P_1
S_2 P_2
:
S_N P_N
  • 1 行目には、整数 N (2 ≦ N ≦ 1,000) が与えられる。
  • 2 行目から N 行では、それぞれの町の情報が与えられる。このうち i 行目には、英小文字のみからなる長さ 1 以上 20 以下の文字列 S_i と 整数 P_i (1 ≦ P_i ≦ 100,000) が空白区切りで与えられる。
  • S_1, S_2, …, S_N は全て異なる。

出力

合併後の新しい市の名称を 1 行に出力せよ。

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

入力例 1

4
unagi 20
usagi 13
snuke 42
smeke 7

出力例 1

snuke

4 つの町の合計人口は 20 + 13 + 42 + 7 = 82 人です。3 番目の町はこの過半数以上の人口を有しています。

入力例 2

5
a 10
b 20
c 30
d 40
e 100

出力例 2

atcoder

5 つの町の合計人口は 10 + 20 + 30 + 40 + 100 = 200 人ですが、この過半数以上の人口を有する町は存在しないので、 atcoder という市名になります。 なお、 5 番目の町は合計人口のちょうど半数の人口を有していますが、過半数ではないことに注意してください。

入力例 3

14
yasuzuka 3340
uragawara 4032
oshima 2249
maki 2614
kakizaki 11484
ogata 10401
kubiki 9746
yoshikawa 5142
joetsu 100000
nakago 4733
itakura 7517
kiyosato 3152
sanwa 6190
nadachi 3169

出力例 3

joetsu
C - 数式の書き換え

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

次のような制約を満たす数式 S が与えられます。

  • 演算子は + (加算) と * (乗算) のみからなる。乗算を優先して計算する。
  • 括弧は存在しない。
  • それぞれの項は、 1 桁の整数である。

例えば、1+3*4*0 、 1+2+3+4+5 などの数式はこの条件を満たしますが、12+3+5、4*6*7-3、(3+4)*5+2 のような数式は 条件を満たさないため、入力として与えられません。

あなたは、この数式のうち数字の部分をいくつか選んで 0 に書き換えることで、この式の値を 0 にしたいです。式の値を 0 にするために 0 に書き換えなければならない数字の個数の最小値を求めてください。

入力

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

S
  • 1 行目には、問題文の条件を満たす数式 S (S の長さは 1 以上 100,000 以下)が与えられる。

出力

0 に書き換えなければならない数字の個数の最小値を 1 行に出力せよ。

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

入力例 1

0+0+2*0

出力例 1

0

すでに与えられた数式は、 0 + 0 + 2 * 0 = 0 であるので、数字を書き換える必要はありません。

入力例 2

3*1+1*2

出力例 2

2

たとえば、入力の 1 文字目と 5 文字目を 0 に書き換えることで、 0 * 1 + 0 * 2 = 0 となり、値が 0 になります。

入力例 3

3*1*4+0+2*0+5*2+9*8*6+1+3

出力例 3

5
D - 三角形の分類

Time Limit: 7 sec / Memory Limit: 256 MB

問題文

2 次元平面上の N 個の点が与えられます。 i 番目の点の座標は (x_i, y_i) です。ただし、このうちのどの 3 点も同一直線上にありません。

N 点のうち 3 点を選ぶことによってこの 3 点を頂点とした三角形を作ることを考えます。三角形は全部で N * (N - 1) * (N - 2) / 6 個できます。 これらの三角形のうち、鋭角三角形の個数、直角三角形の個数、鈍角三角形の個数を求めてください。

ただし、鋭角三角形とは、3 つの角が全て 90° より小さい三角形で、直角三角形とは、ある 1 つの角が 90° である三角形で、 鈍角三角形とは、ある 1 つの角が 90° より大きい三角形のことをいいます。

入力

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

N
x_1 y_1
x_2 y_2
:
x_N y_N
  • 1 行目には、点の個数を表す整数 N (3 ≦ N ≦ 2,000) が与えられる。
  • 2 行目から N 行には、点の座標に関する情報が与えられる。このうち i 行目には、整数 x_i (-10,000 ≦ x_i ≦ 10,000)、 y_i (-10,000 ≦ y_i ≦ 10,000) が空白区切りで与えられる。
  • N 個の点は全て異なる。
  • N 個の点のうち、異なる 3 点が同一直線上にあることはない。

部分点

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

  • N ≦ 100 を満たすデータセットに正解した場合、部分点として 30 点が与えられる。

出力

鋭角三角形の個数、直角三角形の個数、鈍角三角形の個数をこの順に空白区切りで 1 行に出力せよ。

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

入力例 1

5
1 3
2 2
3 2
4 1
4 3

出力例 1

1 2 7
  • 2 番目の点、4 番目の点、5 番目の点を選ぶと、鋭角三角形ができます。
  • 1 番目の点、4 番目の点、5 番目の点を選ぶと、直角三角形ができます。
  • 3 番目の点、4 番目の点、5 番目の点を選ぶと、直角三角形ができます。
  • その他の 7 通りの選び方では、全て鈍角三角形ができます。

入力例 2

9
2 0
1 1
3 1
1 2
5 2
0 3
4 3
2 4
4 4

出力例 2

27 14 43