A - ^{-1}

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

(1,2,…,N) を並び替えた数列 P と整数 X が与えられます。 数列 P の i 番目の項の値は P_i です。 P_k = X を満たす k を出力してください。

制約

  • 1 \leq N \leq 100
  • 1 \leq X \leq N
  • P は (1,2,…,N) を並び替えてできる数列
  • 入力はすべて整数

入力

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

N X
P_1 P_2 \ldots P_N

出力

答えを出力せよ。


入力例 1

4 3
2 3 1 4

出力例 1

2

P = (2,3,1,4) なので、P_2 = 3 です。したがって、2 を出力します。


入力例 2

5 2
3 5 1 4 2

出力例 2

5

入力例 3

6 6
1 2 3 4 5 6

出力例 3

6

Score : 100 points

Problem Statement

You are given a sequence P that is a permutation of (1,2,…,N), and an integer X. The i-th term of P has a value of P_i. Print k such that P_k = X.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq X \leq N
  • P is a permutation of (1,2,…,N).
  • All values in the input are integers.

Input

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

N X
P_1 P_2 \ldots P_N

Output

Print the answer.


Sample Input 1

4 3
2 3 1 4

Sample Output 1

2

We have P = (2,3,1,4), so P_2 = 3. Thus, you should print 2.


Sample Input 2

5 2
3 5 1 4 2

Sample Output 2

5

Sample Input 3

6 6
1 2 3 4 5 6

Sample Output 3

6
B - Many A+B Problems

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

N 個の整数の 2 つ組 (A_1, B_1), (A_2, B_2), \ldots, (A_N, B_N) が与えられます。 各 i = 1, 2, \ldots, N について、A_i + B_i を出力してください。

制約

  • 1 \leq N \leq 1000
  • -10^9 \leq A_i, B_i \leq 10^9
  • 入力はすべて整数

入力

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

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

N 行出力せよ。 i = 1, 2, \ldots, N について、i 行目には A_i+B_i を出力せよ。


入力例 1

4
3 5
2 -6
-5 0
314159265 123456789

出力例 1

8
-4
-5
437616054
  • 1 行目には、A_1 + B_1 = 3 + 5 = 8 を、
  • 2 行目には、A_2 + B_2 = 2 + (-6) = -4 を、
  • 3 行目には、A_3 + B_3 = (-5) + 0 = -5 を、
  • 4 行目には、A_4 + B_4 = 314159265 + 123456789 = 437616054 を出力します。

Score : 100 points

Problem Statement

You are given N pairs of integers: (A_1, B_1), (A_2, B_2), \ldots, (A_N, B_N). For each i = 1, 2, \ldots, N, print A_i + B_i.

Constraints

  • 1 \leq N \leq 1000
  • -10^9 \leq A_i, B_i \leq 10^9
  • All values in the input are integers.

Input

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

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

Print N lines. For i = 1, 2, \ldots, N, the i-th line should contain A_i+B_i.


Sample Input 1

4
3 5
2 -6
-5 0
314159265 123456789

Sample Output 1

8
-4
-5
437616054
  • The first line should contain A_1 + B_1 = 3 + 5 = 8.
  • The second line should contain A_2 + B_2 = 2 + (-6) = -4.
  • The third line should contain A_3 + B_3 = (-5) + 0 = -5.
  • The fourth line should contain A_4 + B_4 = 314159265 + 123456789 = 437616054.
C - 1D Pawn

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

N 個のマスが左右一列に並んでおり、左から順にマス 1、マス 2、…、マス N と番号づけられています。
また、K 個のコマがあり、最初左から i 番目のコマはマス A_i に置かれています。
これらに対して、Q 回の操作を行います。 i 回目の操作では次の操作を行います。

  • 左から L_i 番目のコマが一番右のマスにあるならば何も行わない。
  • そうでない時、左から L_i 番目のコマがあるマスの 1 つ右のマスにコマが無いならば、左から L_i 番目のコマを 1 つ右のマスに移動させる。 1 つ右のマスにコマがあるならば、何も行わない。

Q 回の操作が終了した後の状態について、i=1,2,\ldots,K に対して左から i 番目のコマがあるマスの番号を出力してください。

制約

  • 1\leq K\leq N\leq 200
  • 1\leq A_1<A_2<\cdots<A_K\leq N
  • 1\leq Q\leq 1000
  • 1\leq L_i\leq K
  • 入力はすべて整数

入力

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

N K Q
A_1 A_2 \ldots A_K
L_1 L_2 \ldots L_Q

