A - Capitalized?

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

英大文字・英小文字からなる空でない文字列 S が与えられます。以下の条件が満たされているか判定してください。

  • S の先頭の文字は大文字であり、それ以外の文字はすべて小文字である。

制約

  • 1 \leq |S| \leq 100（|S| は文字列 S の長さ）
  • S の各文字は英大文字または英小文字である。

入力

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

S

出力

条件が満たされていれば Yes、そうでなければ No を出力せよ。

入力例 1

Capitalized

出力例 1

Yes

Capitalized の先頭の文字 C は大文字であり、それ以外の文字 apitalized はすべて小文字であるため、Yes を出力します。

入力例 2

AtCoder

出力例 2

No

AtCoder は先頭以外にも大文字 C を含むため、No を出力します。

入力例 3

yes

出力例 3

No

yes の先頭の文字 y は大文字でないため、No を出力します。

入力例 4

A

出力例 4

Yes

Score: 100 points

Problem Statement

You are given a non-empty string S consisting of uppercase and lowercase English letters. Determine whether the following condition is satisfied:

  • The first character of S is uppercase, and all other characters are lowercase.

Constraints

  • 1 \leq |S| \leq 100 (|S| is the length of the string S.)
  • Each character of S is an uppercase or lowercase English letter.

Input

The input is given from Standard Input in the following format:

S

Output

If the condition is satisfied, print Yes; otherwise, print No.

Sample Input 1

Capitalized

Sample Output 1

Yes

The first character C of Capitalized is uppercase, and all other characters apitalized are lowercase, so you should print Yes.

Sample Input 2

AtCoder

Sample Output 2

No

AtCoder contains an uppercase letter C that is not at the beginning, so you should print No.

Sample Input 3

yes

Sample Output 3

No

The first character y of yes is not uppercase, so you should print No.

Sample Input 4

A

Sample Output 4

Yes
B - Tires

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

末尾が er または ist であるような文字列 S が与えられます。
S の末尾が er である場合は er を、 ist である場合は ist を出力してください。

制約

  • 2 \le |S| \le 20
  • S は英小文字のみからなる。
  • S の末尾は er または ist である。

入力

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

S

出力

答えを出力せよ。

入力例 1

atcoder

出力例 1

er

S="atcoder" の末尾は er です。

入力例 2

tourist

出力例 2

ist

入力例 3

er

出力例 3

er

Score : 100 points

Problem Statement

You are given a string S ending with er or ist.
If S ends with er, print er; if it ends with ist, print ist.

Constraints

  • 2 \le |S| \le 20
  • S consists of lowercase English letters.
  • S ends with er or ist.

Input

Input is given from Standard Input in the following format:

S

Output

Print the answer.

Sample Input 1

atcoder

Sample Output 1

er

S="atcoder" ends with er.

Sample Input 2

tourist

Sample Output 2

ist

Sample Input 3

er

Sample Output 3

er
C - Triangle (Easier)

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

N 頂点 M 辺の単純無向グラフが与えられます。頂点には 1, \dots, N の番号が付けられており、i \, (1 \leq i \leq M) 番目の辺は頂点 U_i と頂点 V_i を結んでいます。

以下の条件を全て満たす整数 a, b, c の組の総数を求めてください。

  • 1 \leq a \lt b \lt c \leq N
  • 頂点 a と頂点 b を結ぶ辺が存在する。
  • 頂点 b と頂点 c を結ぶ辺が存在する。
  • 頂点 c と頂点 a を結ぶ辺が存在する。

制約

  • 3 \leq N \leq 100
  • 1 \leq M \leq \frac{N(N - 1)}{2}
  • 1 \leq U_i \lt V_i \leq N \, (1 \leq i \leq M)
  • (U_i, V_i) \neq (U_j, V_j) \, (i \neq j)
  • 入力は全て整数

入力

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

N M
U_1 V_1
\vdots
U_M V_M

出力

答えを出力せよ。

入力例 1

5 6
1 5
4 5
2 3
1 4
3 5
2 5

出力例 1

2

(a, b, c) = (1, 4, 5), (2, 3, 5) が条件を満たします。

入力例 2

3 1
1 2

出力例 2

0

入力例 3

7 10
1 7
5 7
2 5
3 6
4 7
1 5
2 4
1 3
1 6
2 7

出力例 3

4

Score : 200 points

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The vertices are numbered 1, \dots, N, and the i-th (1 \leq i \leq M) edge connects Vertex U_i and Vertex V_i.

Find the number of tuples of integers a, b, c that satisfy all of the following conditions:

  • 1 \leq a \lt b \lt c \leq N
  • There is an edge connecting Vertex a and Vertex b.
  • There is an edge connecting Vertex b and Vertex c.
  • There is an edge connecting Vertex c and Vertex a.

