A - Buy a Pen

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

高橋君はペンを買うためにお店にやって来ました。お店では赤色のペンが一本 R 円、緑色のペンが一本 G 円、青色のペンが一本 B 円で売られています。

高橋君は色 C が嫌いです。C が Red のときは赤色のペンを、Green のときは緑色のペンを、Blue のときは青色のペンを買うことができません。

高橋君がペンを一本買うために必要な金額の最小値を求めてください。

制約

  • 1\leq R,G,B\leq 100
  • R,G,B は整数
  • C は Red,Green,Blue のいずれか

入力

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

R G B
C

出力

高橋君がペンを一本買うために必要な金額の最小値が X 円であるとき、X を出力せよ。

入力例 1

20 30 10
Blue

出力例 1

20

赤色のペンは 20 円で、緑色のペンは 30 円で、青色のペンは 10 円で売られています。高橋君は青色のペンを買うことができないので、20 円で赤色のペンを一本買うことができます。

入力例 2

100 100 100
Red

出力例 2

100

入力例 3

37 39 93
Blue

出力例 3

37

Score : 100 points

Problem Statement

Takahashi came to a store to buy a pen. Here, a red pen costs R yen, a green pen costs G yen, and a blue pen costs B yen.

Takahashi dislikes the color C. If C is Red, he cannot buy a red pen; if C is Green, he cannot buy a green pen; and if C is Blue, he cannot buy a blue pen.

Determine the minimum amount of money he needs to buy one pen.

Constraints

  • 1\leq R,G,B\leq 100
  • R, G, and B are integers.
  • C is Red, Green, or Blue.

Input

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

R G B
C

Output

If the minimum amount of money Takahashi needs to buy one pen is X yen, print X.

Sample Input 1

20 30 10
Blue

Sample Output 1

20

A red pen costs 20 yen, a green pen costs 30 yen, and a blue pen costs 10 yen. Takahashi cannot buy a blue pen, but he can buy a red pen for 20 yen.

Sample Input 2

100 100 100
Red

Sample Output 2

100

Sample Input 3

37 39 93
Blue

Sample Output 3

37
B - CAPS LOCK

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

英小文字のみからなる文字列 S が与えられます。

S の各文字を英大文字に変換して得られる文字列 T を出力してください。

制約

  • S は英小文字のみからなる、長さが 1 以上 100 以下の文字列

入力

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

S

出力

T を出力せよ。

入力例 1

abc

出力例 1

ABC

abc の各文字を英大文字に変換すると ABC になります。

入力例 2

a

出力例 2

A

入力例 3

abcdefghjiklnmoqprstvuwxyz

出力例 3

ABCDEFGHJIKLNMOQPRSTVUWXYZ

Score : 100 points

Problem Statement

You are given a string S consisting of lowercase English letters.

Uppercase each character of S and print the resulting string T.

Constraints

  • S is a string consisting of lowercase English letters whose length is between 1 and 100, inclusive.

Input

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

S

Output

Print T.

Sample Input 1

abc

Sample Output 1

ABC

Uppercase each character of abc, and you have ABC.

Sample Input 2

a

Sample Output 2

A

Sample Input 3

abcdefghjiklnmoqprstvuwxyz

Sample Output 3

ABCDEFGHJIKLNMOQPRSTVUWXYZ
C - ASCII Art

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

0 以上 26 以下の整数からなる H 行 W 列の行列 A が与えられます。A の上から i 行目、左から j 列目の要素は A_{i,j} です。

H 個の長さ W の文字列 S_1, S_2, \dots, S_H を次の条件を満たすように定めます。

  • S_i の j 文字目は、 A_{i,j} が 0 ならばピリオド (.)、そうでなければ A_{i,j} 番目の大文字アルファベットである。

S_1, S_2, \dots, S_H を順に出力してください。

制約

  • 1 \leq H \leq 100
  • 1 \leq W \leq 100
  • 0 \leq A_{i,j} \leq 26
  • 入力される値はすべて整数

入力

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

H W
A_{1,1} A_{1,2} \dots A_{1,W}
A_{2,1} A_{2,2} \dots A_{2,W}
\vdots
A_{H,1} A_{H,2} \dots A_{H,W}

出力

H 行出力せよ。i 行目には S_i を出力せよ。

入力例 1

2 3
0 1 2
0 0 3

出力例 1

.AB
..C

S_1 = .AB、S_2 = ..C です。この 2 つを順に出力します。

入力例 2

3 3
24 0 0
0 25 0
0 0 26

出力例 2

X..
.Y.
..Z

入力例 3

3 1
2
9
4

出力例 3

B
I
D

入力例 4

