実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
高橋君は AtCoder Land を目指しています。 目の前に看板が置かれているので、ここが AtCoder Land であるかどうか判定したいです。
文字列 S,T が空白区切りで与えられます。
S= AtCoder かつ T= Land であるかどうか判定してください。
制約
- S,T は英大小文字からなる長さ 1 以上 10 以下の文字列
入力
入力は以下の形式で標準入力から与えられる。
S T
出力
S= AtCoder かつ T= Land であるならば Yes を、そうでないならば No を出力せよ。
入力例 1
AtCoder Land
出力例 1
Yes
S= AtCoder かつ T= Land です。
入力例 2
CodeQUEEN Land
出力例 2
No
S= AtCoder ではありません。
入力例 3
aTcodeR lANd
出力例 3
No
大文字と小文字は区別します。
Score : 100 points
Problem Statement
Takahashi is heading to AtCoder Land. There is a signboard in front of him, and he wants to determine whether it says AtCoder Land.
You are given two strings S and T separated by a space.
Determine whether S= AtCoder and T= Land.
Constraints
- S and T are strings consisting of uppercase and lowercase English letters, with lengths between 1 and 10, inclusive.
Input
The input is given from Standard Input in the following format:
S T
Output
If S= AtCoder and T= Land, print Yes; otherwise, print No.
Sample Input 1
AtCoder Land
Sample Output 1
Yes
S= AtCoder and T= Land.
Sample Input 2
CodeQUEEN Land
Sample Output 2
No
S is not AtCoder.
Sample Input 3
aTcodeR lANd
Sample Output 3
No
Uppercase and lowercase letters are distinguished.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
ある星では 1 年が D 日あり、7 日ごとにコンテストが開催されています。コンテストが日をまたいで開催されることはありません。
ある年の最初のコンテストは 1 年のうち F 日目に開催されました。その次の年の最初のコンテストは 1 年のうち何日目に開催されますか？
なお、この問題の制約のもとでは、次の年にコンテストが 1 回以上開催されることが保証されます。
制約
- 10 \leq D \leq 366
- 1 \leq F \leq 7
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
D F
出力
答えを出力せよ。
入力例 1
365 4
出力例 1
3
ある年の最初のコンテストの開催が 1 年のうち 4 日目だったとき、次の年の最初のコンテストの開催は 1 年のうち 3 日目になります。
入力例 2
10 5
出力例 2
2
Score : 100 points
Problem Statement
On a certain planet, a year has D days, and contests are held every 7 days. Contests never span across days.
The first contest of a certain year was held on the F-th day of the year. On what day of the next year will the first contest of the next year be held?
The constraints of this problem guarantee that at least one contest will be held in the next year.
Constraints
- 10 \leq D \leq 366
- 1 \leq F \leq 7
- All input values are integers.
Input
The input is given from Standard Input in the following format:
D F
Output
Print the integer N such that the next contest is held on the N-th day of the year.
Sample Input 1
365 4
Sample Output 1
3
If the first contest of a certain year was held on the 4th day of the year, the first contest of the next year will be held on the 3rd day of the year.
Sample Input 2
10 5
Sample Output 2
2
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
チェス盤のどこにコマが置かれているか答えてください。
縦 8 マス、横 8 マスのグリッドがあります。グリッドの各マスには、次のルールで定められる長さ 2 の文字列の名前がついています。
- 左から 1 列目にあるマスの名前の 1 文字目は
aである。同様に、左から 2,3,\ldots,8 列目にあるマスの名前の 1 文字目はb,c,d,e,f,g,hである。 - 下から 1 行目にあるマスの名前の 2 文字目は
1である。同様に、下から 2,3,\ldots,8 行目にあるマスの名前の 2 文字目は2,3,4,5,6,7,8である。
例えば、グリッドの左下のマスの名前は a1、右下のマスの名前は h1、右上のマスの名前は h8 です。
グリッドの状態を表す長さ 8 の 8 つの文字列 S_1,\ldots,S_8 が与えられます。
S_i の j 文字目は、グリッドの上から i 行目 左から j 列目のマスにコマが置かれているとき *、置かれていないとき . であり、S_1,\ldots,S_8 の中に文字 * はちょうど 1 つ存在します。
コマが置かれているマスの名前を求めてください。
制約
- S_i は
.および*のみからなる長さ 8 の文字列である - S_1,\ldots,S_8 の中に文字
*はちょうど 1 つ存在する。
入力
入力は以下の形式で標準入力から与えられる。
S_1 S_2 S_3 S_4 S_5 S_6 S_7 S_8
出力
答えを出力せよ。
入力例 1
........ ........ ........ ........ ........ ........ ........ *.......
出力例 1
a1
問題文中で説明したとおり、グリッドの左下のマスの名前は a1 です。
入力例 2
........ ........ ........ ........ ........ .*...... ........ ........
出力例 2
b3
Score : 200 points
Problem Statement
Locate a piece on a chessboard.
We have a grid with 8 rows and 8 columns of squares. Each of the squares has a 2-character name determined as follows.
- The first character of the name of a square in the 1-st column from the left is
a. Similarly, the first character of the name of a square in the 2-nd, 3-rd, \ldots, 8-th column from the left isb,c,d,e,f,g,h, respectively. - The second character of the name of a square in the 1-st row from the bottom is
1. Similarly, the second character of the name of a square in the 2-nd, 3-rd, \ldots, 8-th row from the bottom is2,3,4,5,6,7,8, respectively.
For instance, the bottom-left square is named a1, the bottom-right square is named h1, and the top-right square is named h8.
You are given 8 strings S_1,\ldots,S_8, each of length 8, representing the state of the grid.
The j-th character of S_i is * if the square at the i-th row from the top and j-th column from the left has a piece on it, and . otherwise.
The character * occurs exactly once among S_1,\ldots,S_8.
Find the name of the square that has a piece on it.
Constraints
- S_i is a string of length 8 consisting of
.and*. - The character
*occurs exactly once among S_1,\ldots,S_8.
Input
The input is given from Standard Input in the following format:
S_1 S_2 S_3 S_4 S_5 S_6 S_7 S_8
Output
Print the answer.
Sample Input 1
........ ........ ........ ........ ........ ........ ........ *.......
Sample Output 1
a1
As explained in the problem statement, the bottom-left square is named a1.
Sample Input 2
........ ........ ........ ........ ........ .*...... ........ ........
Sample Output 2
b3
実行時間制限: 2 sec / メモリ制限: 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 isD.)
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................... ............................................................
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 350 点
問題文
長さ N の文字列 S が与えられます。クエリが Q 個与えられるので、順番に処理してください。
i 番目のクエリは以下の通りです。
- 整数 X_i と文字 C_i が与えられるので、 S の X_i 番目の文字を C_i に置き換える。その後、 S に文字列
ABCが部分文字列として何箇所含まれるかを出力する。
ここで、 S の 部分文字列 とは、S の先頭から 0 文字以上、末尾から 0 文字以上削除して得られる文字列のことをいいます。
例えば、ab は abc の部分文字列ですが、ac は abc の部分文字列ではありません。
制約
- 3\le N\le 2\times 10^5
- 1\le Q\le 2\times 10^5
- S は英大文字からなる長さ N の文字列
- 1\le X_i\le N
- C_i は英大文字
入力
入力は以下の形式で標準入力から与えられる。
N Q S X_1 C_1 X_2 C_2 \vdots X_Q C_Q
出力
Q 行出力せよ。 i 行目 (1\le i\le Q) には i 番目のクエリに対する答えを出力せよ。
入力例 1
7 4 ABCDABC 4 B 3 A 5 C 4 G
出力例 1
2 1 1 0
各クエリを処理した後の S は次のようになります。
- 1 つ目のクエリを処理後： S=
ABCBABCとなる。この中にABCは部分文字列として 2 回登場する。 - 2 つ目のクエリを処理後： S=
ABABABCとなる。この中にABCは部分文字列として 1 回登場する。 - 3 つ目のクエリを処理後： S=
ABABCBCとなる。この中にABCは部分文字列として 1 回登場する。 - 4 つ目のクエリを処理後： S=
ABAGCBCとなる。この中にABCは部分文字列として 0 回登場する。
入力例 2
3 3 ABC 1 A 2 B 3 C
出力例 2
1 1 1
クエリの処理前と処理後で S が変わらない場合もあります。
入力例 3
15 10 BBCCBCACCBACACA 9 C 11 B 5 B 11 B 4 A 8 C 8 B 5 B 7 B 14 B
出力例 3
0 0 0 0 1 1 2 2 1 1
Score : 350 points
Problem Statement
You are given a string S of length N. You are also given Q queries, which you should process in order.
The i-th query is as follows:
- Given an integer X_i and a character C_i, replace the X_i-th character of S with C_i. Then, print the number of times the string
ABCappears as a substring in S.
Here, a substring of S is a string obtained by deleting zero or more characters from the beginning and zero or more characters from the end of S.
For example, ab is a substring of abc, but ac is not a substring of abc.
Constraints
- 3 \le N \le 2 \times 10^5
- 1 \le Q \le 2 \times 10^5
- S is a string of length N consisting of uppercase English letters.
- 1 \le X_i \le N
- C_i is an uppercase English letter.
Input
The input is given from Standard Input in the following format:
N Q S X_1 C_1 X_2 C_2 \vdots X_Q C_Q
Output
Print Q lines. The i-th line (1 \le i \le Q) should contain the answer to the i-th query.
Sample Input 1
7 4 ABCDABC 4 B 3 A 5 C 4 G
Sample Output 1
2 1 1 0
After processing each query, S becomes as follows.
- After the first query: S=
ABCBABC. In this string,ABCappears twice as a substring. - After the second query: S=
ABABABC. In this string,ABCappears once as a substring. - After the third query: S=
ABABCBC. In this string,ABCappears once as a substring. - After the fourth query: S=
ABAGCBC. In this string,ABCappears zero times as a substring.
Sample Input 2
3 3 ABC 1 A 2 B 3 C
Sample Output 2
1 1 1
There are cases where S does not change through processing a query.
Sample Input 3
15 10 BBCCBCACCBACACA 9 C 11 B 5 B 11 B 4 A 8 C 8 B 5 B 7 B 14 B
Sample Output 3
0 0 0 0 1 1 2 2 1 1