Problem Statement

Takahashi participated in a contest. He made A wrong submissions before being accepted T minutes into the contest.

Compute the penalty value represented by the following expression:

5\times A + T.

Constraints

• 0 \leq A \leq 10
• 1 \leq T \leq 100
• All values in the input are integers.

Sample Input 1

3 10

Sample Output 1

25

Takahashi made 3 wrong submissions before being accepted 10 minutes into the contest, so the penalty value is 25.

Sample Input 2

1 8

Sample Output 2

13

Sample Input 3

0 10

Sample Output 3

10

Problem Statement

In AtCoder, the programming contest hosting website, those whose maximum rating is 2800 or greater is in the "hall of fame".
Takahashi's current rating is C and the maximum rating is H.
Print o if he is in the "hall of fame", and x otherwise.

Constraints

• C and H are integers.
• 0 \le C \le H \le 4400

Sample Input 1

3085 3085

Sample Output 1

o

Takahashi's current rating is 3085, and his maximum rating is 3085 too.
Thus, Takahashi is in the hall of fame.

Sample Input 2

2580 2631

Sample Output 2

x

Sample Input 3

0 2800

Sample Output 3

o

Even if his current rating is less than 2800, he is still in the hall of fame as long as his maximum rating is 2800 or greater.

Problem Statement

On a two-dimensional plane, there is a circle of radius R centered at point (X, Y).
For an integer pair (i, j), let us define S_{i,j} = # if point (i, j) is in the interior or on the circumference of the circle, and S_{i,j} = . otherwise.
Print S_{i,j} for all integer pairs (i, j) such that -N \leq i,j \leq N.

Constraints

• -100 \leq X, Y \leq 100
• 1 \leq R \leq 100
• 1 \leq N \leq 200
• If S_{i,j} = #, then -N \leq i,j \leq N.
• All values in the input are integers.

Sample Input 1

1 -2 1 3

Sample Output 1

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

On a two-dimensional plane, there is a circle of radius 1 centered at point (1,-2).
We have S_{i,j} = # if (i,j) is one of (0,-2),(1,-3),(1,-2),(1,-1), and (2,-2), and S_{i,j} = . otherwise.

Sample Input 2

-3 1 4 8

Sample Output 2

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

Sample Input 3

0 0 10 10

Sample Output 3

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

Problem Statement

Takahashi is trying to record a certain television program (hereafter called "the program") with a recorder.
At time 0, the program is scheduled to be broadcasted from time A to time A + R. However, the broadcast time of the program may change due to programming circumstances. Therefore, Takahashi has decided to take the following actions to record the entire program.

• Perform the following operation at all times that are multiples of D after time 0 (including time 0). (This operation takes no time.)
  • Let t be the current time, and p and q be the program's start and end times scheduled at time t, respectively. If t \lt q, reserve to record from time \max(p, t) to time q.

Here, note that Takahashi's recorder can handle multiple recording reservations. In other words, even if Takahashi makes a new recording reservation when there is already one or more recording reservations, the previous recording reservations are not canceled, and all recording reservations are carried out.

As mentioned earlier, the program was scheduled to be broadcasted from time A to time A + R at time 0. However, at time B, the broadcast time of the program was changed to be from time C to time C + R. (Here, it is guaranteed that B < A, B < C, A \neq C, and none of A, B, C is a multiple of D.)

Please determine whether Takahashi can record the entire program. More precisely, determine whether the following proposition is true.

• For all times t between C and C + R, inclusive, there is at least one recording reservation that satisfies the following conditions.
  • If the recording reservation is from time p to time q, it holds that p \leq t \leq q.

Constraints

• 1 \leq A, B, C, D, R \leq 1000
• A, B, C, D, and R are integers.
• B \lt \min(A, C)
• A \neq C
• None of A, B, and C is a multiple of D.

Sample Input 1

5 3 15 20 20

Sample Output 1

Yes

Takahashi's actions can be described as follows.

• At time 0, the program is scheduled to be broadcasted from time 5 to time 25.
• Takahashi reserves to record from time 5 to time 25 at time 0.
• At time 3, the scheduled broadcast time of the program is changed to be from time 15 to time 35.
• Takahashi reserves to record from time 20 to time 35 at time 20.
• Takahashi does not make any recording reservations after time 40 as it is past the scheduled end time of the program.

