A - Past ABCs

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

長さ 6 の文字列 S が与えられます。S の先頭 3 文字は ABC であり、末尾 3 文字は数字であることが保証されます。

Sが、このコンテスト開始以前に AtCoder上で開催され終了したコンテストの略称であるかどうか判定してください。

ただし、文字列 T が「このコンテスト開始以前に AtCoder上で開催され終了したコンテストの略称」であるとは、以下の 348 個の文字列のうちいずれかに等しいことと定めます。

ABC001, ABC002, \ldots, ABC314, ABC315, ABC317, ABC318, \ldots, ABC348, ABC349

特に ABC316 が含まれないことに注意してください。

制約

  • S は先頭 3 文字が ABC、末尾 3 文字が数字である長さ 6 の文字列

入力

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

S

出力

Sが、このコンテスト開始以前に AtCoder上で開催され終了したコンテストの略称であるなら Yes、そうでないなら No と出力せよ。

入力例 1

ABC349

出力例 1

Yes

ABC349 は先週AtCoder上で開催され終了したコンテストの略称です。

入力例 2

ABC350

出力例 2

No

ABC350 はこのコンテストです。まだ終了していません。

入力例 3

ABC316

出力例 3

No

ABC316 はAtCoder上で開催されていません。

Score: 100 points

Problem Statement

You are given a string S of length 6. It is guaranteed that the first three characters of S are ABC and the last three characters are digits.

Determine if S is the abbreviation of a contest held and concluded on AtCoder before the start of this contest.

Here, a string T is "the abbreviation of a contest held and concluded on AtCoder before the start of this contest" if and only if it equals one of the following 348 strings:

ABC001, ABC002, \ldots, ABC314, ABC315, ABC317, ABC318, \ldots, ABC348, ABC349.

Note that ABC316 is not included.

Constraints

  • S is a string of length 6 where the first three characters are ABC and the last three characters are digits.

Input

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

S

Output

If S is the abbreviation of a contest held and concluded on AtCoder before the start of this contest, print Yes; otherwise, print No.

Sample Input 1

ABC349

Sample Output 1

Yes

ABC349 is the abbreviation of a contest held and concluded on AtCoder last week.

Sample Input 2

ABC350

Sample Output 2

No

ABC350 is this contest, which has not concluded yet.

Sample Input 3

ABC316

Sample Output 3

No

ABC316 was not held on AtCoder.
B - Is it rated?

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

現在 AtCoder で開催されている AtCoder Regular Contest (ARC) には、Div. 1 と Div. 2 の 2 種類が存在します。 ARC Div. 1 では レーティング が 1600 以上 2999 以下の人が、ARC Div. 2 ではレーティングが 1200 以上 2399 以下の人がそれぞれ Rated 対象 となります。

正整数 R, X が与えられます。

レーティングが R の人は ARC Div. X において Rated 対象ですか？

制約

  • 1\leq R \leq 4229
  • 1\leq X \leq 2
  • 入力は全て整数

入力

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

R X

出力

レーティングが R の人が ARC Div. X において Rated 対象ならば Yes を、そうでないならば No を出力せよ。

入力例 1

2000 1

出力例 1

Yes

2000 は 1600 以上 2999 以下であるため、レーティングが 2000 の人は ARC Div. 1 において Rated 対象です。

入力例 2

1000 1

出力例 2

No

1000 は 1600 未満であるため、レーティングが 1000 の人は ARC Div. 1 において Rated 対象ではありません。

入力例 3

1500 2

出力例 3

Yes

1500 は 1200 以上 2399 以下であるため、レーティングが 1500 の人は ARC Div. 2 において Rated 対象です。

入力例 4

2800 2

出力例 4

No

2800 は 2399 より大きいため、レーティングが 2800 の人は ARC Div. 2 において Rated 対象ではありません。

Score : 100 points

Problem Statement

AtCoder Regular Contest (ARC) currently has two divisions: Div. 1 and Div. 2. In ARC Div. 1, participants whose rating is between 1600 and 2999, inclusive, are rated. In ARC Div. 2, participants whose rating is between 1200 and 2399, inclusive, are rated.

You are given positive integers R and X.

Determine whether a person with rating R is rated in ARC Div. X.

Constraints

  • 1 \le R \le 4229
  • 1 \le X \le 2
  • All input values are integers.

Input

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

R X

Output

If a person with rating R is rated in ARC Div. X, output Yes; otherwise, output No.

Sample Input 1

2000 1

Sample Output 1

Yes

Because 2000 lies between 1600 and 2999, a person with rating 2000 is rated in ARC Div. 1.

Sample Input 2

1000 1