出力

K 個の整数を空白区切りで一行に出力せよ。 ここで、i 個目の整数は、 Q 回の操作が終了した後の状態について、左から i 番目のコマの番号を表す。


入力例 1

5 3 5
1 3 4
3 3 1 1 2

出力例 1

2 4 5

最初、コマはマス 1, 3, 4 にあります。これに対して以下のように操作が行われます。

  • 左から 3 番目のコマはマス 4 にあります。 これは一番右のマスでなく、その 1 つ右のマスにもコマが置かれていないため、左から 3 番目のコマをマス 5 に動かします。 コマはマス 1, 3, 5 にある状態になります。
  • 左から 3 番目のコマはマス 5 にあります。 これは一番右のマスなので、何も行いません。 コマはマス 1, 3, 5 にある状態のままです。
  • 左から 1 番目のコマはマス 1 にあります。 これは一番右のマスでなく、その 1 つ右のマスにもコマが置かれていないため、左から 1 番目のコマをマス 2 に動かします。 コマはマス 2, 3, 5 にある状態になります。
  • 左から 1 番目のコマはマス 2 にあります。 これは一番右のマスでありませんが、その 1 つ右のマス(マス 3 )にコマが置かれているため、何も行いません。 コマはマス 2, 3, 5 にある状態のままです。
  • 左から 2 番目のコマはマス 3 にあります。 これは一番右のマスでなく、その右のマスにもコマが置かれていないため、左から 2 番目のコマをマス 4 に動かします。 コマはマス 2, 4, 5 にある状態になります。

よって、Q 回の操作が終わった後でコマはマス 2, 4, 5 に置かれているため、2,4,5 を空白区切りでこの順に出力します。


入力例 2

2 2 2
1 2
1 2

出力例 2

1 2

入力例 3

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

出力例 3

2 5 6 7 9 10

Score : 200 points

Problem Statement

There are N squares, indexed Square 1, Square 2, …, Square N, arranged in a row from left to right.
Also, there are K pieces. The i-th piece from the left is initially placed on Square A_i.
Now, we will perform Q operations against them. The i-th operation is as follows:

  • If the L_i-th piece from the left is on its rightmost square, do nothing.
  • Otherwise, move the L_i-th piece from the left one square right if there is no piece on the next square on the right; if there is, do nothing.

Print the index of the square on which the i-th piece from the left is after the Q operations have ended, for each i=1,2,\ldots,K.

Constraints

  • 1\leq K\leq N\leq 200
  • 1\leq A_1<A_2<\cdots<A_K\leq N
  • 1\leq Q\leq 1000
  • 1\leq L_i\leq K
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K Q
A_1 A_2 \ldots A_K
L_1 L_2 \ldots L_Q

Output

Print K integers in one line, with spaces in between. The i-th of them should be the index of the square on which the i-th piece from the left is after the Q operations have ended.


Sample Input 1

5 3 5
1 3 4
3 3 1 1 2

Sample Output 1

2 4 5

At first, the pieces are on Squares 1, 3, and 4. The operations are performed against them as follows:

  • The 3-rd piece from the left is on Square 4. This is not the rightmost square, and the next square on the right does not contain a piece, so move the 3-rd piece from the left to Square 5. Now, the pieces are on Squares 1, 3, and 5.
  • The 3-rd piece from the left is on Square 5. This is the rightmost square, so do nothing. The pieces are still on Squares 1, 3, and 5.
  • The 1-st piece from the left is on Square 1. This is not the rightmost square, and the next square on the right does not contain a piece, so move the 1-st piece from the left to Square 2. Now, the pieces are on Squares 2, 3, and 5.
  • The 1-st piece from the left is on Square 2. This is not the rightmost square, but the next square on the right (Square 3) contains a piece, so do nothing. The pieces are still on Squares 2, 3, and 5.
  • The 2-nd piece from the left is on Square 3. This is not the rightmost square, and the next square on the right does not contain a piece, so move the 2-nd piece from the left to Square 4; Now, the pieces are still on Squares 2, 4, and 5.

Thus, after the Q operations have ended, the pieces are on Squares 2, 4, and 5, so 2, 4, and 5 should be printed in this order, with spaces in between.


Sample Input 2

2 2 2
1 2
1 2

Sample Output 2

1 2

Sample Input 3

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

Sample Output 3

2 5 6 7 9 10
D - Overlapping sheets

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

座標平面上に N 枚の長方形のシートが張られています。

