A - Range Swap

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

長さ N の数列 A=(A_1,A_2,\ldots,A_N) および正整数 P,Q,R,S が与えられます。
ここで、P,Q,R,S は、1\leq P\leq Q<R\leq S \leq N および Q-P=S-R をみたしています。

数列 A の P 番目から Q 番目の項までと R 番目から S 番目の項までを入れ替えた数列を B=(B_1, B_2,\ldots, B_N) とします。
数列 B を出力してください。

制約

  • 1\leq N \leq 100
  • 1\leq A_i\leq 100
  • 1\leq P\leq Q<R\leq S \leq N
  • Q-P=S-R
  • 入力はすべて整数

入力

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

N P Q R S
A_1 A_2 \ldots A_N

出力

B_1, B_2,\ldots, B_N を空白区切りで出力せよ。

入力例 1

8 1 3 5 7
1 2 3 4 5 6 7 8

出力例 1

5 6 7 4 1 2 3 8

数列 A=(1,2,3,4,5,6,7,8) の 1 番目から 3 番目の項 (1,2,3) と 5 番目から 7 番目までの項 (5,6,7) を 入れ替えると, B=(5,6,7,4,1,2,3,8) となります。 よってこれを空白区切りで出力します。

入力例 2

5 2 3 4 5
2 2 1 1 1

出力例 2

2 1 1 2 1

数列には同じ整数が複数回現れる事もあります。

入力例 3

2 1 1 2 2
50 100

出力例 3

100 50

入力例 4

10 2 4 7 9
22 75 26 45 72 81 47 29 97 2

出力例 4

22 47 29 97 72 81 75 26 45 2

Score : 100 points

Problem Statement

You are given a sequence A=(A_1,A_2,\ldots,A_N) of length N and positive integers P,Q,R, and S.
Here, P,Q,R, and S satisfy 1\leq P\leq Q<R\leq S \leq N and Q-P=S-R.

Let B=(B_1, B_2,\ldots, B_N) be the sequence obtained by swapping the P-th through Q-th terms and the R-th through S-th terms of A.
Print the sequence B.

Constraints

  • 1\leq N \leq 100
  • 1\leq A_i\leq 100
  • 1\leq P\leq Q<R\leq S \leq N
  • Q-P=S-R
  • All values in the input are integers.

Input

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

N P Q R S
A_1 A_2 \ldots A_N

Output

Print B_1, B_2,\ldots, B_N, with spaces in between.

Sample Input 1

8 1 3 5 7
1 2 3 4 5 6 7 8

Sample Output 1

5 6 7 4 1 2 3 8

Swapping the 1-st through 3-rd terms (1,2,3) and the 5-th through 7-th terms (5,6,7) of the sequence A=(1,2,3,4,5,6,7,8) results in B=(5,6,7,4,1,2,3,8), which should be printed with spaces in between.

Sample Input 2

5 2 3 4 5
2 2 1 1 1

Sample Output 2

2 1 1 2 1

The same integer may occur multiple times in the sequence.

Sample Input 3

2 1 1 2 2
50 100

Sample Output 3

100 50

Sample Input 4

10 2 4 7 9
22 75 26 45 72 81 47 29 97 2

Sample Output 4

22 47 29 97 72 81 75 26 45 2
B - CBC

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

英大文字と英小文字からなる文字列 S が与えられます。S の英大文字のみを元の順序で連結して得られる文字列を出力してください。

制約

  • S は英大文字と英小文字からなる文字列である
  • S の長さは 1 以上 100 以下である

入力

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

S

出力

S の英大文字のみを元の順序で連結して得られる文字列を出力せよ。

入力例 1

AtCoderBeginnerContest

出力例 1

ACBC

S の英大文字のみを元の順序で連結して得られる文字列は ACBC です。よって、ACBC を出力します。

入力例 2

PaymentRequired

出力例 2

PR

入力例 3

program

出力例 3




S に英大文字が含まれないことがあることに注意してください。






Score : 100 points