Sample Output 2

No

Because 1000 is less than 1600, a person with rating 1000 is not rated in ARC Div. 1.

Sample Input 3

1500 2

Sample Output 3

Yes

Because 1500 lies between 1200 and 2399, a person with rating 1500 is rated in ARC Div. 2.

Sample Input 4

2800 2

Sample Output 4

No

Because 2800 exceeds 2399, a person with rating 2800 is not rated in ARC Div. 2.
C - Pick Two

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

一直線状の倉庫があります。この倉庫に 偶数個 の荷物が保管されています。
倉庫の情報は文字列 S として与えらます。
倉庫は区画 1,2,\dots,|S| の |S| 個の区画からなり、 S の各文字は以下の情報を表します。

  • S の i 文字目が # であるとき、区画 i に荷物が 1 つ置かれている。
  • S の i 文字目が . であるとき、区画 i に荷物が置かれていない。

この倉庫にはロボットがあり、このロボットは以下の行動を倉庫から荷物が無くなるまで繰り返します。

  • 荷物をその荷物がある区画番号の小さい方から 2 つ回収する。回収された荷物は倉庫の外へ運び出される。

繰り返しの各回で運び出された 2 つの荷物が倉庫のどの区画にあったものかを求めてください。

制約

  • S は # と . からなる長さ 2 以上 1000 以下の文字列
  • 倉庫には偶数個の荷物が保管されている
  • 倉庫には 2 つ以上の荷物が保管されている

入力

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

S

出力

倉庫に保管されている荷物の総数を m とすると、 m/2 行出力せよ。
そのうち i 行目には、 i 回目の繰り返しで運び出された荷物が元々あった区画の番号を小さい方から順に カンマ区切り で出力せよ。

入力例 1

.#.##..##.#.###....#

出力例 1

2,4
5,8
9,11
13,14
15,20

区画 2,4,5,8,9,11,13,14,15,20 に荷物が保管されています。

  • 1 回目の繰り返しでは区画 2,4 にあった荷物が運び出されます。
  • 2 回目の繰り返しでは区画 5,8 にあった荷物が運び出されます。
  • 3 回目の繰り返しでは区画 9,11 にあった荷物が運び出されます。
  • 4 回目の繰り返しでは区画 13,14 にあった荷物が運び出されます。
  • 5 回目の繰り返しでは区画 15,20 にあった荷物が運び出されます。

Score : 200 points

Problem Statement

There is a linear warehouse, which stores an even number of packages.
The layout of the warehouse is represented by a string S.
The warehouse has |S| sections, numbered 1,2,\dots,|S|, and the string S describes them as follows:

  • When the i-th character of S is #, one package is placed in section i.
  • When the i-th character of S is ., no package is placed in section i.

The warehouse has a robot, which repeats the following action until there are no more packages in the warehouse:

  • Collect two packages from the sections with the smallest section numbers among the sections containing packages. The collected packages are carried out of the warehouse.

For each iteration, determine which sections of the warehouse the two packages that were carried out were originally located.

Constraints

  • S is a string consisting of # and . with length between 2 and 1000, inclusive.
  • The warehouse stores an even number of packages.
  • The warehouse stores at least two packages.

Input

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

S

Output

Let m be the total number of packages stored in the warehouse. Output m/2 lines.
The i-th line should contain the section numbers where the packages carried out in the i-th iteration were originally located, in ascending order, separated by a comma.

Sample Input 1

.#.##..##.#.###....#

Sample Output 1

2,4
5,8
9,11
13,14
15,20

Packages are stored in sections 2,4,5,8,9,11,13,14,15,20.

  • In the 1st iteration, packages from sections 2,4 are carried out.
  • In the 2nd iteration, packages from sections 5,8 are carried out.
  • In the 3rd iteration, packages from sections 9,11 are carried out.
  • In the 4th iteration, packages from sections 13,14 are carried out.
  • In the 5th iteration, packages from sections 15,20 are carried out.
D - Unauthorized

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

ある日、高橋くんはあるウェブサイトに対して N 回の操作を行いました。

i 回目 (1\leq i\leq N) の操作は文字列 S _ i で表され、次の 4 つのうちいずれかです。

  • S _ i= login である。高橋くんはログイン操作を行い、高橋くんがウェブサイトにログインした状態になる。
  • S _ i= logout である。高橋くんはログアウト操作を行い、高橋くんがウェブサイトにログインしていない状態になる。
  • S _ i= public である。高橋くんはウェブサイトの公開ページにアクセスする。
  • S _ i= private である。高橋くんはウェブサイトの非公開ページにアクセスする。