24 60
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 13 14 0 0 0 10 0 0 0 0 0 15 24 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 23 7 25 24 13 10 0 10 12 0 0 0 0 19 9 23 0 0 0 0 10 10 14 0 0 0 10 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 13 5 0 0 23 11 14 14 0 0 12 9 1 21 19 0 0 9 12 10 25 3 10 6 0 0 9 13 23 24 14 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 14 6 0 0 0 10 5 25 13 0 0 25 0 0 0 0 0 0 0 0 0 0 10 16 0 0 13 21 13 13 14 23 14 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 13 8 2 0 0 0 0 0 13 11 13 19 0 0 1 2 5 9 12 12 5 9 9 20 6 0 14 14 14 9 0 0 0 14 14 18 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 23 13 13 13 13 13 13 14 14 14 13 14 14 13 7 0 0 0 0 0 0 0 0 0 0 0 0 13 13 13 2 0 0 0 0 13 11 13 16 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 13 1 0 0 0 9 20 9 20 20 20 20 13 20 20 13 20 23 8 8 8 20 8 20 7 8 17 7 10 13 14 13 19 0 0 0 0 0 22 14 25 13 16 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 13 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 20 20 13 13 7 20 26 13 8 6 14 0 0 0 0 0 0 0 0 0
0 0 0 0 0 5 0 0 0 0 0 0 0 1 2 20 20 23 13 2 7 2 10 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 20 23 13 0 0 0 0 0 0 0 0 0
0 0 0 0 13 0 0 0 0 0 0 0 0 1 0 0 0 13 12 9 14 13 13 9 9 20 12 0 0 0 0 0 0 0 0 0 0 0 1 9 9 9 9 12 0 0 0 0 0 0 0 20 0 0 0 0 0 0 0 0
0 0 0 2 0 0 0 0 0 0 0 0 0 0 19 0 0 14 13 14 14 13 13 0 0 9 5 16 0 0 0 0 0 0 5 20 20 13 2 2 20 9 13 14 14 20 12 12 0 0 0 0 9 13 0 0 0 0 0 0
0 0 1 9 0 0 0 0 0 0 0 0 0 0 0 13 10 13 13 13 13 2 5 12 10 5 0 0 0 0 0 0 0 0 20 16 0 0 0 13 14 13 13 13 13 0 0 10 8 0 0 0 0 0 20 7 0 0 0 0
0 0 4 2 0 0 0 0 0 0 0 0 0 0 0 0 9 7 14 10 10 14 13 5 0 0 0 0 0 0 0 0 0 0 0 23 13 12 13 13 13 13 13 9 13 0 14 4 0 0 0 0 0 0 0 9 16 0 0 0
0 0 22 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 13 13 13 2 9 14 2 20 14 0 0 0 0 0 0 0 0 0 2 0 0 0
0 0 0 5 13 0 0 0 2 7 13 13 13 13 13 13 13 2 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 20 20 9 0 0 0 0 0 0 0 0 0 0 0 0 0 19 0 0 0
0 0 0 0 20 13 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 21 14 7 2 20 24 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 6 0 0 0
0 0 0 0 0 0 9 14 14 0 0 20 20 13 13 20 13 9 0 0 10 0 0 0 0 0 0 9 23 13 9 0 0 0 0 0 0 0 10 6 0 0 7 0 0 9 20 13 13 14 2 0 0 0 0 5 0 0 0 0
0 0 0 0 0 0 0 0 20 13 14 0 0 0 0 0 0 0 0 13 9 0 0 0 0 0 0 0 0 13 11 0 0 0 0 0 0 0 14 9 0 0 0 20 25 14 7 0 0 0 0 9 1 14 7 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 9 13 13 20 0 0 0 0 0 9 12 0 0 0 0 0 0 0 14 13 14 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 9 9 20 14 14 4 14 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 2 9 0 0 0 0 9 9 20 21 7 13 20 0 0 20 23 7 7 2 12 7 6 0 0 0 0 0 0 0 0 0 0 0 0 5 5 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 20 9 9 20 24 10 12 10 0 0 0 0 0 0 0 0 20 20 0 0 0 0 0 20 7 7 13 22 2 5 9 2 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 20 5 20 5 2 5 7 20 5 14 14 5 11 5 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

出力例 4

................................B...........................
...................MMN...J.....OXN..........................
.................MWGYXMJ.JL....SIW....JJN...JN..............
...............IME..WKNN..LIAUS..ILJYCJF..IMWXN.............
..............MNF...JEYM..Y..........JP..MUMMNWN............
.............MHB.....MKMS..ABEILLEIITF.NNNI...NNR...........
..........JWMMMMMMNNNMNNMG............MMMB....MKMP..........
........MA...ITITTTTMTTMTWHHHTHTGHQGJMNMS.....VNYMP.........
......MI...............................TTTMMGTZMHFN.........
.....E.......ABTTWMBGBJL.......................TTWM.........
....M........A...MLINMMIITL...........AIIIIL.......T........
...B..........S..NMNNMM..IEP......ETTMBBTIMNNTLL....IM......
..AI...........MJMMMMBELJE........TP...MNMMMM..JH.....TG....
..DB............IGNJJNME...........WMLMMMMMIM.ND.......IP...
..VM.................................TMMMBINBTN.........B...
...EM...BGMMMMMMMBI....................ITTI.............S...
....TML..................UNGBTX........................IF...
......INN..TTMMTMI..J......IWMI.......JF..G..ITMMNB....E....
........TMN........MI........MK.......NI...TYNG....IANG.....
..........IMMT.....IL.......NMN.......F........IITNNDN......
..............TBI....IITUGMT..TWGGBLGF............EE........
.................TTIITXJLJ........TT.....TGGMVBEIB..........
.........................ITETEBEGTENNEKEB...................
............................................................