Constraints

  • 3 \leq N \leq 100
  • 1 \leq M \leq \frac{N(N - 1)}{2}
  • 1 \leq U_i \lt V_i \leq N \, (1 \leq i \leq M)
  • (U_i, V_i) \neq (U_j, V_j) \, (i \neq j)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
U_1 V_1
\vdots
U_M V_M

Output

Print the answer.

Sample Input 1

5 6
1 5
4 5
2 3
1 4
3 5
2 5

Sample Output 1

2

(a, b, c) = (1, 4, 5), (2, 3, 5) satisfy the conditions.

Sample Input 2

3 1
1 2

Sample Output 2

0

Sample Input 3

7 10
1 7
5 7
2 5
3 6
4 7
1 5
2 4
1 3
1 6
2 7

Sample Output 3

4
D - Mex

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

長さ N の整数からなる数列 A=(A_1,\ldots,A_N) が与えられます。

A_1,\ldots,A_N に含まれない最小の非負整数を求めてください。

制約

  • 1 \leq N \leq 2000
  • 0 \leq A_i \leq 2000
  • 入力は全て整数である

入力

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

N
A_1 \ldots A_N

出力

答えを出力せよ。

入力例 1

8
0 3 2 6 2 1 0 0

出力例 1

4

非負整数は 0,1,2,3,4,\ldots と続きます。
0,1,2,3 は A に含まれ、4 は A に含まれないので、答えは 4 です。

入力例 2

3
2000 2000 2000

出力例 2

0

Score : 200 points

Problem Statement

You are given a sequence of length N consisting of integers: A=(A_1,\ldots,A_N).

Find the smallest non-negative integer not in (A_1,\ldots,A_N).

Constraints

  • 1 \leq N \leq 2000
  • 0 \leq A_i \leq 2000
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 \ldots A_N

Output

Print the answer.

Sample Input 1

8
0 3 2 6 2 1 0 0

Sample Output 1

4

The non-negative integers are 0,1,2,3,4,\ldots.
We have 0,1,2,3 in A, but not 4, so the answer is 4.

Sample Input 2

3
2000 2000 2000

Sample Output 2

0
E - Approximate Equalization 2

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

整数列 A=(A_1,A_2,\dots,A_N) があります。 あなたは次の操作を好きな回数（0 回でもよい）行うことができます。

  • 1\leq i,j \leq N を満たす整数 i,j を選ぶ。A_i を 1 減らし、A_j を 1 増やす。

A の最小値と最大値の差を 1 以下にするために必要な最小の操作回数を求めてください。

制約

  • 1\leq N \leq 2\times 10^5
  • 1\leq A_i \leq 10^9
  • 入力は全て整数

入力

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

N
A_1 A_2 \dots A_N

出力

答えを整数として出力せよ。

入力例 1

4
4 7 3 7

出力例 1

3

以下のように 3 回の操作を行うことで、A の最小値と最大値の差を 1 以下にすることができます。

  • i=2,j=3 として操作を行う。A=(4,6,4,7) になる。
  • i=4,j=1 として操作を行う。A=(5,6,4,6) になる。
  • i=4,j=3 として操作を行う。A=(5,6,5,5) になる。

3 回未満の操作で A の最小値と最大値の差を 1 以下にすることはできません。よって答えは 3 です。

入力例 2

1
313

出力例 2

0

入力例 3

10
999999997 999999999 4 3 2 4 999999990 8 999999991 999999993

出力例 3

2499999974

Score : 400 points

Problem Statement

You are given an integer sequence A=(A_1,A_2,\dots,A_N). You can perform the following operation any number of times (possibly zero).

  • Choose integers i and j with 1\leq i,j \leq N. Decrease A_i by one and increase A_j by one.

Find the minimum number of operations required to make the difference between the minimum and maximum values of A at most one.

Constraints

  • 1\leq N \leq 2\times 10^5
  • 1\leq A_i \leq 10^9
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N

Output

Print the answer as an integer.

Sample Input 1

4
4 7 3 7

Sample Output 1

3

By the following three operations, the difference between the minimum and maximum values of A becomes at most one.

  • Choose i=2 and j=3 to make A=(4,6,4,7).
  • Choose i=4 and j=1 to make A=(5,6,4,6).
  • Choose i=4 and j=3 to make A=(5,6,5,5).

You cannot make the difference between maximum and minimum values of A at most one by less than three operations, so the answer is 3.

Sample Input 2

1
313

Sample Output 2

0

Sample Input 3

10
999999997 999999999 4 3 2 4 999999990 8 999999991 999999993

Sample Output 3

2499999974