高橋くんがログインしていない状態で非公開ページにアクセスした時、またその時に限り、ウェブサイトは認証エラーを返します。

ログインした状態でさらにログイン操作をしたり、ログインしていない状態でさらにログアウト操作をしてもエラーにはなりません。 また、認証エラーが返されたあとも、高橋くんは操作を続けることができます。

はじめ、高橋くんはログインしていない状態です。

N 回の操作のうち、高橋くんが認証エラーを受け取った回数を出力してください。

制約

  • 1\leq N\leq100
  • N は整数
  • S _ i は login, logout, public, private のいずれか (1\leq i\leq N)

入力

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

N
S _ 1
S _ 2
\vdots
S _ N

出力

高橋くんが認証エラーを受け取った回数を出力せよ。

入力例 1

6
login
private
public
logout
private
public

出力例 1

1

高橋くんが行うそれぞれの操作の結果は以下のようになります。

  • 高橋くんがウェブサイトにログインした状態になる。
  • 高橋くんは非公開ページにアクセスする。高橋くんは現在ログインしているので、エラーは返されない。
  • 高橋くんは公開ページにアクセスする。
  • 高橋くんがウェブサイトにログインしていない状態になる。
  • 高橋くんは非公開ページにアクセスする。高橋くんは現在ログインしていないので、認証エラーが返される。
  • 高橋くんは公開ページにアクセスする。

高橋くんが認証エラーを受け取るのは 5 回目の操作のみなので、1 を出力してください。

入力例 2

4
private
private
private
logout

出力例 2

3

連続で非公開ページにアクセスしようとした場合、操作のたびに認証エラーを受け取ります。

ログインしていない状態からさらにログアウト操作をした場合には認証エラーは返されないことに注意してください。

入力例 3

20
private
login
private
logout
public
logout
logout
logout
logout
private
login
login
private
login
private
login
public
private
logout
private

出力例 3

3

Score : 200 points

Problem Statement

One day, Takahashi performed N operations on a certain web site.

The i‑th operation (1 \le i \le N) is represented by a string S_i, which is one of the following:

  • S _ i= login: He performs a login operation and becomes logged in to the site.
  • S _ i= logout: He performs a logout operation and becomes not logged in to the site.
  • S _ i= public: He accesses a public page of the site.
  • S _ i= private: He accesses a private page of the site.

The site returns an authentication error if and only if he accesses a private page while he is not logged in.

Logging in again while already logged in, or logging out again while already logged out, does not cause an error. Even after an authentication error is returned, he continues performing the remaining operations.

Initially, he is not logged in.

Print the number of operations among the N operations at which he receives an authentication error.

Constraints

  • 1 \le N \le 100
  • N is an integer.
  • Each S_i is one of login, logout, public, private. (1 \le i \le N)

Input

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

N
S_1
S_2
\vdots
S_N

Output

Print the number of times Takahashi receives an authentication error.

Sample Input 1

6
login
private
public
logout
private
public

Sample Output 1

1

The result of each operation is as follows:

  • Takahashi becomes logged in.
  • He accesses a private page. He is logged in, so no error is returned.
  • He accesses a public page.
  • He becomes logged out.
  • He accesses a private page. He is not logged in, so an authentication error is returned.
  • He accesses a public page.

An authentication error occurs only at the 5th operation, so print 1.

Sample Input 2

4
private
private
private
logout

Sample Output 2

3

If he tries to access private pages consecutively while not logged in, he receives an authentication error for each such operation.

Note that logging out again while already logged out does not cause an authentication error.

Sample Input 3

20
private
login
private
logout
public
logout
logout
logout
logout
private
login
login
private
login
private
login
public
private
logout
private

Sample Output 3

3
E - Spiral Rotation

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

N 行 N 列のグリッドが与えられます。ここで、N は偶数です。グリッドの上から i 行目、左から j 列目のマスをマス (i, j) と表記します。

グリッドの各マスは黒か白のいずれかで塗られており、A_{i, j} = # のときマス (i, j) は黒、A_{i, j} = . のときマス (i, j) は白で塗られています。

i = 1, 2, \ldots, \frac{N}{2} の順に以下の操作を行った後のグリッドの各マスの色を求めてください。

  • i 以上 N + 1 - i 以下の整数 x, y について、マス (y, N + 1 - x) の色をマス (x, y) の色で置き換える。この置き換えは条件を満たすすべての整数 x, y について同時に行う。

制約

  • N は 2 以上 3000 以下の偶数
  • A_{i, j} は # または .

入力

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

N
A_{1, 1}A_{1, 2}\ldotsA_{1, N}
A_{2, 1}A_{2, 2}\ldotsA_{2, N}
\vdots
A_{N, 1}A_{N, 2}\ldotsA_{N, N}