The period 15 \leq t \leq 20 is covered by the first recording reservation, and the period 20 \leq t \leq 35 is covered by the second recording reservation. Therefore, the answer is Yes.

Sample Input 2

5 3 27 30 20

Sample Output 2

No

Sample Input 3

930 542 605 509 582

Sample Output 3

No

Problem Statement

In a certain programming contest, N problems are set, and if you answer the i-th problem correctly, you are given A_i points.

Consider choosing and solving exactly K problems out of these N problems.
When you calculate the "total score obtained when all the selected problems are solved" for all ways of choosing problems, what is the sum of those total scores?

Constraints

• All input values are integers.
• 1 \le K \le N \le 8
• 1 \le A_i \le 2718

Sample Input 1

4 2
100 200 300 400

Sample Output 1

3000

In this contest, 4 problems are set, and we consider solving 2 of them. There are 6 ways to choose the problems as follows.

• Solve the 1-st and 2-nd problems. The total score obtained is 300 points.
• Solve the 1-st and 3-rd problems. The total score obtained is 400 points.
• Solve the 1-st and 4-th problems. The total score obtained is 500 points.
• Solve the 2-nd and 3-rd problems. The total score obtained is 500 points.
• Solve the 2-nd and 4-th problems. The total score obtained is 600 points.
• Solve the 3-rd and 4-th problems. The total score obtained is 700 points.

The sum of these total scores is 3000 points.

Sample Input 2

1 1
2718

Sample Output 2

2718

Sample Input 3

8 4
597 1035 2048 994 1843 601 7 659

Sample Output 3

272440

Problem Statement

Given a sequence A of length N, find a sequence B that satisfies all of the following conditions.
We can prove that this sequence B is unique.

• B is a sequence obtained by rearranging (1,2,...,N).
• For all integer pairs (i,j)(i \neq j), the following conditions are satisfied:
  • if A_i<A_j, then B_i<B_j;
  • if A_i=A_j and i<j, then B_i<B_j.

Constraints

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

Sample Input 1

10
2 3 4 4 4 4 3 3 2 1

Sample Output 1

2 4 7 8 9 10 5 6 3 1

When the sequence A=(2,3,4,4,4,4,3,3,2,1), the sequence B=(2,4,7,8,9,10,5,6,3,1).

Sample Input 2

1
1000000000

Sample Output 2

1

Sample Input 3

20
30 10 40 10 50 90 20 60 50 30 50 80 90 70 90 30 20 30 80 40

Sample Output 3

5 1 9 2 11 18 3 14 12 6 13 16 19 15 20 7 4 8 17 10

Problem Statement

Determine if there is a way to assign 0 or 1 to each of N variables x_1,x_2,\ldots,x_N so that:

• for all i=1,2,\ldots,M,
  • there exists an integer j (1 \leq j \leq k_i) such that x_{a_{i,j}}=b_{i,j}.

Constraints

• 1 \leq N \leq 15
• 1 \leq M \leq 100
• 1 \leq k_i \leq N
• 1 \leq a_{i,1} \lt a_{i,2} \lt \ldots \lt a_{i,k_i} \leq N
• b_{i,j} \in \{0,1 \}
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

Yes

For example, assigning x_1=1, x_2=0,x_3=0,x_4=0, and x_5=0 satisfies the condition.

Sample Input 2

1 2
1
1 0
1
1 1

Sample Output 2

No

Problem Statement

When you represent an integer N as the sum of one or more distinct positive integers, at most how many positive integers can be used?

Constraints

• N is an integer between 1 and 10^{18}, inclusive.

Sample Input 1

7

Sample Output 1

3

We can represent 7 as 1+2+4.

Since we cannot represent 7 as the sum of four or more distinct positive integers, 3 is the answer.

Sample Input 2

1

Sample Output 2

1

Sample Input 3

164312478120341038

Sample Output 3

573258192

Problem Statement

You are given N integers A_1, A_2, \ldots, A_N.

Consider choosing K of them. Find the maximum possible greatest common divisor of the chosen integers.

Constraints

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

Sample Input 1

3 2
2 3 4

Sample Output 1

2

If you choose 2 and 4, the greatest common divisor will be 2, which is the maximum.

