Problem Statement

Does 2^n \gt n^2 hold?

Constraints

• n is an integer between 1 and 10^9 (inclusive).

Sample Input 1

5

Sample Output 1

Yes

Since 2^5=32,\ 5^2=25, we have 2^n \gt n^2, so Yes should be printed.

Sample Input 2

2

Sample Output 2

No

For n=2, we have 2^n=n^2=2^2, so 2^n \gt n^2 does not hold. Thus, No should be printed.

Sample Input 3

623947744

Sample Output 3

Yes

Problem Statement

The magnitude of an earthquake is a logarithmic scale of the energy released by the earthquake. It is known that each time the magnitude increases by 1, the amount of energy gets multiplied by approximately 32.
Here, we assume that the amount of energy gets multiplied by exactly 32 each time the magnitude increases by 1. In this case, how many times is the amount of energy of a magnitude A earthquake as much as that of a magnitude B earthquake?

Constraints

• 3\leq B\leq A\leq 9
• A and B are integers.

Sample Input 1

6 4

Sample Output 1

1024

6 is 2 greater than 4, so a magnitude 6 earthquake has 32\times 32=1024 times as much energy as a magnitude 4 earthquake has.

Sample Input 2

5 5

Sample Output 2

1

Earthquakes with the same magnitude have the same amount of energy.

Problem Statement

Takahashi has a string S consisting of lowercase English letters.

On this string, he will do the operation below just once.

• First, choose a non-negative integer K.
• Then, shift each character of S to the right by K (see below).

Here,

• a shifted to the right by 1 is b;
• b shifted to the right by 1 is c;
• c shifted to the right by 1 is d;
• \cdots
• y shifted to the right by 1 is z;
• z shifted to the right by 1 is a.

For example, b shifted to the right by 4 is f, and y shifted to the right by 3 is b.

You are given a string T. Determine whether Takahashi can make S equal T by the operation above.

Constraints

• Each of S and T is a string of length between 1 and 10^5 (inclusive) consisting of lowercase English letters.
• The lengths of S and T are equal.

Sample Input 1

abc
ijk

Sample Output 1

Yes

When Takahashi chooses K=8,

• a is shifted to the right by 8 and becomes i,
• b is shifted to the right by 8 and becomes j,
• c is shifted to the right by 8 and becomes k,

and now S and T are equal.
Therefore, he can make S equal T, so Yes should be printed.

Sample Input 2

z
a

Sample Output 2

Yes

Choosing K=1 makes S and T equal.
Note that the letter on the right of z is a.

Sample Input 3

ppq
qqp

Sample Output 3

No

There is no non-negative integer K that he can choose to make S equal T, so No should be printed.

Sample Input 4

atcoder
atcoder

Sample Output 4

Yes

Choosing K=0 makes S and T equal.

Problem Statement

We have 4 cards with an integer 1 written on it, 4 cards with 2, \ldots, 4 cards with N, for a total of 4N cards.

Takahashi shuffled these cards, removed one of them, and gave you a pile of the remaining 4N-1 cards. The i-th card (1 \leq i \leq 4N - 1) of the pile has an integer A_i written on it.

Find the integer written on the card removed by Takahashi.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq A_i \leq N \, (1 \leq i \leq 4N - 1)
• For each k \, (1 \leq k \leq N), there are at most 4 indices i such that A_i = k.
• All values in input are integers.

Sample Input 1

3
1 3 2 3 3 2 2 1 1 1 2

Sample Output 1

3

Takahashi removed a card with 3 written on it.

Sample Input 2

1
1 1 1

Sample Output 2

1

Sample Input 3

4
3 2 1 1 2 4 4 4 4 3 1 3 2 1 3

Sample Output 3

2

Problem Statement

You are given three sequences A=(A_1,\ldots,A_N), B=(B_1,\ldots,B_M), and C=(C_1,\ldots,C_L).

Additionally, a sequence X=(X_1,\ldots,X_Q) is given. For each i=1,\ldots,Q, solve the following problem:

Problem: Is it possible to select one element from each of A, B, and C so that their sum is X_i?

Constraints

• 1 \leq N,M,L \leq 100
• 0 \leq A_i, B_i ,C_i \leq 10^8
• 1 \leq Q \leq 2\times 10^5
• 0 \leq X_i \leq 3\times 10^8
• All input values are integers.

Sample Input 1

3
1 2 3
2
2 4
6
1 2 4 8 16 32
4
1 5 10 50

Sample Output 1

No
Yes
Yes
No

• It is impossible to select one element from each of A, B, and C so that their sum is 1.
• Selecting 1, 2, and 2 from A, B, and C, respectively, makes the sum 5.
• Selecting 2, 4, and 4 from A, B, and C, respectively, makes the sum 10.
• It is impossible to select one element from each of A, B, and C so that their sum is 50.

Problem Statement