各シートが覆う長方形領域の各辺はそれぞれ x 軸または y 軸と平行であり、
具体的には、i 枚目のシートはちょうど A_i \leq x\leq B_i かつ C_i \leq y\leq D_i をみたす領域全体を覆っています。

1 枚以上のシートによって覆われている領域 の面積を S とすると、 S は制約の条件下で整数となる事が証明できます。
S を整数の形で出力してください。

制約

  • 2\leq N\leq 100
  • 0\leq A_i<B_i\leq 100
  • 0\leq C_i<D_i\leq 100
  • 入力はすべて整数

入力

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

N
A_1 B_1 C_1 D_1
A_2 B_2 C_2 D_2
\vdots
A_N B_N C_N D_N

出力

1 枚以上のシートによって覆われている領域の面積 S を整数で出力せよ。


入力例 1

3
0 5 1 3
1 4 0 5
2 5 2 4

出力例 1

20

3 枚のシートによって覆われている領域は次のようになります。
ここで、赤色・黄色・青色はそれぞれ 1 枚目・ 2 枚目・ 3 枚目のシートによって覆われている領域を表しています。

よって、1 枚以上のシートによって覆われている領域の面積は S=20 となります。


入力例 2

2
0 100 0 100
0 100 0 100

出力例 2

10000

異なるシートが同じ領域を覆っている事があることに注意してください。


入力例 3

3
0 1 0 1
0 3 0 5
5 10 0 10

出力例 3

65

Score : 200 points

Problem Statement

There are N rectangular sheets spread out on a coordinate plane.

Each side of the rectangular region covered by each sheet is parallel to the x- or y-axis.
Specifically, the i-th sheet covers exactly the region satisfying A_i \leq x\leq B_i and C_i \leq y\leq D_i.

Let S be the area of the region covered by one or more sheets. It can be proved that S is an integer under the constraints.
Print S as an integer.

Constraints

  • 2\leq N\leq 100
  • 0\leq A_i<B_i\leq 100
  • 0\leq C_i<D_i\leq 100
  • All input values are integers.

Input

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

N
A_1 B_1 C_1 D_1
A_2 B_2 C_2 D_2
\vdots
A_N B_N C_N D_N

Output

Print the area S of the region covered by one or more sheets as an integer.


Sample Input 1

3
0 5 1 3
1 4 0 5
2 5 2 4

Sample Output 1

20

The three sheets cover the following regions.
Here, red, yellow, and blue represent the regions covered by the first, second, and third sheets, respectively.

Therefore, the area of the region covered by one or more sheets is S=20.


Sample Input 2

2
0 100 0 100
0 100 0 100

Sample Output 2

10000

Note that different sheets may cover the same region.


Sample Input 3

3
0 1 0 1
0 3 0 5
5 10 0 10

Sample Output 3

65
E - Counting Squares

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

二次元平面があります。1 以上 9 以下の整数 r,c について、S_{r} の c 番目の文字が # であるとき座標 (r,c) にポーンが置いてあり、S_{r} の c 番目の文字が . であるとき座標 (r,c) に何も置かれていません。

この平面上の正方形であって、4 頂点全てにポーンが置いてあるものの個数を求めてください。

制約

  • S_1,\ldots,S_9 はそれぞれ # と . からなる長さ 9 の文字列

入力

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

S_1
S_2
\vdots
S_9

出力

答えを出力せよ。


入力例 1

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

出力例 1

2

座標 (1,1),(1,2),(2,2),(2,1) を頂点とする正方形は、4 頂点全てにポーンが置かれています。

座標 (4,8),(5,6),(7,7),(6,9) を頂点とする正方形も、4 頂点全てにポーンが置かれています。

よって答えは 2 です。


入力例 2

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

出力例 2

3

Score : 300 points

Problem Statement

There is a two-dimensional plane. For integers r and c between 1 and 9, there is a pawn at the coordinates (r,c) if the c-th character of S_{r} is #, and nothing if the c-th character of S_{r} is ..

Find the number of squares in this plane with pawns placed at all four vertices.

Constraints

  • Each of S_1,\ldots,S_9 is a string of length 9 consisting of # and ..

Input

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

S_1
S_2
\vdots
S_9

Output

Print the answer.


Sample Input 1

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

Sample Output 1

2

The square with vertices (1,1), (1,2), (2,2), and (2,1) have pawns placed at all four vertices.

The square with vertices (4,8), (5,6), (7,7), and (6,9) also have pawns placed at all four vertices.

Thus, the answer is 2.


Sample Input 2

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

Sample Output 2

3