Sample Input 2

3 3
5 5 5

Sample Output 2

5

Sample Input 3

10 4
225707 265514 765350 617700 837712 187034 799142 35549 784661 961512

Sample Output 3

2

Problem Statement

A ninja will fight against N monsters one by one in order. The attack power of the i-th monster is a_i, and its health is b_i. A monster is immediately defeated when its health becomes 0 or less.
Each monster is either on the ground or flying. If x_i = 0, the i-th monster is on the ground, and if x_i = 1, it is flying.

The ninja initially has M shurikens. Each shuriken can be used only once by throwing it.
The ninja and the i-th monster fight as follows:

• First, the ninja chooses zero or more shurikens from the ones he has and throws them at the monster. The monster's health decreases by the number of shurikens thrown, and if one or more shurikens are thrown at a flying monster, it lands on the ground.
• Then, the ninja and the monster take turns attacking each other. Each attack by the ninja decreases the monster's health by 1, and each attack by the monster decreases the ninja's health by a_i. Here, if the monster is on the ground, the ninja attacks first, and if it is flying, the monster attacks first.

Find the minimum possible difference between the ninja's initial health and his health after defeating all the monsters.
Assume that the ninja's health is sufficiently large.

Constraints

• 1 \leq N \leq 3 \times 10^5
• 0 \leq M \leq 10^{11}
• 1 \leq a_i, b_i \leq 3 \times 10^5
• x_i = 0 or x_i = 1.
• All input values are integers.

Sample Input 1

2 1
2 2 1
5 2 0

Sample Output 1

4

If the ninja fights as follows, his health will decrease by a total of 4, which is optimal:

• Do not throw any shurikens at the first monster.
  • Since the monster is flying, it attacks the ninja first. The ninja's health decreases by 2.
  • The ninja attacks. The monster's health becomes 1.
  • The monster attacks. The ninja's health decreases by 2.
  • The ninja attacks. The monster's health becomes 0, and it is defeated.
• Throw one shuriken at the second monster. The monster's health becomes 1.
  • Since the monster is on the ground, the ninja attacks first. The monster's health becomes 0, and it is defeated.

Sample Input 2

1 2
1 4 1

Sample Output 2

1

If the ninja fights as follows, his health will decrease by a total of 1, which is optimal:

• Throw two shurikens at the first monster. The monster's health becomes 2, and it lands on the ground.
  • Since the monster is on the ground, the ninja attacks first. The monster's health becomes 1.
  • The monster attacks. The ninja's health decreases by 1.
  • The ninja attacks. The monster's health becomes 0, and it is defeated.

Sample Input 3

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

Sample Output 3

25

Problem Statement

There is a sequence of length N, P=(P_1,P_2,\ldots,P_N), which is a permutation of (1,2,\ldots,N).

You can perform the following operation on this sequence any number of times, possibly zero:

• Choose an integer i between 1 and N-1, inclusive, and swap the i-th element and the (i+1)-th element of P. The cost of this operation is the sum of the two numbers being swapped.

Find the minimum cost required to sort P in ascending order.

Constraints

• 1 \leq N \leq 2\times 10^5
• N is an integer.
• P is a permutation of (1,2,\ldots,N).

Sample Input 1

4
3 2 1 4

Sample Output 1

12

For example, you can sort P in ascending order by performing the following three operations:

• Choose i=1 to swap 3 and 2. This costs 5, and the sequence becomes (2,3,1,4).
• Choose i=2 to swap 3 and 1. This costs 4, and the sequence becomes (2,1,3,4).
• Choose i=1 to swap 2 and 1. This costs 3, and the sequence becomes (1,2,3,4).

Since it is impossible to sort the sequence in ascending order with a cost less than 12, the answer is 12.

Sample Input 2

9
3 1 4 5 9 2 6 8 7

Sample Output 2

96

Sample Input 3

6
1 2 3 4 5 6

Sample Output 3

0

Sometimes, no operations are needed.

Problem Statement

You are given an H-by-W matrix A consisting of non-negative integers.

You can perform the following operations any number of times (possibly zero):

