Problem Statement

You are given an integer N. Compute and output the value of 2^N-2N.

Constraints

• N is an integer between 1 and 11, inclusive.

Sample Input 1

1

Sample Output 1

0

The value of N given in this input is 1, so output the value of 2^1 - 2 \times 1, which is 0.

Sample Input 2

2

Sample Output 2

0

The value of N given in this input is 2, so output the value of 2^2 - 2 \times 2, which is 0.

Sample Input 3

11

Sample Output 3

2026

The value of N given in this input is 11, so output the value of 2^{11} - 2 \times 11, which is 2026.

Problem Statement

There are 4 squares lined up horizontally.

You are given a string S of length 4 consisting of 0 and 1.
If the i-th character of S is 1, there is a person in the i-th square from the left;
if the i-th character of S is 0, there is no person in the i-th square from the left.

Now, everyone will move to the next square to the right simultaneously. By this move, the person who was originally in the rightmost square will disappear.

Determine if there will be a person in each square after the move. Print the result as a string in the same format as S. (See also Sample Input / Output for clarity.)

Constraints

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

Sample Input 1

1011

Sample Output 1

0101

After the move, the person who was originally in the 1-st square will move to the 2-nd square,
the person in the 3-rd square to the 4-th square,
and the person in the 4-th square will disappear.

Sample Input 2

0000

Sample Output 2

0000

Sample Input 3

1111

Sample Output 3

0111

Problem Statement

A regular pentagon P is shown in the figure below.

Determine whether the length of the line segment connecting points S_1 and S_2 of P equals the length of the line segment connecting points T_1 and T_2.

Constraints

• Each of S_1, S_2, T_1, and T_2 is one of the characters A, B, C, D, and E.
• S_1 \neq S_2
• T_1 \neq T_2

Sample Input 1

AC
EC

Sample Output 1

Yes

The length of the line segment connecting point A and point C of P equals the length of the line segment connecting point E and point C.

Sample Input 2

DA
EA

Sample Output 2

No

The length of the line segment connecting point D and point A of P does not equal the length of the line segment connecting point E and point A.

Sample Input 3

BD
BD

Sample Output 3

Yes

Problem Statement

AtCoder Regular Contest (ARC) is divided into two divisions.

• In ARC Div. 1, participants whose rating at the start of the contest is between 1600 and 2799, inclusive, are subject to rating updates.
• In ARC Div. 2, participants whose rating at the start of the contest is between 1200 and 2399, inclusive, are subject to rating updates.

Takahashi decided to participate in N ARCs.

Initially, his rating is R.

The i-th (1\leq i\leq N) ARC is Div. D _ i, and his performance in that contest is represented by an integer A _ i.

If he is subject to a rating update in the i-th ARC, let T be his rating at the start of that contest. Then, after the contest, his rating becomes T+A _ i.

If his is not subject to a rating update, his rating does not change.

Rating updates for ARCs are performed immediately after the contest ends, and whether he is subject to rating updates in the next contest is determined based on his rating after the update.

Find his rating after finishing the N ARCs.

He does not participate in any contests other than these N ARCs, and his rating does not change in other ways.

Constraints

• 1\leq N\leq 100
• 0\leq R\leq 4229
• 1\leq D _ i\leq 2\ (1\leq i\leq N)
• -1000\leq A _ i\leq 1000\ (1\leq i\leq N)
• All input values are integers.

Sample Input 1

4 1255
2 900
1 521
2 600
1 52

Sample Output 1

2728

Initially, Takahashi's rating is 1255.

For each contest, Takahashi's rating changes as follows:

• The 1st ARC is Div. 2. He is subject to rating updates, so his rating becomes 1255+900=2155.
• The 2nd ARC is Div. 1. He is subject to rating updates, so his rating becomes 2155+521=2676.
• The 3rd ARC is Div. 2. He is not subject to rating updates, so his rating does not change.
• The 4th ARC is Div. 1. He is subject to rating updates, so his rating becomes 2676+52=2728.

After the four ARCs, his rating is 2728, so print 2728.

Sample Input 2

2 3031
1 1000
2 -1000

Sample Output 2

3031

He is a Red coder, so his rating does not change upon his performance in ARC.

Sample Input 3

15 2352
2 -889
2 420
2 -275
1 957
1 -411
1 -363
1 151
2 -193
2 289
2 -770
2 109
1 345
2 551
1 -702
1 355

Sample Output 3

1226

Problem Statement

You are given a sequence of positive integers A=(A_1,A_2,\dots,A_N) of length N and a positive integer K.

Find the sum of the integers between 1 and K, inclusive, that do not appear in the sequence A.

Constraints

• 1\leq N \leq 2\times 10^5
• 1\leq K \leq 2\times 10^9
• 1\leq A_i \leq 2\times 10^9
• All input values are integers.

Sample Input 1

4 5
1 6 3 1

Sample Output 1

11

Among the integers between 1 and 5, three numbers, 2, 4, and 5, do not appear in A.

Thus, print their sum: 2+4+5=11.

Sample Input 2

1 3
346

Sample Output 2

6

Sample Input 3

10 158260522
877914575 24979445 623690081 262703497 24979445 1822804784 1430302156 1161735902 923078537 1189330739

Sample Output 3

12523196466007058

Problem Statement

You have N socks. The color of the i-th sock is A_i.