Score : 200 points

Problem Statement

You are given an H-by-W matrix A consisting of integers between 0 and 26. The element at the i-th row from the top and j-th column from the left is A_{i,j}.

Let S_1, S_2, \dots, S_H be H strings of length W that satisfy the following.

  • The j-th character of S_i is a period (.) if A_{i,j} is 0, and the A_{i,j}-th uppercase English letter otherwise. (For instance, the 4-th letter is D.)

Print S_1, S_2, \dots, S_H in order.

Constraints

  • 1 \leq H \leq 100
  • 1 \leq W \leq 100
  • 0 \leq A_{i,j} \leq 26
  • All values in the input are integers.

Input

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

H W
A_{1,1} A_{1,2} \dots A_{1,W}
A_{2,1} A_{2,2} \dots A_{2,W}
\vdots
A_{H,1} A_{H,2} \dots A_{H,W}

Output

Print H lines. The i-th line should contain S_i.

Sample Input 1

2 3
0 1 2
0 0 3

Sample Output 1

.AB
..C

We have S_1 = .AB and S_2 = ..C. Print these in order.

Sample Input 2

3 3
24 0 0
0 25 0
0 0 26

Sample Output 2

X..
.Y.
..Z

Sample Input 3

3 1
2
9
4

Sample Output 3

B
I
D

Sample Input 4

24 60
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 13 14 0 0 0 10 0 0 0 0 0 15 24 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 23 7 25 24 13 10 0 10 12 0 0 0 0 19 9 23 0 0 0 0 10 10 14 0 0 0 10 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 13 5 0 0 23 11 14 14 0 0 12 9 1 21 19 0 0 9 12 10 25 3 10 6 0 0 9 13 23 24 14 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 14 6 0 0 0 10 5 25 13 0 0 25 0 0 0 0 0 0 0 0 0 0 10 16 0 0 13 21 13 13 14 23 14 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 13 8 2 0 0 0 0 0 13 11 13 19 0 0 1 2 5 9 12 12 5 9 9 20 6 0 14 14 14 9 0 0 0 14 14 18 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 10 23 13 13 13 13 13 13 14 14 14 13 14 14 13 7 0 0 0 0 0 0 0 0 0 0 0 0 13 13 13 2 0 0 0 0 13 11 13 16 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 13 1 0 0 0 9 20 9 20 20 20 20 13 20 20 13 20 23 8 8 8 20 8 20 7 8 17 7 10 13 14 13 19 0 0 0 0 0 22 14 25 13 16 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 13 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 20 20 13 13 7 20 26 13 8 6 14 0 0 0 0 0 0 0 0 0
0 0 0 0 0 5 0 0 0 0 0 0 0 1 2 20 20 23 13 2 7 2 10 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 20 23 13 0 0 0 0 0 0 0 0 0
0 0 0 0 13 0 0 0 0 0 0 0 0 1 0 0 0 13 12 9 14 13 13 9 9 20 12 0 0 0 0 0 0 0 0 0 0 0 1 9 9 9 9 12 0 0 0 0 0 0 0 20 0 0 0 0 0 0 0 0
0 0 0 2 0 0 0 0 0 0 0 0 0 0 19 0 0 14 13 14 14 13 13 0 0 9 5 16 0 0 0 0 0 0 5 20 20 13 2 2 20 9 13 14 14 20 12 12 0 0 0 0 9 13 0 0 0 0 0 0
0 0 1 9 0 0 0 0 0 0 0 0 0 0 0 13 10 13 13 13 13 2 5 12 10 5 0 0 0 0 0 0 0 0 20 16 0 0 0 13 14 13 13 13 13 0 0 10 8 0 0 0 0 0 20 7 0 0 0 0
0 0 4 2 0 0 0 0 0 0 0 0 0 0 0 0 9 7 14 10 10 14 13 5 0 0 0 0 0 0 0 0 0 0 0 23 13 12 13 13 13 13 13 9 13 0 14 4 0 0 0 0 0 0 0 9 16 0 0 0
0 0 22 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 13 13 13 2 9 14 2 20 14 0 0 0 0 0 0 0 0 0 2 0 0 0
0 0 0 5 13 0 0 0 2 7 13 13 13 13 13 13 13 2 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 20 20 9 0 0 0 0 0 0 0 0 0 0 0 0 0 19 0 0 0
0 0 0 0 20 13 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 21 14 7 2 20 24 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 6 0 0 0
0 0 0 0 0 0 9 14 14 0 0 20 20 13 13 20 13 9 0 0 10 0 0 0 0 0 0 9 23 13 9 0 0 0 0 0 0 0 10 6 0 0 7 0 0 9 20 13 13 14 2 0 0 0 0 5 0 0 0 0
0 0 0 0 0 0 0 0 20 13 14 0 0 0 0 0 0 0 0 13 9 0 0 0 0 0 0 0 0 13 11 0 0 0 0 0 0 0 14 9 0 0 0 20 25 14 7 0 0 0 0 9 1 14 7 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 9 13 13 20 0 0 0 0 0 9 12 0 0 0 0 0 0 0 14 13 14 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 9 9 20 14 14 4 14 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 2 9 0 0 0 0 9 9 20 21 7 13 20 0 0 20 23 7 7 2 12 7 6 0 0 0 0 0 0 0 0 0 0 0 0 5 5 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 20 9 9 20 24 10 12 10 0 0 0 0 0 0 0 0 20 20 0 0 0 0 0 20 7 7 13 22 2 5 9 2 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 20 5 20 5 2 5 7 20 5 14 14 5 11 5 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Sample Output 4