There is an N\times N grid with horizontal rows and vertical columns, where all squares are initially painted white. Let (i,j) denote the square at the i-th row and j-th column.

Takahashi has integers A and B, which are between 1 and N (inclusive). He will do the following operations.

• For every integer k such that \max(1-A,1-B)\leq k\leq \min(N-A,N-B), paint (A+k,B+k) black.
• For every integer k such that \max(1-A,B-N)\leq k\leq \min(N-A,B-1), paint (A+k,B-k) black.

In the grid after these operations, find the color of each square (i,j) such that P\leq i\leq Q and R\leq j\leq S.

Constraints

• 1 \leq N \leq 10^{18}
• 1 \leq A \leq N
• 1 \leq B \leq N
• 1 \leq P \leq Q \leq N
• 1 \leq R \leq S \leq N
• (Q-P+1)\times(S-R+1)\leq 3\times 10^5
• All values in input are integers.

Sample Input 1

5 3 2
1 5 1 5

Sample Output 1

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

The first operation paints the four squares (2,1), (3,2), (4,3), (5,4) black, and the second paints the four squares (4,1), (3,2), (2,3), (1,4) black.
Thus, the above output should be printed, since P=1, Q=5, R=1, S=5.

Sample Input 2

5 3 3
4 5 2 5

Sample Output 2

#.#.
...#

The operations paint the nine squares (1,1), (1,5), (2,2), (2,4), (3,3), (4,2), (4,4), (5,1), (5,5).
Thus, the above output should be printed, since P=4, Q=5, R=2, S=5.

Sample Input 3

1000000000000000000 999999999999999999 999999999999999999
999999999999999998 1000000000000000000 999999999999999998 1000000000000000000

Sample Output 3

#.#
.#.
#.#

Note that the input may not fit into a 32-bit integer type.

Problem Statement

Given is a sequence of length N: A=(A_1,A_2,\ldots,A_N), and an integer K.

How many of the contiguous subsequences of A have the sum of K?
In other words, how many pairs of integers (l,r) satisfy all of the conditions below?

• 1\leq l\leq r\leq N
• \displaystyle\sum_{i=l}^{r}A_i = K

Constraints

• 1\leq N \leq 2\times 10^5
• |A_i| \leq 10^9
• |K| \leq 10^{15}
• All values in input are integers.

Sample Input 1

6 5
8 -3 5 7 0 -4

Sample Output 1

3

(l,r)=(1,2),(3,3),(2,6) are the three pairs that satisfy the conditions.

Sample Input 2

2 -1000000000000000
1000000000 -1000000000

Sample Output 2

0

There may be no pair that satisfies the conditions.

Problem Statement

AtCoder Inc. is planning to develop a product. The product has K parameters, whose values are currently all zero. The company aims to raise all parameter values to at least P.

There are N development plans. Executing the i-th development plan (1 \le i \le N) increases the value of the j-th parameter by A_{i,j} for every integer j such that 1 \le j \le K, at the cost of C_i.

A development plan cannot be executed more than once. Determine whether the company can achieve its goal, and if it can, find the minimum total cost required to achieve the goal.

Constraints

• 1 \le N \le 100
• 1 \le K,P \le 5
• 0 \le A_{i,j} \le P(1 \le i \le N,1 \le j \le K)
• 1 \le C_i \le 10^9(1 \le i \le N)
• All input values are integers.

Sample Input 1

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

Sample Output 1

9

If you execute the first, third, and fourth development plans, each parameter will be 3+2+0=5,0+4+1=5,2+0+4=6, all of which are at least 5, so the goal is achieved. The total cost in this case is 5 + 3 + 1 = 9.

It is impossible to achieve the goal at a total cost of 8 or less. Thus, the answer is 9.

Sample Input 2

7 3 5
85 1 0 1
37 1 1 0
38 2 0 0
45 0 2 2
67 1 1 0
12 2 2 0
94 2 2 1

Sample Output 2

-1

You cannot achieve the goal no matter what you do. Thus, print -1.

Problem Statement

You will play a game against a dealer. The game uses a D-sided die (dice) that shows an integer from 1 to D with equal probability, and two variables x and y initialized to 0. The game proceeds as follows:

• You may perform the following operation any number of times: roll the die and add the result to x. You can choose whether to continue rolling or not after each roll.

• Then, the dealer will repeat the following operation as long as y < L: roll the die and add the result to y.

• If x > N, you lose. Otherwise, you win if y > N or x > y and lose if neither is satisfied.

Determine the probability of your winning when you act in a way that maximizes the probability of winning.

Constraints

• All inputs are integers.
• 1 \leq L \leq N \leq 2 \times 10^5
• 1 \leq D \leq N

Sample Input 1

3 2 2

Sample Output 1

0.468750000000000

It can be proved that the optimal strategy is to continue rolling as long as x is not greater than 2.

Sample Input 2

200000 200000 200000

Sample Output 2

0.999986408692793