Problem Statement

There is a bus stop where buses depart at X minutes past each hour. For example, if X=10, buses depart at 0:10, 1:10, \ldots, and 23:10. No buses depart at any other time.

It is currently M minutes past H (M\neq X). How many minutes are left before the next bus departs?

Constraints

• 0\leq H \leq 23
• 0\leq X,M \leq 59
• X\neq M
• All input values are integers.

Sample Input 1

30 14 10

Sample Output 1

20

It is 14:10 now. The next bus departs at 14:30, which is 20 minutes from now.

Sample Input 2

12 23 30

Sample Output 2

42

It is 23:30 now. The next bus departs at 0:12 on the next day, which is 42 minutes from now.

Sample Input 3

1 17 34

Sample Output 3

27

Problem Statement

Takahashi made (N - 1) transactions at a bank.

The transactions are described by integers A_1, A_2, \ldots, A_N. The i-th transaction is a deposit of (A_{i + 1} - A_i) yen if A_i < A_{i + 1}, and a withdrawal of (A_i - A_{i + 1}) yen if A_i > A_{i + 1}. (Yen is a currency of Japan.) Here, it is guaranteed that the given input satisfies A_i \neq A_{i + 1}.

Find the total amounts of money deposited and withdrawn through these transactions.

Constraints

• 2 \leq N \leq 100
• 0 \leq A_i \leq 10^7
• A_i \neq A_{i + 1}
• All input values are integers.

Sample Input 1

4
2 9 5 8

Sample Output 1

10 4

• The 1-st transaction is a 9 - 2 = 7 yen deposit, as 2 < 9.
• The 2-st transaction is a 9 - 5 = 4 yen withdrawal, as 9 > 5.
• The 3-st transaction is a 8 - 5 = 3 yen deposit, as 5 < 8.

Thus, a total of 10 yen was deposited, and 4 yen was withdrawn.

Sample Input 2

5
10 8 6 4 2

Sample Output 2

0 8

Problem Statement

A good number is defined as follows.

• A positive integer x is said to be a good number if and only if:
  • every pair of adjacent digits in x has a difference of 1 or less.
  • Formally, if x has k digits and its decimal representation is d_1d_2 \dots d_k, then |d_i - d_{i+1}| \le 1 for all integers i with 1 \le i < k.

For example, 1,56,777, and 3234 are good numbers, but 13,1235, and 909 are not.

A goodish number is defined as follows.

• A positive integer x is said to be a goodish number if and only if:
  • one can modify at most one digit of x to make it a good number. Here, it is disallowed to produce a leading zero.
  • Formally, if x has k digit and its decimal representation is d_1d_2 \dots d_k, there exists an integer pair (p,q) such that:
    • 1 \le p \le k,
    • 0 \le q \le 9,
    • (p,q) \neq (1,0), and
    • setting d_p in x to q makes x a good number.
  • Note that a good number is always a goodish number.

For example, given 7176, one can set d_2 to 8 to make it 7876, which is a good number, so 7176 is a goodish number.

Given an integer N, determine if N is a goodish number.

Constraints

• N is an integer such that 1 \le N < 10^{18}.

Sample Input 1

7176

Sample Output 1

Yes

This is the same as the example in the problem statement.

Sample Input 2

2020

Sample Output 2

No

2020 is not a goodish number.

Sample Input 3

3728

Sample Output 3

No

Sample Input 4

987654321012345678

Sample Output 4

Yes

N may not fit into a 32-bit signed integer.
Also, N itself may be a good number.

Problem Statement

N teams competed in a programming contest.
The contest lasted T minutes.
Team i solved A_i problems, and the last acceptance time was B_i.

In this contest, the ranks are determined as follows:

• Those who solved more problems rank higher.
• Among those with the same number of solved problems, those with earlier last acceptance time rank higher.
• Among those with the same number of solved problems and last acceptance time, those with a smaller team number rank higher.

Let A' be the number of problems solved by the team ranked first, and B' be its last acceptance time.
Find the following value G_i for each team.

• G_i = T \times (A' - A_i) + (B_i - B')

Constraints

• All input values are integers.
• 1 \le N \le 1000
• 1 \le T \le 1000
• 1 \le A_i \le 1000
• 1 \le B_i \le T