................................B...........................
...................MMN...J.....OXN..........................
.................MWGYXMJ.JL....SIW....JJN...JN..............
...............IME..WKNN..LIAUS..ILJYCJF..IMWXN.............
..............MNF...JEYM..Y..........JP..MUMMNWN............
.............MHB.....MKMS..ABEILLEIITF.NNNI...NNR...........
..........JWMMMMMMNNNMNNMG............MMMB....MKMP..........
........MA...ITITTTTMTTMTWHHHTHTGHQGJMNMS.....VNYMP.........
......MI...............................TTTMMGTZMHFN.........
.....E.......ABTTWMBGBJL.......................TTWM.........
....M........A...MLINMMIITL...........AIIIIL.......T........
...B..........S..NMNNMM..IEP......ETTMBBTIMNNTLL....IM......
..AI...........MJMMMMBELJE........TP...MNMMMM..JH.....TG....
..DB............IGNJJNME...........WMLMMMMMIM.ND.......IP...
..VM.................................TMMMBINBTN.........B...
...EM...BGMMMMMMMBI....................ITTI.............S...
....TML..................UNGBTX........................IF...
......INN..TTMMTMI..J......IWMI.......JF..G..ITMMNB....E....
........TMN........MI........MK.......NI...TYNG....IANG.....
..........IMMT.....IL.......NMN.......F........IITNNDN......
..............TBI....IITUGMT..TWGGBLGF............EE........
.................TTIITXJLJ........TT.....TGGMVBEIB..........
.........................ITETEBEGTENNEKEB...................
............................................................
D - Magic Square

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

3 以上の奇数 N が与えられます。

N 行 N 列のマス目があり、はじめどのマスも空白です。 今から、以下の手順に従ってこのマス目の各マスに整数を書き込みます。 なお、上から i+1 行目、左から j+1 列目 (0\leq i<N, 0\leq j<N) のマスを (i,j) と表記することとします。

  1. マス (0,\frac{N-1}{2}) に 1 を書き込む。
  2. 次の操作を N^2-1 回繰り返す。
    • 前回整数を書き込んだマスを (r,c)、書き込んだ整数を k としたとき、マス ((r-1) \bmod N, (c+1) \bmod N) が空白ならばそのマスに、そうでなければマス ((r+1) \bmod N,c) に k+1 を書き込む。 ここで、x \bmod N は x を N で割ったあまりを表す。

この手順においてそれぞれのマスに書き込まれる整数を求めてください。 なお、どのマスもちょうど 1 回だけ整数を書き込まれることが証明できます。

制約

  • 3\leq N \leq 99
  • N は奇数

入力

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

N

出力

マス (i,j) に書き込まれる整数を a_{i,j} として、以下の形式で出力せよ。

a_{0,0} a_{0,1} \dots a_{0,N-1}
\vdots
a_{N-1,0} a_{N-1,1} \dots a_{N-1,N-1}

入力例 1

3

出力例 1

8 1 6
3 5 7
4 9 2

以下のように各マスに整数が書き込まれていきます。

  1. マス (0,\frac{3-1}{2})=(0,1) に 1 を書き込む。
  2. マス ((0-1) \bmod 3, (1+1) \bmod 3)=(2,2) は空白なので、そこに 2 を書き込む。
  3. マス ((2-1) \bmod 3, (2+1) \bmod 3)=(1,0) は空白なので、そこに 3 を書き込む。
  4. マス ((1-1) \bmod 3, (0+1) \bmod 3)=(0,1) は空白ではないので、マス ((1+1) \bmod 3,0)=(2,0) に 4 を書き込む。
  5. \vdots

