A - AtCoder Quiz 3

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

AtCoder で定期的に開催されている、国際的な権威があるコンテストである AtCoder Grand Contest (以下、AGC) は今までに 54 回開催されてきました。

みなさんがちょうど参加している 230 回目の ABC である ABC230 と同様に、 当初は N 回目の AGC のコンテスト名には N を 3 桁になるようにゼロ埋めした数が割り振られていました。( 1 回目の AGC は AGC001, 2 回目の AGC は AGC002, ...)

ところが、最新の 54 回目の AGC のコンテスト名は AGC055 で、回数より 1 大きい数が割り振られています。これは、AGC042 が社会情勢の影響で中止されて欠番となったため、42 回目以降に開催されたコンテストでは開催された回数より 1 大きい数が割り振られているからです。(入出力例にある説明も参考にしてください。)

さて、ここで問題です。整数 N が与えられるので、N 回目に開催された AGC のコンテスト名を AGCXXX の形式で出力してください。ここで、XXX にはゼロ埋めがなされた 3 桁の数が入ります。

制約

  • 1 \leq N \leq 54
  • N は整数である。

入力

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

N

出力

N 回目に開催された AGC のコンテスト名を所定の形式で出力せよ。

入力例 1

42

出力例 1

AGC043

問題文にある通り、 42 回目以降の AGC には回数より 1 大きい数が割り振られています。
よって 42 回目の AGC のコンテスト名は AGC043 になります。

入力例 2

19

出力例 2

AGC019

41 回目以前の AGC は回数と同じ数が割り振られています。
よって AGC019 が答えとなります。

入力例 3

1

出力例 3

AGC001

問題文にある通り、 1 回目の AGC のコンテスト名は AGC001 です。
数が 3 桁になるようにゼロ埋めを行う必要があるのに注意してください。

入力例 4

50

出力例 4

AGC051

Score : 100 points

Problem Statement

AtCoder Grand Contest (AGC), a regularly held contest with a world authority, has been held 54 times.

Just like the 230-th ABC ― the one you are in now ― is called ABC230, the N-th AGC is initially named with a zero-padded 3-digit number N. (The 1-st AGC is AGC001, the 2-nd AGC is AGC002, ...)

However, the latest 54-th AGC is called AGC055, where the number is one greater than 54. Because AGC042 is canceled and missing due to the social situation, the 42-th and subsequent contests are assigned numbers that are one greater than the numbers of contests held. (See also the explanations at Sample Inputs and Outputs.)

Here is the problem: given an integer N, print the name of the N-th AGC in the format AGCXXX, where XXX is the zero-padded 3-digit number.

Constraints

  • 1 \leq N \leq 54
  • N is an integer.

Input

Input is given from Standard Input in the following format:

N

Output

Print the name of the N-th AGC in the specified format.

Sample Input 1

42

Sample Output 1

AGC043

As explained in Problem Statement, the 42-th and subsequent AGCs are assigned numbers that are one greater than the numbers of contests.
Thus, the 42-th AGC is named AGC043.

Sample Input 2

19

Sample Output 2

AGC019

The 41-th and preceding AGCs are assigned numbers that are equal to the numbers of contests.
Thus, the answer is AGC019.

Sample Input 3

1

Sample Output 3

AGC001

As mentioned in Problem Statement, the 1-st AGC is named AGC001.
Be sure to pad the number with zeros into a 3-digit number.

Sample Input 4

50

Sample Output 4

AGC051
B - flip

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

0 と 1 の 2 種類の文字からなる文字列 s が与えられます。 s に含まれる 0 を 1 に、1 を 0 に置き換えた文字列を出力してください。

制約

  • s の長さは 1 以上 10 以下
  • s は 0 と 1 の 2 種類の文字からなる

入力

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

s

出力

答えを 1 行で出力せよ。

入力例 1

01

出力例 1

10

s の 1 文字目は 1 なので、1 文字目に出力すべき文字は 0 です。 s の 2 文字目は 0 なので、2 文字目に出力すべき文字は 1 です。

入力例 2

1011

出力例 2

0100

入力例 3

100100001

出力例 3

011011110

Score : 100 points

Problem Statement

You are given a string s consisting of two kinds of characters, 0 and 1. Print the string obtained by replacing 0 with 1 and 1 with 0 in s.

Constraints

  • The length of s is between 1 and 10, inclusive.
  • s consists of two kinds of characters, 0 and 1.

Input

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

s

Output

Print the answer in a single line.

Sample Input 1

01

Sample Output 1

10

The 1-st character of s is 1, so the 1-st character to print is 0. The 2-nd character of s is 0, so the 2-nd character to print is 1.

Sample Input 2

1011

Sample Output 2

0100

Sample Input 3

100100001

Sample Output 3

011011110
C - How many?

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

a+b+c \leq S かつ a \times b \times c \leq T を満たす非負整数の組 (a,b,c) はいくつありますか？