Sample Input 1

6 120
3 80
4 90
5 120
5 100
3 110
4 70

Sample Output 1

220
110
20
0
250
90

Six teams participated in this contest, and it lasted 120 minutes.
The first-ranked team is team 4, which solved five problems and the last acceptance time is 100.
Therefore, G_i is calculated as follows.

• G_1 = 120 \times (5-3) + (80-100) = 220
• G_2 = 120 \times (5-4) + (90-100) = 110
• G_3 = 120 \times (5-5) + (120-100) = 20
• G_4 = 120 \times (5-5) + (100-100) = 0
• G_5 = 120 \times (5-3) + (110-100) = 250
• G_6 = 120 \times (5-4) + (70-100) = 90

Problem Statement

You want to implement a C-like comment-out system.

You are given a length-N string S consisting of /, *, and lowercase English letters.
You are asked to perform the following procedure against S.

1. Prepare a variable x that takes on an integer value. x is initialized with 1.
2. Seek for an n such that:
   • x \leq n \leq |S| - 1; and
   • the n-th character of S is / and the (n + 1)-th character of S is *.
3. If no n satisfies the conditions in step 2, terminate the procedure. Otherwise, let i be the smallest such n.
4. Seek for an n such that:
   • i + 2 \leq n \leq |S| - 1; and
   • the n-th character of S is * and the (n + 1)-th character of S is /.
5. If no n satisfies the conditions in step 4, terminate the procedure. Otherwise, let j be the smallest such n.
6. Remove the i-th through (j + 1)-th characters of S, concatenate the remaining strings without changing the order, and set S to the resulting string. Set x to i, and go back to step 2.

Print S resulting from the procedure.

Constraints

• 1 \leq N \leq 10^6
• S is a length-N string consisting of /, *, and lowercase English letters.
• N is an integer.

Sample Input 1

7
a/*b*/c

Sample Output 1

ac

In this description, we denote the n-th character of S by S_n.
The procedure proceeds as follows.

• Initially, S = a/*b*/c and x = 1.
• Seek for an n satisfying the conditions in step 2. n = 2 satisfies x \leq n \leq |S|-1, S_{n} = /, and S_{n+1} = *, and is the minimum n that satisfies these conditions. Thus, let i = 2.
• Seek for an n satisfying the conditions in step 4. n = 5 satisfies i + 2 \leq n \leq |S| - 1, S_{n} = *, and S_{n+1} = /, and is the minimum n that satisfies these conditions. Thus, let j = 5.
• Remove the i = 2-nd through j + 1 = 6-th characters of S, concatenate the remaining strings without changing the order, and set S to the resulting string. Now S is ac. Set x to 2, and go back to step 2.
• Seeking for an n satisfying the conditions in step 2, one finds that there is no such n. Thus, the procedure terminates here.

At the end of the procedure, S results in ac, which should be printed.

Sample Input 2

10
/*a*//*b*/

Sample Output 2

At the end of the procedure, S may result in an empty string.

Sample Input 3

18
/*/a/*b*/c/*d*/e*/

Sample Output 3

ce*/

Problem Statement

You are lining up dominoes.

N clues are given: for each 1 \leq i \leq N, if domino S_i falls, then domino T_i will also fall.

Determine if the given clues imply that if domino X falls, then domino Y will also fall.

Constraints

• 1 \leq N \leq 2\times 10^5
• N is an integer.
• Each of S_i,T_i,X, and Y is a string of length between 1 and 100, inclusive, consisting of lowercase English letters.
• X \neq Y
• S_i \neq T_i for all i.
• (S_i,T_i) are distinct.

Sample Input 1

5
second fourth
first second
second third
third fourth
fourth fifth
fifth sixth

Sample Output 1

Yes

The second clue states that if domino second falls, then domino third will also fall; and the third clue states that if domino third falls, then domino fourth will also fall.
Thus, we can infer that if domino second falls, then domino fourth will also fall.

Sample Input 2

5
fourth second
first second
second third
third fourth
fourth fifth
fifth sixth

Sample Output 2

No

One cannot infer from the given clues that if domino fourth falls, then domino second will also fall.