入力例 2

5

出力例 2

17 24 1 8 15
23 5 7 14 16
4 6 13 20 22
10 12 19 21 3
11 18 25 2 9

Score : 200 points

Problem Statement

You are given an odd number N that is at least 3.

There is a grid with N rows and N columns, where all cells are initially empty. Now, you will write integers in each cell of this grid according to the following procedure. Let (i,j) denote the cell at the (i+1)-th row from the top and (j+1)-th column from the left (0\leq i<N, 0\leq j<N).

  1. Write 1 in cell (0,\frac{N-1}{2}).
  2. Repeat the following operation N^2-1 times:
    • Let (r,c) be the cell where an integer was written last time, and k be the integer written. If cell ((r-1) \bmod N, (c+1) \bmod N) is empty, write k+1 in that cell; otherwise, write k+1 in cell ((r+1) \bmod N,c). Here, x \bmod N denotes the remainder when x is divided by N.

Find the integer that will be written in each cell in this procedure. It can be proved that each cell will have an integer written in it exactly once.

Constraints

  • 3\leq N \leq 99
  • N is an odd number.

Input

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

N

Output

Let a_{i,j} be the integer written in cell (i,j), and print it in the following format:

a_{0,0} a_{0,1} \dots a_{0,N-1}
\vdots
a_{N-1,0} a_{N-1,1} \dots a_{N-1,N-1}

Sample Input 1

3

Sample Output 1

8 1 6
3 5 7
4 9 2

Integers are written in each cell as follows:

  1. Write 1 in cell (0,\frac{3-1}{2})=(0,1).
  2. Cell ((0-1) \bmod 3, (1+1) \bmod 3)=(2,2) is empty, so write 2 there.
  3. Cell ((2-1) \bmod 3, (2+1) \bmod 3)=(1,0) is empty, so write 3 there.
  4. Cell ((1-1) \bmod 3, (0+1) \bmod 3)=(0,1) is not empty, so write 4 in cell ((1+1) \bmod 3,0)=(2,0).
  5. \vdots

Sample Input 2

5

Sample Output 2

17 24 1 8 15
23 5 7 14 16
4 6 13 20 22
10 12 19 21 3
11 18 25 2 9
E - Make it Simple

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

頂点に 1 から N の、辺に 1 から M の番号がついた N 頂点 M 辺の無向グラフが与えられます。辺 i は頂点 u_i と頂点 v_i を結ぶ辺です。
グラフから辺を取り除いてグラフを単純にするためには、少なくとも何本の辺を取り除く必要がありますか？
ここでグラフが単純であるとは、グラフが自己ループや多重辺を含まないことをいいます。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 5 \times 10^5
  • 1 \leq u_i \leq N
  • 1 \leq v_i \leq N
  • 入力される値は全て整数

入力

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

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

出力

グラフを単純にするために取り除く必要がある辺の本数の最小値を出力せよ。

入力例 1

3 5
1 2
2 3
3 2
3 1
1 1

出力例 1

2

辺 3 と辺 5 を取り除くとグラフを単純にすることが出来て、これが取り除く辺の本数が最小となる選び方の 1 つです。よって答えは 2 本です。

入力例 2

1 0

出力例 2

0

入力例 3

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

出力例 3

3

Score : 300 points

Problem Statement

You are given an undirected graph with N vertices and M edges, where the vertices are numbered 1 through N and the edges are numbered 1 through M. Edge i connects vertices u_i and v_i.
To make the graph simple by removing edges, what is the minimum number of edges that must be removed?
Here, a graph is called simple if and only if it does not contain self-loops or multi-edges.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 5 \times 10^5
  • 1 \leq u_i \leq N
  • 1 \leq v_i \leq N
  • All input values are integers.

Input

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

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

Output

Print the minimum number of edges that must be removed to make the graph simple.

Sample Input 1

3 5
1 2
2 3
3 2
3 1
1 1

Sample Output 1

2

By removing edges 3 and 5, the graph becomes simple. This is one of the ways to remove the minimum number of edges, so the answer is 2.

Sample Input 2

1 0

Sample Output 2

0

Sample Input 3

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

Sample Output 3

3
F - Ideal Holidays

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 350 点

問題文

AtCoder 王国の 1 週間は A+B 日からなり、1 日目から A 日目が休日で、A+1 日目から A+B 日目が平日です。

高橋くんは N 個の予定があり、i 番目の予定は今日から D_i 日後です。

高橋くんは今日が 1 週間の何日目かを忘れてしまいました。高橋くんの N 個の予定が全て休日である可能性があるかを判定してください。

制約

  • 1\leq N\leq 2\times 10^5
  • 1\leq A,B\leq 10^9
  • 1\leq D_1<D_2<\ldots<D_N\leq 10^9

入力

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

N A B
D_1 D_2 \ldots D_N

出力