出力

すべての操作を終えた後、マス (i, j) の色が黒であるとき B_{i, j} = #、マス (i, j) の色が白であるとき B_{i, j} = . として以下の形式で出力せよ。

B_{1, 1}B_{1, 2}\ldotsB_{1, N}
B_{2, 1}B_{2, 2}\ldotsB_{2, N}
\vdots
B_{N, 1}B_{N, 2}\ldotsB_{N, N}

入力例 1

8
.......#
.......#
.####..#
.####..#
.##....#
.##....#
.#######
.#######

出力例 1

........
#######.
#.....#.
#.###.#.
#.#...#.
#.#####.
#.......
########

操作によってグリッドの各マスの色は以下のように変化します。

.......#   ........   ........   ........   ........
.......#   ######..   #######.   #######.   #######.
.####..#   ######..   #....##.   #.....#.   #.....#.
.####..# → ##..##.. → #....##. → #.##..#. → #.###.#.
.##....#   ##..##..   #..####.   #.##..#.   #.#...#.
.##....#   ##......   #..####.   #.#####.   #.#####.
.#######   ##......   #.......   #.......   #.......
.#######   ########   ########   ########   ########

入力例 2

6
.#.#.#
##.#..
...###
###...
..#.##
#.#.#.

出力例 2

#.#.#.
.#.#.#
#.#.#.
.#.#.#
#.#.#.
.#.#.#

入力例 3

12
.......#.###
#...#...#..#
###.#..#####
..#.#.#.#...
.#.....#.###
.......#.#..
#...#..#....
#####.......
...#...#.#.#
..###..#..##
#..#.#.#.#.#
.####.......

出力例 3

.#..##...##.
#.#.#.#.#...
###.##..#...
#.#.#.#.#...
#.#.##...##.
............
............
.###.###.###
...#...#.#..
.###...#.###
...#...#...#
.###...#.###

Score : 400 points

Problem Statement

You are given a grid with N rows and N columns, where N is an even number. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left.

Each cell is painted black or white. If A_{i, j} = #, cell (i, j) is black; if A_{i, j} = ., it is white.

Find the color of each cell after performing the following operation for i = 1, 2, \ldots, \frac{N}{2} in this order.

  • For all pairs of integers x, y between i and N + 1 - i, inclusive, replace the color of cell (y, N + 1 - x) with the color of cell (x, y). Perform these replacements simultaneously for all such pairs x, y.

Constraints

  • N is an even number between 2 and 3000, inclusive.
  • Each A_{i, j} is # or ..

Input

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

N
A_{1,1}A_{1,2}\ldots A_{1,N}
A_{2,1}A_{2,2}\ldots A_{2,N}
\vdots
A_{N,1}A_{N,2}\ldots A_{N,N}

Output

After all operations, let B_{i, j} = # if cell (i, j) is black, and B_{i, j} = . if it is white. Print the grid in the following format:

B_{1,1}B_{1,2}\ldots B_{1,N}
B_{2,1}B_{2,2}\ldots B_{2,N}
\vdots
B_{N,1}B_{N,2}\ldots B_{N,N}

Sample Input 1

8
.......#
.......#
.####..#
.####..#
.##....#
.##....#
.#######
.#######

Sample Output 1

........
#######.
#.....#.
#.###.#.
#.#...#.
#.#####.
#.......
########

The operations change the colors of the grid cells as follows:

.......#   ........   ........   ........   ........
.......#   ######..   #######.   #######.   #######.
.####..#   ######..   #....##.   #.....#.   #.....#.
.####..# → ##..##.. → #....##. → #.##..#. → #.###.#.
.##....#   ##..##..   #..####.   #.##..#.   #.#...#.
.##....#   ##......   #..####.   #.#####.   #.#####.
.#######   ##......   #.......   #.......   #.......
.#######   ########   ########   ########   ########

Sample Input 2

6
.#.#.#
##.#..
...###
###...
..#.##
#.#.#.

Sample Output 2

#.#.#.
.#.#.#
#.#.#.
.#.#.#
#.#.#.
.#.#.#

Sample Input 3

12
.......#.###
#...#...#..#
###.#..#####
..#.#.#.#...
.#.....#.###
.......#.#..
#...#..#....
#####.......
...#...#.#.#
..###..#..##
#..#.#.#.#.#
.####.......

Sample Output 3

.#..##...##.
#.#.#.#.#...
###.##..#...
#.#.#.#.#...
#.#.##...##.
............
............
.###.###.###
...#...#.#..
.###...#.###
...#...#...#
.###...#.###