Sample Input 3

6
e d
a b
b a
a c
c d
d e
e a

Sample Output 3

Yes

Sample Input 4

1
a b
x y

Sample Output 4

No

Problem Statement

You are given an N-by-N matrix A. The element in the i-th row and j-th column of A is denoted by A(i,j). Exactly one element of A is 0, and each of the other (N^2-1) elements is an integer between 1 and N.

How many ways are there to replace the only element 0 in A with an integer between 1 and N, inclusive, such that the resulting A satisfies the following condition?

• A(A(i,j),k)=A(i,A(j,k)) for all 1\leq i,j,k\leq N.

Constraints

• 1\leq N \leq 300
• 0\leq A(i,j)\leq N
• There is exactly one occurrence of 0 in A(i,j)\ (1\leq i,j\leq N).
• All input values are integers.

Sample Input 1

3
1 2 3
2 0 1
3 1 2

Sample Output 1

1

Since A(2,2) is 0, we consider replacing it with each integer between 1 and 3.

• If A(2,2) becomes 1: it does not satisfy the condition. For (i,j,k)=(2,2,3), we have A(A(i,j),k)=3 but A(i,A(j,k))=2.
• If A(2,2) becomes 2: it does not satisfy the condition. For (i,j,k)=(3,3,2), we have A(A(i,j),k)=2 but A(i,A(j,k))=3.
• If A(2,2) becomes 3: it satisfies the condition. A(A(i,j),k)=A(i,A(j,k)) for all 1\leq i,j,k\leq N.

Thus, the answer is 1.

Sample Input 2

3
2 1 0
1 2 3
1 3 2

Sample Output 2

0

Sample Input 3

6
4 5 5 2 4 2
5 2 2 4 5 4
5 2 0 4 5 4
2 4 4 5 2 5
4 5 5 2 4 2
2 4 4 5 2 5

Sample Output 3

2

Problem Statement

You are given an integer S, and N integers a_1,a_2,\dots,a_N.
Can you construct a mathematical expression that evaluates to S using +, \times, and the N integers?
Here,

• use each of the N integers exactly once.
• You can freely rearrange the integers.
• You may not use parentheses.
• You may not join integers without an operator in between (for example, join 1 and 2 to form 12).

Constraints

• 2 \leq N \leq 6
• 1 \leq S \leq 10^{18}
• 1 \leq a_i \leq 1000
• All input values are integers.

Sample Input 1

3 11
1 2 5

Sample Output 1

Yes
1+2x5

The expression 1 + 2 \times 5 satisfies the conditions in the problem statement, so you may print this.
The expression 2 \times 5 + 1 also satisfies the conditions, so printing it is also accepted.

Sample Input 2

5 2
1 1 1 1 1

Sample Output 2

Yes
1+1x1x1x1

If the same integer occurs in a_1, a_2, \dots, a_N multiple times, use it as many times as it occurs.

Sample Input 3

2 12
1 2

Sample Output 3

No

Sample Input 4

6 302934
614 490 585 613 420 945

Sample Output 4

Yes
420+490x613+585+614+945

Problem Statement

AtCoderLand has N islands: island 1, island 2, \ldots, and island N, and M roads: road 1, road 2, \ldots, and road M. Road i connects island A_i and island B_i bidirectionally. Road i\ (1\leq i\leq M) will be submerged on day D_i, so it will not be available on or after day D_i.

The islands are said to be connected if one can travel between any pair of islands via available roads. On day 0 (when no road is submerged), the islands are connected. Find the integer X such that the islands are connected on day (X-1) but not on day X.

Constraints

• 2\leq N\leq2\times10 ^ 5
• N-1\leq M\leq2\times10 ^ 5
• 1\leq A _ i\leq B _ i\leq N\ (1\leq i\leq M)
• 1\leq D _ i\leq10 ^ 9\ (1\leq i\leq M)
• The islands are initially connected.
• All input values are integers.

Sample Input 1

5 6
1 2 10
1 3 25
2 3 35
2 4 15
3 4 30
4 5 40

Sample Output 1

25

The islands of AtCoderLand are illustrated in the figure below:

On day 24, the islands are connected.