高橋くんの N 個の予定が全て休日である可能性がある場合は Yes を、そうでない場合は No を一行に出力せよ。

入力例 1

3 2 5
1 2 9

出力例 1

Yes

入力では 1 週間は 7 日からなり、1 日目から 2 日目が休日、3 日目から 7 日目が平日です。

今日が 1 週間の 7 日目だとします。このとき、1 日後は 1 週間の 1 日目、2 日後は 1 週間の 2 日目、9 日後は 1 週間の 2 日目となり、全ての予定が休日となります。そのため、高橋くんの N 個の予定が全て休日である可能性があります。

入力例 2

2 5 10
10 15

出力例 2

No

入力例 3

4 347 347
347 700 705 710

出力例 3

Yes

Score: 350 points

Problem Statement

In the Kingdom of AtCoder, a week consists of A+B days, with the first through A-th days being holidays and the (A+1)-th through (A+B)-th being weekdays.

Takahashi has N plans, and the i-th plan is scheduled D_i days later.

He has forgotten what day of the week it is today. Determine if it is possible for all of his N plans to be scheduled on holidays.

Constraints

  • 1\leq N\leq 2\times 10^5
  • 1\leq A,B\leq 10^9
  • 1\leq D_1<D_2<\ldots<D_N\leq 10^9

Input

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

N A B
D_1 D_2 \ldots D_N

Output

Print Yes in a single line if it is possible for all of Takahashi's N plans to be scheduled on holidays, and No otherwise.

Sample Input 1

3 2 5
1 2 9

Sample Output 1

Yes

In this input, a week consists of seven days, with the first through second days being holidays and the third through seventh days being weekdays.

Let us assume today is the seventh day of the week. In this case, one day later would be the first day of the week, two days later would be the second day of the week, and nine days later would also be the second day of the week, making all plans scheduled on holidays. Therefore, it is possible for all of Takahashi's N plans to be scheduled on holidays.

Sample Input 2

2 5 10
10 15

Sample Output 2

No

Sample Input 3

4 347 347
347 700 705 710

Sample Output 3

Yes
G - Colorful Bracket Sequence

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

6 種類の文字、(, ), [, ], <, > からなる文字列 S が与えられます。

ここで、文字列 T は、以下の条件を満たすときカラフル括弧列と呼ばれます。

以下の操作を何回か（0 回でも良い）繰り返すことで、T を空文字列にできる。

  • T の（連続する）部分文字列であって、(), [], <> のいずれかであるようなものが存在するとき、そのうちの 1 つを選んで削除する。
  • 削除された部分文字列が T の先頭または末尾であるとき、残りの文字列を新たに T とする。
  • そうでないとき、削除された前後の文字列を 1 つに連結し、新たに T とする。

S がカラフル括弧列であるか判定してください。

制約

  • S は長さ 1 以上 2\times 10^5 以下の文字列
  • S は (, ), [, ], <, > のみからなる。

入力

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

S

出力

S がカラフル括弧列ならば Yes を、そうでないならば No を出力せよ。

入力例 1

([])<>()

出力例 1

Yes

S=([])<>() に対して、次のように操作を繰り返すことで空文字列にすることができます。

  • ([])<>() の 2 文字目から 3 文字目までをとった部分文字列 [] を削除し、前後を連結する。文字列は新たに ()<>() となる。
  • ()<>() の 1 文字目から 2 文字目までをとった部分文字列 () を削除する。文字列は新たに <>() となる。
  • <>() の 1 文字目から 2 文字目までをとった部分文字列 <> を削除する。文字列は新たに () となる。
  • () の 1 文字目から 2 文字目までをとった部分文字列 () を削除する。文字列は空文字列となる。

よって、S=([])<>() はカラフル括弧列であるため、Yes を出力します。

入力例 2

([<)]>

出力例 2

No

S=([<)]> は (), [], <> を部分列として含まないため、1 回目の操作を行うことができず、特に S はカラフル括弧列ではありません。よって、No を出力します。

入力例 3

())

出力例 3

No

S に対して操作を繰り返し、空文字列とすることはできません。
よって、S はカラフル括弧列ではないため、No を出力します。

Score : 400 points

Problem Statement

You are given a string S consisting of six types of characters: (, ), [, ], <, >.

A string T is called a colorful bracket sequence if it satisfies the following condition:

It is possible to turn T into an empty string by repeating the following operation any number of times (possibly zero):

  • If there exists a contiguous substring of T that is one of (), [], or <>, choose one such substring and delete it.
  • If the deleted substring was at the beginning or end of T, the remainder becomes the new T.
  • Otherwise, concatenate the part before the deleted substring and the part after the deleted substring, and that becomes the new T.

Determine whether S is a colorful bracket sequence.

Constraints

  • S is a string of length between 1 and 2\times 10^5, inclusive.
  • S consists of (, ), [, ], <, >.

Input

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

S

Output

If S is a colorful bracket sequence, print Yes; otherwise, print No.