You want to perform the following operation as many times as possible. How many times can it be performed at most?

• Choose two same-colored socks that are not paired yet, and pair them.

Constraints

• 1\leq N \leq 5\times 10^5
• 1\leq A_i \leq 10^9
• All values in the input are integers.

Sample Input 1

6
4 1 7 4 1 4

Sample Output 1

2

You can do the operation twice as follows.

• Choose two socks with the color 1 and pair them.
• Choose two socks with the color 4 and pair them.

Then, you will be left with one sock with the color 4 and another with the color 7, so you can no longer do the operation. There is no way to do the operation three or more times, so you should print 2.

Sample Input 2

1
158260522

Sample Output 2

0

Sample Input 3

10
295 2 29 295 29 2 29 295 2 29

Sample Output 3

4

Problem Statement

For i=1,2,\dots,N, let B_i denote the integer formed by concatenating A_i ones.
More formally, B_i=\sum_{j=0}^{A_i-1}{10^j}.
Find \sum_{i=1}^{N}{B_i}.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 2 \times 10^5
• All input values are integers.

Sample Input 1

4
3 3 3 3

Sample Output 1

444

B_1=B_2=B_3=B_4=111, so B_1+B_2+B_3+B_4=444.

Sample Input 2

3
30 10 20

Sample Output 2

111111111122222222223333333333

The answer may be very large.

Sample Input 3

10
1 2 3 4 5 6 7 8 9 10

Sample Output 3

1234567900

Problem Statement

There is a grid with H rows and W columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left of the grid.
Each square of the grid is holed or not. There are exactly N holed squares: (a_1, b_1), (a_2, b_2), \dots, (a_N, b_N).

When the triple of positive integers (i, j, n) satisfies the following condition, the square region whose top-left corner is (i, j) and whose bottom-right corner is (i + n - 1, j + n - 1) is called a holeless square.

• i + n - 1 \leq H.
• j + n - 1 \leq W.
• For every pair of non-negative integers (k, l) such that 0 \leq k \leq n - 1, 0 \leq l \leq n - 1, square (i + k, j + l) is not holed.

How many holeless squares are in the grid?

Constraints

• 1 \leq H, W \leq 3000
• 0 \leq N \leq \min(H \times W, 10^5)
• 1 \leq a_i \leq H
• 1 \leq b_i \leq W
• All (a_i, b_i) are pairwise different.
• All input values are integers.

Sample Input 1

2 3 1
2 3

Sample Output 1

6

There are six holeless squares, listed below. For the first five, n = 1, and the top-left and bottom-right corners are the same square.

• The square region whose top-left and bottom-right corners are (1, 1).
• The square region whose top-left and bottom-right corners are (1, 2).
• The square region whose top-left and bottom-right corners are (1, 3).
• The square region whose top-left and bottom-right corners are (2, 1).
• The square region whose top-left and bottom-right corners are (2, 2).
• The square region whose top-left corner is (1, 1) and whose bottom-right corner is (2, 2).

Sample Input 2

3 2 6
1 1
1 2
2 1
2 2
3 1
3 2

Sample Output 2

0

There may be no holeless square.

Sample Input 3

1 1 0

Sample Output 3

1

The whole grid may be a holeless square.

Sample Input 4

3000 3000 0

Sample Output 4

9004500500

Problem Statement

There is a skating rink represented by a grid with H horizontal rows and W vertical columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.

The skating rink has N obstacles. The i-th obstacle is placed at (X_i,Y_i).

In a single move, Takahashi chooses one of the four directions, up, down, left, or right, and keeps moving until he hits an obstacle.
When he hits an obstacle, he stops at the square right before the obstacle. Since the skating rink is surrounded by cliffs, it is prohibited to start a move in which he will never hit an obstacle.

Takahashi is initially at (s_x,s_y). He wants to make some number of moves to stop at (g_x,g_y).

Find the minimum number of moves required to end up at (g_x, g_y). If it is not possible, report the fact.

Constraints

• 1\leq H \leq 10^9
• 1\leq W \leq 10^9
• 1\leq N \leq 10^5
• 1\leq s_x,g_x\leq H
• 1\leq s_y,g_y\leq W
• 1\leq X_i \leq H
• 1\leq Y_i \leq W
• (s_x,s_y)\neq (g_x,g_y)
• (s_x,s_y)\neq (X_i,Y_i)
• (g_x,g_y)\neq (X_i,Y_i)
• If i\neq j, then (X_i,Y_i)\neq (X_j,Y_j).
• All values in input are integers.

Sample Input 1

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

Sample Output 1

4

In the figure, (s_x,s_y) is denoted by S and (g_x,g_y) is denoted by G.
By moving as (3,4)\rightarrow(2,4) \rightarrow(2,2) \rightarrow(5,2) \rightarrow(5,6), he can end up at (g_x,g_y) with 4 moves.

Sample Input 2

4 6 2
3 2
3 5
4 5
2 5

Sample Output 2

-1

He must stop at (g_x,g_y).
Note that just passing through (g_x,g_y) is not considered to be ending up at the goal.

Sample Input 3

1 10 1
1 5
1 1
1 7

Sample Output 3

-1

If he chooses to move to the left, Takahashi will fall down the cliff after passing through (g_x,g_y).
Note that it is prohibited to start a move in which he will never hit an obstacle, as the skating rink is surrounded by cliffs.