Problem Statement
You are given a string S consisting of uppercase and lowercase English letters. Print the string obtained by concatenating only the uppercase letters of S in their original order.











Constraints
    

  • S is a string of uppercase and lowercase English letters.
    • 

  • The length of S is between 1 and 100, inclusive.
    • 
















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


S













Output
Print the string obtained by concatenating only the uppercase letters of S in their original order.















Sample Input 1
AtCoderBeginnerContest













Sample Output 1
ACBC




The string obtained by concatenating only the uppercase letters of S in their original order is ACBC. Hence, print ACBC.













Sample Input 2
PaymentRequired













Sample Output 2
PR















Sample Input 3
program













Sample Output 3



Note that S may contain no uppercase letters.






			


			
		

	
		

		

			C - Let's Get a Perfect Score
			

			
Time Limit: 2 sec / Memory Limit: 1024 MiB


			

				


配点 : 200 点







問題文
1 から N までの番号がついた N 人の参加者が、1 から M までの番号がついた M 問からなるコンテストに参加します。


1 以上 N 以下の整数 i 、1 以上 M 以下の整数 j について、S_i の j 番目の文字が o のとき参加者 i は問題 j を解くことが可能で、S_i の j 番目の文字が x のとき参加者 i は問題 j を解くことが不可能です。


このコンテストは、二人の参加者でペアを組んで参加します。二人が協力することで M 問全てを解くことが可能であるようなペアの個数を答えてください。


より厳密には、1\leq x < y\leq N を満たす整数の組 (x,y) であって、 1 以上 M 以下の任意の整数 j について、参加者 x か参加者 y の少なくとも一方は問題 j を解くことが可能であるという条件を満たすものの個数を答えてください。











制約
    

  • N は 2 以上 30 以下の整数
    • 

  • M は 1 以上 30 以下の整数
    • 

  • S_i は o, x からなる長さ M の文字列
    • 
















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


N M
S_1
S_2
\vdots
S_N












出力
答えを出力せよ。















入力例 1
5 5
ooooo
oooxx
xxooo
oxoxo
xxxxx












出力例 1
5



参加者 1 と 2 のペア、参加者 1 と 3 のペア、参加者 1 と 4 のペア、参加者 1 と 5 のペア、参加者 2 と 3 のペアの 5 個のペアが条件を満たします。


例えば参加者 2 と 4 のペアは、問題 4 が解けないので条件を満たしません。













入力例 2
3 2
ox
xo
xx












出力例 2
1














入力例 3
2 4
xxxx
oxox












出力例 3
0







Score : 200 points







Problem Statement
N participants, numbered 1 to N, will participate in a contest with M problems, numbered 1 to M.


For an integer i between 1 and N and an integer j between 1 and M, participant i can solve problem j if the j-th character of S_i is o, and cannot solve it if that character is x.


The participants must be in pairs. Print the number of ways to form a pair of participants who can collectively solve all the M problems.


More formally, print the number of pairs (x,y) of integers satisfying 1\leq x < y\leq N such that for any integer j between 1 and M, at least one of participant x and participant y can solve problem j.











Constraints
    

  • N is an integer between 2 and 30, inclusive.
    • 

  • M is an integer between 1 and 30, inclusive.
    • 

  • S_i is a string of length M consisting of o and x.
    • 
















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


N M
S_1
S_2
\vdots
S_N












Output
Print the answer.















Sample Input 1
5 5
ooooo
oooxx
xxooo
oxoxo
xxxxx












Sample Output 1
5



The following five pairs satisfy the condition: participants 1 and 2, participants 1 and 3, participants 1 and 4, participants 1 and 5, and participants 2 and 3.


On the other hand, the pair of participants 2 and 4, for instance, does not satisfy the condition because they cannot solve problem 4.













Sample Input 2
3 2
ox
xo
xx












Sample Output 2
1














Sample Input 3
2 4
xxxx
oxox












Sample Output 3
0







			


			
		

	
		

		

			D - Split?
			

			