制約

  • 0 \leq S \leq 100
  • 0 \leq T \leq 10000
  • S, T は整数である。

入力

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

S T

出力

条件を満たす非負整数の組 (a,b,c) の個数を出力せよ。

入力例 1

1 0

出力例 1

4

条件を満たす非負整数の組 (a,b,c) は (0,0,0), (0,0,1), (0,1,0), (1,0,0) の 4 つです。

入力例 2

2 5

出力例 2

10

入力例 3

10 10

出力例 3

213

入力例 4

30 100

出力例 4

2471

Score : 200 points

Problem Statement

How many triples of non-negative integers (a, b, c) satisfy a+b+c \leq S and a \times b \times c \leq T?

Constraints

  • 0 \leq S \leq 100
  • 0 \leq T \leq 10000
  • S and T are integers.

Input

Input is given from Standard Input in the following format:

S T

Output

Print the number of triples of non-negative integers (a,b,c) satisfying the conditions.

Sample Input 1

1 0

Sample Output 1

4

The triples (a,b,c) satisfying the conditions are (0,0,0), (0,0,1), (0,1,0), and (1,0,0) ― there are four of them.

Sample Input 2

2 5

Sample Output 2

10

Sample Input 3

10 10

Sample Output 3

213

Sample Input 4

30 100

Sample Output 4

2471
D - 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
E - Adjacent Swaps

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

N 個のボールが左右一列に並んでいます。初め、左から i \, (1 \leq i \leq N) 番目のボールには整数 i が書かれています。

高橋君は Q 回の操作を行いました。 i \, (1 \leq i \leq Q) 回目に行われた操作は次のようなものです。

  • 整数 x_i が書かれているボールをその右隣のボールと入れ替える。ただし、整数 x_i が書かれているボールが元々右端にあった場合、代わりに左隣のボールと入れ替える。

操作後において左から i \, (1 \leq i \leq N) 番目のボールに書かれている整数を a_i とします。 a_1,\ldots,a_N を求めてください。

制約

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

入力

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

N Q
x_1
\vdots
x_Q

出力

a_1,\ldots,a_N を空白区切りで出力せよ。

入力例 1

5 5
1
2
3
4
5

出力例 1

1 2 3 5 4

操作は以下のように行われます。

  • 1 と書かれたボールを右隣のボールと入れ替える。ボールに書かれた整数は左から 2,1,3,4,5 となる。
  • 2 と書かれたボールを右隣のボールと入れ替える。ボールに書かれた整数は左から 1,2,3,4,5 となる。
  • 3 と書かれたボールを右隣のボールと入れ替える。ボールに書かれた整数は左から 1,2,4,3,5 となる。
  • 4 と書かれたボールを右隣のボールと入れ替える。ボールに書かれた整数は左から 1,2,3,4,5 となる。
  • 5 と書かれたボールは右端にあるので左隣のボールと入れ替える。ボールに書かれた整数は左から 1,2,3,5,4 となる。

入力例 2

7 7
7
7
7
7
7
7
7

出力例 2

1 2 3 4 5 7 6

入力例 3

10 6
1
5
2
9
6
6

出力例 3

1 2 3 4 5 7 6 8 10 9

Score : 300 points

Problem Statement

N balls are lined up in a row from left to right. Initially, the i-th (1 \leq i \leq N) ball from the left has an integer i written on it.

Takahashi has performed Q operations. The i-th (1 \leq i \leq Q) operation was as follows.

  • Swap the ball with the integer x_i written on it with the next ball to the right. If the ball with the integer x_i written on it was originally the rightmost ball, swap it with the next ball to the left instead.

Let a_i be the integer written on the i-th (1 \leq i \leq N) ball after the operations. Find a_1,\ldots,a_N.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq x_i \leq N
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
x_1
\vdots
x_Q

Output

Print a_1,\ldots,a_N, with spaces in between.

Sample Input 1

5 5
1
2
3
4
5

Sample Output 1

1 2 3 5 4

The operations are performed as follows.

  • Swap the ball with 1 written on it with the next ball to the right. Now, the balls have integers 2,1,3,4,5 written on them, from left to right.
  • Swap the ball with 2 written on it with the next ball to the right. Now, the balls have integers 1,2,3,4,5 written on them, from left to right.
  • Swap the ball with 3 written on it with the next ball to the right. Now, the balls have integers 1,2,4,3,5 written on them, from left to right.
  • Swap the ball with 4 written on it with the next ball to the right. Now, the balls have integers 1,2,3,4,5 written on them, from left to right.
  • Swap the ball with 5 written on it with the next ball to the left, since it is the rightmost ball. Now, the balls have integers 1,2,3,5,4 written on them, from left to right.

Sample Input 2

7 7
7
7
7
7
7
7
7

Sample Output 2

1 2 3 4 5 7 6

Sample Input 3

10 6
1
5
2
9
6
6

Sample Output 3

1 2 3 4 5 7 6 8 10 9