On day 25, road 2 will be submerged, making it impossible to travel between, for instance, island 1 and island 2.

Thus, 25 should be printed.

Sample Input 2

3 4
1 2 31
2 3 4
2 3 15
3 3 9

Sample Output 2

15

There may be a road that leads from an island to itself, or multiple roads between the same pair of islands.

Sample Input 3

15 20
6 7 54
5 15 63
8 14 30
5 8 52
5 9 96
1 13 51
8 13 89
4 15 81
12 12 80
4 10 48
1 11 63
1 9 72
10 14 83
3 5 30
7 12 60
1 10 60
2 11 68
5 7 52
6 12 34
1 8 41

Sample Output 3

30

Problem Statement

There are 3N people numbered from 1 to 3N. Person i has A_i yen (currency in Japan).
You are going to group the 3N people into N groups of three people each. Let S_i be the total amount of yen in the i-th group.
Find the minimum possible \displaystyle \max_{1 \leq k \leq N} S_k - \min_{1 \leq k \leq N}S_k.

Constraints

• 2 \leq N \leq 5
• 0 \leq A_i \leq 10^8
• All input values are integers.

Sample Input 1

2
1 3 4 6 2 9

Sample Output 1

1

If you group person 1, person 2, and person 6 into group 1, and person 3, person 4, and person 5 into group 2, then

• S_1 = 1 + 3 + 9 = 13,
• S_2 = 4 + 6 + 2 = 12,
• \displaystyle \max_{1 \leq k \leq N} S_k - \min_{1 \leq k \leq N}S_k = 13 - 12 = 1.

No grouping makes \displaystyle \max_{1 \leq k \leq N} S_k - \min_{1 \leq k \leq N}S_k less than 1, so the answer is 1.

Sample Input 2

2
0 0 0 0 0 100000000

Sample Output 2

100000000

Sample Input 3

5
614 490 420 945 613 585 760 38 926 725 667 685 449 455 873

Sample Output 3

35

Problem Statement

There is an N-vertex tree whose vertices are numbered 1 through N. The i-th edge connects vertex u_i and vertex v_i bidirectionally. Vertex i has an integer A_i written on it.

Determine if there is a way to choose K vertices among the N so that no pair of chosen vertices are adjacent. If there is, find the maximum sum of integers written on the chosen K vertices.

Constraints

• 2\leq N\leq 100
• 1\leq K \leq N
• 1\leq u_i,v_i\leq N
• 1\leq A_i \leq 100
• The input graph is a tree.
• All input values are integers.

Sample Input 1

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

Sample Output 1

9

It is optimal to choose vertex 3 and vertex 5.

Sample Input 2

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

Sample Output 2

34

Sample Input 3

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

Sample Output 3

-1

There is no conforming choice.

Problem Statement

A length-k sequence A=(A_1,\ldots,A_k) is a zigzag sequence if:

• A_1 < A_2> A_3 < A_4 > \ldots , or

• A_1 > A_2 < A_3 > A_4 <\ldots .

More formally, a sequence is said to be a zigzag sequence if and only if:

• A_i \neq A_{i+1}\ (1\leq i \leq k-1), and
• (A_{i+1}-A_i)(A_i-A_{i-1}) < 0\ (2\leq i \leq k-1).

Especially, note that a sequence of length one is always a zigzag sequence.

Given a length-N sequence B=(B_1,\ldots,B_N), find the maximum length of a subsequence of B that is a zigzag sequence.

Constraints

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

Sample Input 1

7
5 1 2 3 4 3 3

Sample Output 1

4

The subsequence (5,2,4,3) of B is a zigzag sequence of length 4.

Sample Input 2

5
1 2 3 4 5

Sample Output 2

2

Problem Statement

You are given an N-vertex M-edge simple directed graph. The vertices are numbered 1 through N, and the edges are numbered 1 through M. Edge j directs from vertex U_j to vertex V_j. Each vertex has an integer attribute point: the point of vertex i is P_i. Also, each edge has a real attribute decay between 0 and 1: the decay of edge j is W_j. It is guaranteed that the given graph does not have a closed cycle. (In other words, there is no way to travel from a vertex i along edges to go back to vertex i.)