Sample Input 1

([])<>()

Sample Output 1

Yes

For S=([])<>(), it is possible to turn it into an empty string by repeating the operation as follows:

  • Delete the substring [] from the 2nd to the 3rd character in ([])<>(), then concatenate the parts before and after it. The string becomes ()<>().
  • Delete the substring () from the 1st to the 2nd character in ()<>(). The string becomes <>().
  • Delete the substring <> from the 1st to the 2nd character in <>(). The string becomes ().
  • Delete the substring () from the 1st to the 2nd character in (). The string becomes empty.

Thus, S=([])<>() is a colorful bracket sequence, so print Yes.

Sample Input 2

([<)]>

Sample Output 2

No

Since S=([<)]> does not contain (), [], or <> as a contiguous substring, we cannot perform the 1st operation, and in particular S is not a colorful bracket sequence. Therefore, print No.

Sample Input 3

())

Sample Output 3

No

It is impossible to turn S into an empty string by repeating the operations.
Therefore, S is not a colorful bracket sequence, so print No.
H - Σ[k=0..10^100]floor(X／10^k)

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

\displaystyle \sum_{k=0}^{10^{100}} \left \lfloor \frac{X}{10^k} \right \rfloor を求めてください。

注釈

\lfloor A \rfloor は、 A の小数点以下を切り捨てた値を指します。

制約

  • X は整数
  • 1 \le X < 10^{500000}

入力

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

X

出力

答えを整数として出力せよ。
但し、たとえ答えが大きな整数であっても、求める答えを正確に整数として出力する必要がある。たとえば、 2.33e+21 のような指数表記や、 0523 のような先頭に不要な 0 を付けたような表記は許されない。

入力例 1

1225

出力例 1

1360

求める値は、 1225+122+12+1+0+0+\dots+0=1360 となります。

入力例 2

99999

出力例 2

111105

繰り上がりに注意してください。

入力例 3

314159265358979323846264338327950288419716939937510

出力例 3

349065850398865915384738153697722542688574377708317

入力される値も出力すべき値も非常に大きくなる場合があります。

Score : 500 points

Problem Statement

Find \displaystyle \sum_{k=0}^{10^{100}} \left \lfloor \frac{X}{10^k} \right \rfloor.

Notes

\lfloor A \rfloor denotes the value of A truncated to an integer.

Constraints

  • X is an integer.
  • 1 \le X < 10^{500000}

Input

Input is given from Standard Input in the following format:

X

Output

Print the answer as an integer.
Here, the answer must be precisely printed as an integer, even if it is large. It is not allowed to use exponential notation, such as 2.33e+21, or print unnecessary leading zeros, as in 0523.

Sample Input 1

1225

Sample Output 1

1360

The value we seek is 1225+122+12+1+0+0+\dots+0=1360.

Sample Input 2

99999

Sample Output 2

111105

Beware of carries.

Sample Input 3

314159265358979323846264338327950288419716939937510

Sample Output 3

349065850398865915384738153697722542688574377708317

The values in input and output can both be enormous.
I - Egoism

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 550 点

問題文

AtCoder 牧場では馬がみずから水浴びをします。後片づけをする馬もいれば、散らかしたままにする馬もいます。

N 頭の馬がおり、1 から N までの番号が付けられています。馬 i (1 \leq i \leq N) は機嫌 A_i と丁寧さ B_i をもちます(ここで、B_i は 1, 2 のいずれか)。

夜になると、N 頭の馬が 1 回ずつ水浴びをします。j 回目 (1 \leq j \leq N) に水浴びをする馬の番号を p_j とおくと、馬 p_j の満足度が以下で与えられます。

  • j \geq 2 の場合、馬 p_j の機嫌と馬 p_{j-1} の丁寧さの積。
  • j = 1 の場合、馬 p_j の機嫌。

これから Q 日にわたって毎日 1 つずつクエリが与えられるので、順に処理してください。k 日目 (1 \leq k \leq Q) のクエリは以下の通りです。

  • 馬 W_k の機嫌を X_k に、丁寧さを Y_k に変更する(ここで、Y_k は 1, 2 のいずれか)。その後、その夜に N 頭の馬が水浴びをする順番を任意に決められるとき、その夜の N 頭の水浴びの満足度の総和が最大でいくらになるかを求める。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^6 (1 \leq i \leq N)
  • B_i は 1,2 のいずれか (1 \leq i \leq N)
  • 1 \leq W_k \leq N (1 \leq k \leq Q)
  • 1 \leq X_k \leq 10^6 (1 \leq k \leq Q)
  • Y_k は 1,2 のいずれか (1 \leq k \leq Q)
  • 入力される値はすべて整数

入力

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

N Q
A_1 B_1
\vdots
A_N B_N
W_1 X_1 Y_1
\vdots
W_Q X_Q Y_Q

出力

Q 行出力せよ。k 行目 (1 \leq k \leq Q) には k 日目のクエリの答えを出力せよ。