Time Limit: 2 sec / Memory Limit: 1024 MiB


			

				


配点 : 200 点







問題文
ボウリングのピンは 1 から 10 の番号が付けられており、上から見ると下図のように配置されます。


0


この図の二つの点線に挟まれた部分を列と呼ぶことにします。

例えば、ピン 1, 5 とピン 3, 9 はそれぞれ同じ列に存在します。


いくつかのピンが倒れた状態のうち、特殊なものはスプリットと呼ばれます。

ピンの配置がスプリットであるとは、以下の条件が全て成り立つことを言います。


    

  • ピン 1 が倒れている。
    • 

  • ある二つの異なる列であって、次の条件を満たすものが存在する。
      

    • それぞれの列には、立っているピンが 1 本以上存在する。
      • 

    • それらの列の間に、ピンが全て倒れている列が存在する。
      • 

    

    • 



具体例は入出力例を参考にしてください。


さて、あるピンの配置が長さ 10 の文字列 S として与えられます。
i = 1, \dots, 10 について、ピン i が倒れているとき S の i 文字目は 0 であり、ピン i が立っているとき S の i 文字目は 1 です。

S で表されるピンの配置がスプリットかどうか判定してください。











制約
    

  • S は 0 と 1 からなる長さ 10 の文字列
    • 
















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


S












出力
S で表されるピンの配置がスプリットなら Yes を、そうでないなら No を出力せよ。















入力例 1
0101110101












出力例 1
Yes



倒れているピンを灰色で、立っているピンを白色で示すと下図のようになります。


ex0


ピン 5 が立っている列とピン 6 が立っている列の間にはピン 3, 9 が置かれている列が存在しますが、ピン 3, 9 はいずれも倒れているので、この配置はスプリットです。













入力例 2
0100101001












出力例 2
Yes



ex1













入力例 3
0000100110












出力例 3
No



ex2


この配置はスプリットではありません。













入力例 4
1101110101












出力例 4
No



ex3


ピン 1 が倒れていないので、スプリットではありません。






Score : 200 points







Problem Statement
Bowling pins are numbered 1 through 10.  The following figure is a top view of the arrangement of the pins:


0


Let us call each part between two dotted lines in the figure a column.

For example, Pins 1 and 5 belong to the same column, and so do Pin 3 and 9.


When some of the pins are knocked down, a special situation called split may occur.

A placement of the pins is a split if both of the following conditions are satisfied:


    

  • Pin 1 is knocked down.
    • 

  • There are two different columns that satisfy both of the following conditions:
      

    • Each of the columns has one or more standing pins.
      • 

    • There exists a column between these columns such that all pins in the column are knocked down.
      • 

    

    • 



See also Sample Inputs and Outputs for examples.


Now, you are given a placement of the pins as a string S of length 10.
For i = 1, \dots, 10, the i-th character of S is 0 if Pin i is knocked down, and is 1 if it is standing.

Determine if the placement of the pins represented by S is a split.











Constraints
    

  • S is a string of length 10 consisting of 0 and 1.
    • 
















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


S












Output
If the placement of the pins represented by S is a split, print Yes; otherwise, print No.















Sample Input 1
0101110101












Sample Output 1
Yes



In the figure below, the knocked-down pins are painted gray, and the standing pins are painted white:


ex0


Between the column containing a standing pin 5 and the column containing a standing pin 6 is a column containing Pins 3 and 9.  Since Pins 3 and 9 are both knocked down, the placement is a split.













Sample Input 2
0100101001












Sample Output 2
Yes



ex1













Sample Input 3
0000100110












Sample Output 3
No



ex2


This placement is not a split.













Sample Input 4
1101110101












Sample Output 4
No



ex3


This is not a split because Pin 1 is not knocked down.





			


			
		

	
		

		

			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
.#..##...##.
#.#.#.#.#...
###.##..#...
#.#.#.#.#...
#.#.##...##.
............
............
.###.###.###
...#...#.#..
.###...#.###
...#...#...#
.###...#.###