Takahashi is going to play a game on this graph. Initially, vertex 1 has a piece on it, and Takahashi's score is 0. He performs the following procedure to move the piece to vertex N while accumulating his score.

1. Let i be the current number of vertex with the piece. Add the point P_i of vertex i to his score.
2. If i=N, he ends the game successfully.
3. If there is no edge going from vertex i, he ends the game unsuccessfully. Otherwise, choose an edge going from vertex i.
4. Let j be the number of the chosen edge. Multiply the point of each vertex by the decay of edge j. In other words, let P_i \leftarrow P_i\times W_j for each i\ (1\leq i\leq N).
5. Move the piece to vertex V_j, and jump to step 1.

Determine if he can end the game successfully. If it is possible, print the maximum possible final score of the game.

Constraints

• N,M,P_i,U_j, and V_j are integers.
• 2\leq N \leq 10^5
• 1\leq M \leq 10^5
• 1\leq P_i\leq 10^4
• U_j \neq V_j
• (U_j,V_j)\neq (U_k, V_k)\ (j\neq k)
• 0\leq W_j\leq 1
• W_j is a multiple of 10^{-6} and given with six decimal places.
• The given graph does not have a directed cycle.

Sample Input 1

4 4
2 5 3 1
1 3 0.500000
1 2 0.250000
2 3 0.250000
3 4 0.500000

Sample Output 1

3.7500000000

We denote the sequence (P_1,P_2,P_3,P_4) simply by P. Initially, P=(2,5,3,1).

If he moves the piece along vertices 1\rightarrow 3\rightarrow 4, the game proceeds as follows.

1. Add the point P_1=2 of vertex 1 to his score.
2. Among the edges going from vertex 1, choose edge 1.
3. Multiply the point of each vertex by the decay W_1=0.5 of edge 1. Now, P=(1,2.5,1.5,0.5).
4. Move the piece to vertex V_1=3.
5. Add the point P_3=1.5 of vertex 3 to his score.
6. Among the edges going from vertex 3, choose edge 4.
7. Multiply the point of each vertex by the decay W_4=0.5 of edge 4. Now, P=(0.5,1.25,0.75,0.25).
8. Move the piece to vertex V_4=4.
9. Add the point P_4=0.25 of vertex 4 to his score.
10. He ends the game successfully.

In this case, the final score is 2+1.5+0.25=3.75, which is maximum possible.

Sample Input 2

3 1
1 1 1
1 2 0.000000

Sample Output 2

-1

He cannot end the game successfully.

Sample Input 3

6 12
22 75 26 45 72 81
4 6 0.185514
3 6 0.758252
2 3 0.622989
2 4 0.984614
1 3 0.465086
1 5 0.396959
5 3 0.618272
5 2 0.016128
1 2 0.869673
1 4 0.363219
2 6 0.097935
5 4 0.877468

Sample Output 3

138.6258141601

Problem Statement

You are given a length-N sequence A=(A _ 1,A _ 2,\ldots,A _ N) of non-negative integers, and a real value x strictly greater than 0 and less than or equal to 1.

For an integer pair (l,r)\ (1\leq l\leq r\leq N), we define f(l,r) as follows:

Answer Q queries. In the i-th query (1\leq i\leq Q), given an integer pair (l _ i,r _ i)\ (1\leq l _ i\leq r _ i\leq N), find f(l _ i,r _ i).

Constraints

• 1\leq N\leq2\times10 ^ 5
• 0\leq A _ i\leq10 ^ 9\ (1\leq i\leq N)
• 0\lt x\leq 1
• 1\leq Q\leq2\times10 ^ 5
• 1\leq l _ i\leq r _ i\leq N\ (1\leq i\leq Q)
• N,A _ i,Q,l _ i, and r _ i are integers.
• x is a real value with at most 15 decimal places.

Sample Input 1

7
3 1 4 1 5 9 2
0.25
4
1 3
3 6
1 7
2 2

Sample Output 1

3.5
4.703125
3.54443359375
1

For each query, the answer is as follows.