• Choose an integer i satisfying 1 \le i \le H and a non-negative integer X, and replace each element A_{i,j} in the i-th row of the matrix A with A_{i,j}\ \mathrm{XOR}\ X.
• Choose an integer j satisfying 1 \le j \le W and a non-negative integer X, and replace each element A_{i,j} in the j-th column of the matrix A with A_{i,j}\ \mathrm{XOR}\ X.

You are also given an H-by-W matrix B consisting of non-negative integers and -1.

Determine if it is possible to make A_{i,j}=B_{i,j} for all pairs of integers (i,j) such that B_{i,j} \neq -1 by performing the operations.

Constraints

• 1 \le H,W \le 500
• 0 \le A_{i,j} < 2^{30}
• -1 \le B_{i,j} < 2^{30}
• All input values are integers.

Sample Input 1

2 2
1 2
3 4
-1 3
1 7

Sample Output 1

Yes

Initially, A is as follows:

1 2
3 4

Performing the operation with X=1 on the second column, we get:

1 3
3 5

Performing the operation with X=2 on the second row, we get:

1 3
1 7

Thus, it is possible to satisfy the condition, so print Yes.

Sample Input 2

2 2
1 2
3 4
5 3
1 7

Sample Output 2

No

In this case, it is impossible to satisfy the condition no matter what, so print No.

Problem Statement

There are N points on a number line, numbered from 1 to N. The N points satisfy the following condition:

• The distance between point i and point i+1 is d_i. (1 \leq i \leq N - 1)

Find the minimum possible distance between point 1 and point N.

Constraints

• 2 \leq N \leq 1000
• 1 \leq d_i \leq 2000
• All input values are integers.

Sample Input 1

4
5 2 4

Sample Output 1

1

Let x_i be the coordinate of the point i. For example, (x_1,x_2,x_3,x_4)=(0,-5,-3,1) satisfies the condition, and in this case, the distance between point 1 and point 4 is 1.

Sample Input 2

10
314 159 265 358 979 323 846 264 338

Sample Output 2

2

Problem Statement

There are N real numbers x_1,\ldots,x_N between 0 (inclusive) and M (exclusive).

Among these N numbers, it is known that there are C_k numbers between k (inclusive) and k+1 (exclusive) for k=0,1,\ldots,M-1.

You are curious about how small the absolute difference between the median and the mean of x_1,\ldots,x_N can be.

Find the largest b such that the absolute difference between the median and the mean of x_1,\ldots,x_N cannot be smaller than b.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 0 \leq C_k
• C_0+\ldots+C_{M-1}=N
• All input values are integers.

Sample Input 1

3 3
0 1 2

Sample Output 1

0.0

For example, when x_1=1.5, x_2=2, x_3=2.5, the median and the mean of these numbers are both 2, and the absolute difference is 0.
Since the absolute difference cannot be smaller than 0, the largest b such that the absolute difference between the median and the mean cannot be smaller than b is 0.

Sample Input 2

4 5
2 1 0 0 1

Sample Output 2

0.25

For example, when x_1=4, x_2=1-2\times 10^{-100}, x_3=0, x_4=2-2\times 10^{-100}, the median is 1.5-2\times 10^{-100}, the mean is 1.75-10^{-100}, and the absolute difference is 0.25+10^{-100}.
As seen here, the absolute difference between the median and the mean can be slightly larger than 0.25, but we can prove that it cannot be smaller than 0.25. Therefore, the answer is 0.25.

Sample Input 3

10 10
1 0 0 0 0 0 0 0 0 9

Sample Output 3

0.4

Your output will be considered correct if the absolute or relative error from the true answer is at most 10^{-6}.

Problem Statement

You are given integers N, A, and B. Solve the following problem.

An arithmetic sequence S = (S_1, S_2, \dots, S_N) of length N is defined as S_i = A \times (i - 1) + B.
Find the number of prime numbers in S.

Constraints

• All input values are integers.
• 1 \le N \le 5 \times 10^5
• 1 \le A \le 10^6
• 2 \le B \le 5 \times 10^{11}

Sample Input 1

10 3 4

Sample Output 1

4

S = (4, 7, 10, 13, 16, 19, 22, 25, 28, 31).
Among these are four prime numbers: 7, 13, 19, 31.

Sample Input 2

99 1 2

Sample Output 2

25

There are 25 prime numbers not greater than 100.

Sample Input 3

314159 265358 499999999999

Sample Output 3

23166