入力例 1

4 4
1 2
10 1
3 1
7 2
2 7 1
1 3 1
2 2 1
3 1000000 2

出力例 1

32
27
18
2000015

1 日目のクエリにおいて、馬 3,1,4,2 の順に水浴びすることで、各馬の満足度は以下のようになります。

  • 馬 3 の満足度は 3
  • 馬 1 の満足度は 1 \times 1 = 1
  • 馬 4 の満足度は 7 \times 2 = 14
  • 馬 2 の満足度は 7 \times 2 = 14

このときの満足度の総和は 32 です。

2 日目のクエリにおいて、馬 4,2,1,3 の順に水浴びすることで、各馬の満足度は以下のようになります。

  • 馬 4 の満足度は 7
  • 馬 2 の満足度は 7 \times 2 = 14
  • 馬 1 の満足度は 3 \times 1 = 3
  • 馬 3 の満足度は 3 \times 1 = 3

このときの満足度の総和は 27 です。

3 日目のクエリにおいて、馬 4,3,2,1 の順に水浴びすることで、満足度の総和は 18 になります。

4 日目のクエリにおいて、馬 4,3,1,2 の順に水浴びすることで、満足度の総和は 2000015 になります。

入力例 2

10 10
340019 2
598908 1
177330 2
575439 2
916653 2
451275 2
762769 2
36625 2
273231 2
367619 2
8 334230 2
8 835378 1
4 777076 2
6 61501 1
4 516395 1
4 35678 2
5 751493 1
3 815798 1
2 369777 2
5 941470 2

出力例 2

9417616
10146681
10549955
9708906
8847525
8463663
7860112
8606740
8516097
9236070

Score : 550 points

Problem Statement

At AtCoder Ranch, horses bathe themselves. Some horses clean up afterward, while others leave a mess.

There are N horses, numbered 1 to N. Horse i (1 \leq i \leq N) has a mood A_i and a tidiness B_i (where B_i is 1 or 2).

At night, the N horses bathe once each. Let p_j be the number of the horse that bathes in the j-th turn (1 \leq j \leq N). The satisfaction of horse p_j is given as follows:

  • If j \geq 2, the product of the mood of horse p_j and the tidiness of horse p_{j-1}.
  • If j = 1, the mood of horse p_j.

You will be given Q queries, one for each day over Q days. Process them in order. The query for the k-th day (1 \leq k \leq Q) is as follows:

  • Change the mood of horse W_k to X_k and its tidiness to Y_k (where Y_k is 1 or 2). Then, find the maximum possible total satisfaction of the N horses' baths that night if you can decide the order in which the N horses bathe arbitrarily.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^6 (1 \leq i \leq N)
  • B_i is 1 or 2. (1 \leq i \leq N)
  • 1 \leq W_k \leq N (1 \leq k \leq Q)
  • 1 \leq X_k \leq 10^6 (1 \leq k \leq Q)
  • Y_k is 1 or 2. (1 \leq k \leq Q)
  • All input values are integers.

Input

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

N Q
A_1 B_1
\vdots
A_N B_N
W_1 X_1 Y_1
\vdots
W_Q X_Q Y_Q

Output

Output Q lines. The k-th line (1 \leq k \leq Q) should contain the answer to the query for the k-th day.

Sample Input 1

4 4
1 2
10 1
3 1
7 2
2 7 1
1 3 1
2 2 1
3 1000000 2

Sample Output 1

32
27
18
2000015

For the query on the first day, if the horses bathe in the order 3,1,4,2, the satisfaction of each horse is as follows:

  • Horse 3's satisfaction is 3
  • Horse 1's satisfaction is 1 \times 1 = 1
  • Horse 4's satisfaction is 7 \times 2 = 14
  • Horse 2's satisfaction is 7 \times 2 = 14

The total satisfaction in this case is 32.

For the query on the second day, if the horses bathe in the order 4,2,1,3, the satisfaction of each horse is as follows:

  • Horse 4's satisfaction is 7
  • Horse 2's satisfaction is 7 \times 2 = 14
  • Horse 1's satisfaction is 3 \times 1 = 3
  • Horse 3's satisfaction is 3 \times 1 = 3

The total satisfaction in this case is 27.

For the query on the third day, if the horses bathe in the order 4,3,2,1, the total satisfaction is 18.

For the query on the fourth day, if the horses bathe in the order 4,3,1,2, the total satisfaction is 2000015.

Sample Input 2

10 10
340019 2
598908 1
177330 2
575439 2
916653 2
451275 2
762769 2
36625 2
273231 2
367619 2
8 334230 2
8 835378 1
4 777076 2
6 61501 1
4 516395 1
4 35678 2
5 751493 1
3 815798 1
2 369777 2
5 941470 2

Sample Output 2

9417616
10146681
10549955
9708906
8847525
8463663
7860112
8606740
8516097
9236070