• f(1,3)=A _ 1\times0.25 ^ 0+A _ 2\times0.25 ^ 1+A _ 3\times0.25 ^ 2=3+0.25+0.25=3.5.
• f(3,6)=A _ 3\times0.25 ^ 0+A _ 4\times0.25 ^ 1+A _ 5\times0.25 ^ 2+A _ 6\times0.25 ^ 3=4+0.25+0.3125+0.140625=4.703125.
• f(1,7)=A _ 1\times0.25 ^ 0+A _ 2\times0.25 ^ 1+A _ 3\times0.25 ^ 2+A _ 4\times0.25 ^ 3+A _ 5\times0.25 ^ 4+A _ 6\times0.25 ^ 5+A _ 7\times0.25 ^ 6=3+0.25+0.25+0.015625+0.01953125+0.0087890625+0.00048828125=3.54443359375.
• f(2,2)=A _ 2\times0.25 ^ 0=1.

Since your answer is considered correct if the relative or absolute error is at most 10 ^ {-6}, output like

3.5
4.703125
3.54443359375
0.999999

and

3.4999965
4.703129703125
3.54443004931640625
1.000001

are also accepted.

Sample Input 2

15
6 45 81 83 28 40 31 30 51 31 59 50 94 36 0
0.998244353
20
1 2
1 5
1 10
2 5
2 10
3 3
3 8
3 12
4 4
4 14
5 5
5 11
5 13
5 14
6 7
7 7
8 10
10 13
10 14
12 14

Sample Output 2

50.920995885
242.004326432639783195178618854259
422.764240065920208662445303267128
236.419395434977014285377699356
417.497217803865912440022892137641
81
292.066191815728552247199317241863
480.544234637661958884554506013369
83
528.144974561396676686531955107577
28
268.416129630805326045766513470066
410.492717775411750526215653552396
445.927866482402907904585917660160
70.945574943
31
111.801707440188046879
233.226782486727123857410847838
268.974634315843968519190799533618
179.708673560669989924

Problem Statement

A 4\times 4 grid is said to be good if it is in the following state:

For every integer i between 1 and 15, inclusive, there is exactly one cell with that integer written on it.
No other cell has something written on it. In other words, there is exactly one cell with nothing written on it.

You are given two distinct good grids S and T.
Here, the good grid S is given by 16 integers S_{i,j} (1\leq i,j\leq 4).
If 1\leq S_{i,j}\leq 15, it means that the cell in the i-th row from the top and j-th column from the left has S_{i,j} written on it;
if S_{i,j}=-1, it means that the cell in the i-th row from the top and j-th column from the left has nothing written on it.
Likewise, T is given by 16 integers T_{i,j} (1\leq i,j\leq 4).

Find the minimum number of times of performing the following operation to make the grid equal to T, starting from S.
If the grid cannot be made equal to T with 30 operations or less (including the case where any number of operations can do so), print -1 instead.

• Choose a cell adjacent to the cell with nothing written on it, and write the integer written on the chosen cell to the empty cell. Then, erase the integer written on the chosen cell.

Constraints

• -1\leq S_{i,j},T_{i,j}\leq 15
• S_{i,j},T_{i,j}\neq 0
• S and T are distinct good grids.
• All input values are integers.

Sample Input 1

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 -1
1 2 3 4
5 6 -1 8
9 10 7 11
13 14 15 12

Sample Output 1

3

We denote by (i,j) the cell in the i-th row from the top and j-th column from the left in the grid.
In S, the empty cell is (4,4).
One can perform three operations to obtain T.

• Choose (3,4). Write 12 to (4,4), and erase the integer written on (3,4).
• Choose (3,3). Write 11 to (3,4), and erase the integer written on (3,3).
• Choose (2,3). Write 7 to (3,3), and erase the integer written on (2,3).

On the other hand, one cannot obtain T with two operations or less, so print 3.

Sample Input 2

-1 11 10 9
1 12 15 8
2 13 14 7
3 4 5 6
6 5 4 3
7 12 15 2
8 13 14 1
9 10 11 -1

Sample Output 2

-1

One cannot obtain T with 30 operations or less, so print -1.

Sample Input 3

1 12 11 10
2 13 -1 9
3 14 15 8
4 5 6 7
1 10 5 14
2 11 6 15
3 12 7 -1
4 13 8 9

Sample Output 3

30