A time of day is represented by three integers: hours, minutes, and seconds. A time is called good if one of these integers equals the sum of the other two.
Given two times on the same day in the 24-hour format, count the good times between them, including both endpoints.
There is only one test case in each test file.
The first line contains three integers $$$h_1$$$, $$$m_1$$$, and $$$s_1$$$ ($$$0\le h_1\le23$$$, $$$0\le m_1,s_1\le59$$$), representing the hours, minutes, and seconds of the starting time, respectively.
The second line contains three integers $$$h_2$$$, $$$m_2$$$, and $$$s_2$$$ ($$$0\le h_2\le23$$$, $$$0\le m_2,s_2\le59$$$), representing the hours, minutes, and seconds of the ending time, respectively.
It is guaranteed that the starting time is no later than the ending time.
Print one integer: the number of good times.
0 2 00 3 0
1
1 45 461 46 45
2
23 36 5923 36 59
1
In the first example, the only good time is $$$00{:}02{:}02$$$, since $$$0+2=2$$$, so the answer is $$$1$$$.
In the second example, the good times are $$$01{:}45{:}46$$$ and $$$01{:}46{:}45$$$, so the answer is $$$2$$$.
Decimal digits can be formed using matchsticks as shown below. Each dark segment represents one matchstick. The digits $$$0,1,2,3,4,5,6,7,8,9$$$ require $$$6,2,5,5,4,5,6,3,7,6$$$ matchsticks, respectively.
Figure: Matchstick representations of decimal digits
For a positive integer $$$x$$$, let $$$g(x)$$$ be the total number of matchsticks needed to form its decimal representation without leading zeros. Starting with the given positive integer $$$x$$$, perform the assignment $$$x=g(x)$$$ exactly $$$10$$$ times, and denote the final value of $$$x$$$ by $$$f(x)$$$.
Given positive integers $$$a$$$ and $$$b$$$, find
$$$$$$\sum_{x=a}^{b} f(x) \bmod (10^9+7)$$$$$$.
Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \le T \le 1000$$$). Description of the test cases follows.
The first line contains a positive integer $$$a$$$ ($$$1 \le a \lt 10^{1000}$$$), without leading zeros.
The second line contains a positive integer $$$b$$$ ($$$a \le b \lt 10^{1000}$$$), without leading zeros.
The sum of the lengths of the decimal representations of $$$a$$$ and $$$b$$$ over all test cases does not exceed $$$2000$$$.
For each test case, output one line containing the answer.
Print the required sum modulo $$$10^9 + 7$$$.
2110137284
51758
For the first test case:
For $$$x=1,2,3,5,7,8,10$$$, we have $$$f(x)=5$$$; for $$$x=4$$$, we have $$$f(x)=4$$$; and for $$$x=6,9$$$, we have $$$f(x)=6$$$. Thus the answer for this test case is $$$7\cdot5+4+2\cdot6=51$$$.
There are $$$n$$$ cells in a row, represented by a binary string $$$s$$$ of length $$$n$$$: 0 denotes white and 1 denotes black.
In one operation, you may toggle the color of one cell. You may perform at most $$$b$$$ operations. A black segment is a maximal nonempty contiguous segment of black cells. Find the minimum possible number of black segments after the operations.
Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \le T \le 10000$$$). Description of the test cases follows.
The first line contains two integers $$$n$$$ and $$$b$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le b \le n$$$).
The second line contains a binary string $$$s$$$ of length $$$n$$$.
The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, output one line containing the answer.
Print one integer: the minimum possible number of black segments.
49 21110101117 010101015 30010012 2011010001101
1402
In the first test case, changing cells $$$4$$$ and $$$6$$$ to black produces 111111111, which has one black segment.
In the second test case, no operation is allowed, so the four original black segments remain.
In the third test case, changing the only black cell to white removes all black segments.
In the fourth test case, changing cells $$$4$$$ and $$$11$$$ to black leaves two black segments, achieving the optimum $$$2$$$.
Alice and Bob play exactly $$$k$$$ rounds on a string $$$s$$$ of length $$$n$$$ consisting of lowercase English letters. In each round, Alice first chooses to delete either the leftmost or the rightmost character of the current string. Bob then chooses one of the two ends of the remaining string and deletes the character at that end.
The final string has length $$$n-2k$$$. Its score is the number of palindromic substring occurrences. A substring is a contiguous sequence of characters, and a palindrome reads the same forwards and backwards. Single-character substrings count, and equal substrings at different positions are counted separately.
Alice wants to maximize the score, while Bob wants to minimize it. Both players see the current string and play optimally. Determine the final score.
Each test file contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1\le T\le10^4$$$). The description of the test cases follows.
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$3\le n\le10^6$$$, $$$1\le k$$$, $$$2k \lt n$$$).
The second line contains a string $$$s$$$ of length $$$n$$$, consisting only of lowercase English letters.
For each test file, it is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.
For each test case, print the final score under optimal play on a separate line.
86 1xabbay7 2cababac6 1aaaaaa5 1abcba3 1abc7 1abababa8 3aaaabbbb9 2abacabcaa
541031926
In the first test case, $$$s=\texttt{xabbay}$$$ and $$$k=1$$$. The possible remaining strings of length $$$4$$$ are xabb, abba, and bbay, with palindromic substring counts $$$5,6,5$$$, respectively. Optimal play results in a score of $$$5$$$.
There are $$$n$$$ mining sites and $$$m$$$ bidirectional pipes. The sites are numbered from $$$1$$$ to $$$n$$$. Site $$$i$$$ has elevation $$$h_i$$$, worker count $$$p_i$$$, and evacuation capacity $$$c_i$$$.
You must choose a nonnegative integer water level $$$h$$$. Every site with $$$h_i\le h$$$ and every pipe incident to such a site are deleted, and workers at deleted sites cannot evacuate. The remaining sites and pipes form connected components.
For each connected component, let its total worker count be $$$s_p$$$ and its total evacuation capacity be $$$s_c$$$. If $$$s_p\le s_c$$$, all $$$s_p$$$ workers in that component evacuate successfully; otherwise, evacuation fails for the entire component and none of its workers evacuate.
You may choose the water level freely. Find the maximum number of workers that can evacuate.
There is only one test case in each test file.
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n\le2\cdot10^5$$$, $$$0\le m\le2\cdot10^5$$$).
The $$$i$$$-th of the next $$$n$$$ lines contains three integers $$$h_i$$$, $$$p_i$$$, $$$c_i$$$ ($$$1\le h_i\le10^9$$$, $$$0\le p_i,c_i\le10^9$$$). Different sites may have the same elevation.
Each of the next $$$m$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1\le u,v\le n$$$, $$$u\ne v$$$), describing a bidirectional pipe between these sites. There are no multiple edges or self-loops.
Print one integer: the maximum total number of workers that can evacuate.
4 31 100 03 10 505 30 107 5 101 22 33 4
45
5 56 3 52 8 29 5 64 4 16 2 41 22 32 43 54 5
14
Figure: Components and evacuation results at different water levels
In the first example, with $$$h=0$$$, the only component has $$$145$$$ workers and capacity $$$70$$$, so none evacuate. With $$$h=2$$$, the remaining sites have $$$45$$$ workers and capacity $$$70$$$, so all evacuate. With $$$h=4$$$, the remaining component has $$$35$$$ workers and capacity $$$20$$$, so none evacuate. With $$$h=6$$$, only site $$$4$$$ remains and $$$5$$$ workers evacuate. The maximum is $$$45$$$.
In the second example, choosing $$$h=2$$$ leaves site $$$1$$$ as one component, with $$$3$$$ workers and capacity $$$5$$$. Sites $$$3,4,5$$$ form another component, with $$$11$$$ workers and capacity $$$11$$$. The maximum number of workers evacuated is therefore $$$14$$$.
You are given an integer matrix $$$a$$$ with $$$m$$$ rows and $$$n$$$ columns. Both row and column indices start at $$$1$$$.
Choose two rows $$$x_1 \lt x_2$$$ and two columns $$$y_1 \lt y_2$$$ to form a subrectangle. It is a fitting rectangle if its top-left and bottom-right entries satisfy
$$$$$$a_{x_1,y_1}+a_{x_2,y_2}=(x_2-x_1)+(y_2-y_1)$$$$$$.
Count the fitting rectangles. Two rectangles are different if and only if their corresponding tuples $$$(x_1,x_2,y_1,y_2)$$$ differ.
There is only one test case in each test file.
The first line contains two integers $$$m$$$ and $$$n$$$ ($$$2\le m,n\le1500$$$, $$$m\cdot n\le10^6$$$).
Each of the next $$$m$$$ lines contains $$$n$$$ integers. The $$$j$$$-th integer on the $$$i$$$-th line is $$$a_{i,j}$$$ ($$$0\le a_{i,j}\le m+n$$$).
Print one integer: the number of fitting rectangles.
3 41 0 2 10 2 1 01 0 3 2
4
2 21 11 1
1
In the first example, the four fitting rectangles have top-left and bottom-right corner pairs $$$(1,3),(2,4)$$$; $$$(1,1),(3,3)$$$; $$$(1,2),(3,3)$$$; and $$$(2,1),(3,3)$$$.
In the second example, the matrix has only two rows and two columns. Since $$$x_1 \lt x_2$$$ and $$$y_1 \lt y_2$$$ must hold, the selected rows must be the first and second rows, and the selected columns must be the first and second columns. Thus there is only one subrectangle. It satisfies $$$1+1=2$$$, so the answer is $$$1$$$.
A crane boom is a line segment with one endpoint fixed at the origin. It may rotate continuously around the origin, and its length may vary continuously within $$$[l,r]$$$.
There are $$$n$$$ axis-aligned rectangular restricted zones. The boom may touch their boundaries, but no part of the segment may intersect the interior of any zone. Zones may intersect or contain one another. The origin is not in the interior of any zone.
A state is described by the position of the boom's other endpoint. Given valid initial and target states, determine whether the boom can move continuously from the initial state to the target state while remaining valid at every moment.
Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \le T \le 10000$$$). Description of the test cases follows.
The first line contains three integers $$$n$$$, $$$l$$$, $$$r$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le l \le r \le 10^9$$$).
The second line contains four integers $$$s_x$$$, $$$s_y$$$, $$$t_x$$$, $$$t_y$$$ ($$$-10^9 \le s_x,s_y,t_x,t_y \le 10^9$$$). The initial endpoint is $$$(s_x,s_y)$$$, and the target endpoint is $$$(t_x,t_y)$$$. It is guaranteed that the boom does not intersect the interior of any restricted zone in either the initial or the target state, and its length in both states belongs to $$$[l,r]$$$.
The $$$i$$$-th of the next $$$n$$$ lines contains four integers $$$x_{1,i}$$$, $$$y_{1,i}$$$, $$$x_{2,i}$$$, $$$y_{2,i}$$$ ($$$-10^9 \le x_{1,i} \lt x_{2,i} \le 10^9$$$, $$$-10^9 \le y_{1,i} \lt y_{2,i} \le 10^9$$$), describing a zone with opposite corners $$$(x_{1,i},y_{1,i})$$$ and $$$(x_{2,i},y_{2,i})$$$. The origin is not in the interior of any zone.
The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, output one line containing the answer.
Print Yes if the target state is reachable, and No otherwise.
42 5 105 0 -5 0-1 1 1 4-1 -4 1 -12 1 106 0 -6 0-2 2 2 4-2 -4 2 -24 4 125 3 -3 -71 5 4 8-6 2 -2 5-5 -4 -2 -15 -6 8 -32 0 65 0 -5 0-2 0 2 3-2 -3 2 0
NoYesYesYes
Figure: Forbidden zones and boom motion in the four sample cases
In the first test case, even at the minimum length, the upper zone blocks counterclockwise rotation from the positive horizontal axis to the negative horizontal axis, and the lower zone blocks rotation in the other direction.
In the second test case, contract the boom to length $$$2$$$, rotate below the origin toward the target, and extend to length $$$6$$$.
In the third test case, contract the boom to length $$$4$$$, rotate clockwise to the target direction, and extend to the target position. This path avoids the interior of every forbidden zone.
In the fourth test case, the two forbidden zones meet along a horizontal boundary containing the origin. The origin lies on their shared boundary, outside both forbidden interiors. The boom can contract to length $$$0$$$ and then extend toward the target, staying on the shared boundary during contraction and extension.
There are $$$n$$$ lights in a circle, numbered from $$$1$$$ to $$$n$$$ clockwise. Light $$$i$$$ initially has state $$$a_i$$$: 0 means off and 1 means on.
In one operation, choose a starting light $$$i$$$, pay $$$c_i$$$, and toggle exactly $$$k$$$ consecutive lights clockwise starting from it. Toggling changes 0 to 1 and 1 to 0; light $$$n$$$ is followed by light $$$1$$$. Any number of operations, including zero, is allowed.
Find the minimum total cost to turn all lights off.
Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \le T \le 10000$$$). Description of the test cases follows.
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$).
The second line contains a binary string $$$a$$$ of length $$$n$$$. Its $$$i$$$-th character is the initial state of light $$$i$$$.
The third line contains $$$n$$$ integers $$$c_1,c_2,\ldots,c_n$$$ ($$$1 \le c_i \le 10^9$$$), giving the operation cost for each starting position.
The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, output one line containing the answer.
Print one integer: the minimum total cost to turn all lights off.
If there is no solution, print a single integer $$$-1$$$.
45 2001109 4 7 1 84 210001 1 1 16 2110000100 1 1 1 1 11 101000000000
7-150
In the first test case, starting at light $$$3$$$ toggles lights $$$3$$$ and $$$4$$$ and costs $$$7$$$.
In the second test case, each operation toggles $$$2$$$ lights, so the parity of the number of lights that are on does not change. Initially, $$$1$$$ light is on, so it is impossible to turn all lights off.
In the third test case, operating once from each of lights $$$2,3,4,5,6$$$ costs $$$5$$$, whereas operating from light $$$1$$$ costs $$$100$$$.
In the fourth test case, the only light is initially off. No operations are needed, so the minimum cost is $$$0$$$.
You are given two integer arrays $$$a$$$ and $$$b$$$, both of length $$$n$$$. In one operation, choose two adjacent elements of the current array $$$a$$$. If their sum is a multiple of $$$3$$$, swap them.
Determine whether $$$a$$$ can be transformed into $$$b$$$ using any number of operations, including zero.
Each test file contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1\le T\le1000$$$). The description of the test cases follows.
The first line contains an integer $$$n$$$ ($$$1\le n\le5\cdot10^5$$$).
The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$0\le a_i\le10^9$$$).
The third line contains $$$n$$$ integers $$$b_1,b_2,\ldots,b_n$$$ ($$$0\le b_i\le10^9$$$).
For each test file, it is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5\cdot10^5$$$.
For each test case, print Yes on a separate line if $$$a$$$ can be transformed into $$$b$$$, and No otherwise.
531 2 42 1 420 33 031 4 24 1 230 1 33 1 031 2 11 1 2
YesYesNoNoYes
In the first test case, swapping the first two elements gives the target array, since $$$1+2=3$$$.
In the fourth test case, the middle element cannot be swapped with either neighbor, so the two end elements cannot be exchanged.
Initially, a rooted tree contains only its root, whose depth is $$$1$$$. A child's depth is $$$1$$$ greater than its parent's depth. A vertex without children is a leaf.
In each round, every leaf with depth less than $$$k$$$ independently chooses one action: it adds one child with probability $$$\alpha$$$, adds two children with probability $$$\beta$$$, or adds no children with probability $$$1-\alpha-\beta$$$.
Choices are independent between vertices and between rounds. All participating leaves act simultaneously, and new vertices can first act in the next round. A leaf that adds no children may still participate in later rounds; vertices of depth $$$k$$$ never participate.
Find the expected total number of vertices after $$$n$$$ rounds, including the root, modulo $$$M=998~244~353$$$.
Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \le T \le 10000$$$). Description of the test cases follows.
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$0 \le n \le 10^{18}$$$, $$$1 \le k \le 10^6$$$).
The second line contains two numbers $$$\alpha$$$ and $$$\beta$$$ ($$$0 \le \alpha,\beta \le 1$$$, $$$\alpha + \beta \le 1$$$), each with exactly four digits after the decimal point, representing the probabilities of adding one and two children, respectively.
The sum of $$$k$$$ over all test cases does not exceed $$$10^6$$$.
For each test case, output one line containing the answer.
Output the expected total number of vertices after $$$n$$$ rounds modulo $$$998~244~353$$$.
Formally, let $$$M = 998~244~353$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$z$$$ that $$$0 \le z \lt M$$$ and $$$z \cdot q \equiv p \pmod{M}$$$.
22 20.2500 0.25008 50.5000 0.2500
873463811454218250
In the first test case, $$$\alpha=\beta=1/4$$$ and $$$k=2$$$, so only the root can act. If it adds one or two children in the first round, the final number of vertices is $$$2$$$ or $$$3$$$, respectively. If it adds no children in the first round, it tries to grow again in the second round. Thus the expectation is
$$$$$$\frac14\cdot2+\frac14\cdot3+\frac12\left(\frac14\cdot2+\frac14\cdot3+\frac12\cdot1\right)=\frac{17}{8}$$$$$$.
The modular encoding of $$$\frac{17}{8}$$$ is $$$873463811$$$.
You are given $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ and two integers $$$m$$$ and $$$k$$$. For each position $$$i$$$, independently choose an integer $$$d_i$$$ ($$$0\le d_i\le k$$$) and replace its value with $$$a_i+d_i$$$.
For every $$$0\le s \lt 2^m$$$, count the choices satisfying
$$$$$$(a_1+d_1)\oplus\cdots\oplus(a_n+d_n)=s$$$$$$.
Here, $$$\oplus$$$ denotes the bitwise XOR operation. Write the two nonnegative integers in binary and pad them with leading zeros to the same length. For each position, the resulting bit is $$$1$$$ if the two corresponding bits differ, and $$$0$$$ if they are equal. For example, $$$(0011)_2\oplus(0101)_2=(0110)_2$$$.
Two choices are different if and only if the chosen increments differ at at least one position. Print all answers modulo $$$998~244~353$$$.
There is only one test case in each test file.
The first line contains three integers $$$n$$$, $$$m$$$, $$$k$$$ ($$$1\le n\le500000$$$, $$$1\le m\le19$$$, $$$0\le k\le100$$$). It is guaranteed that $$$2^m-k \gt 0$$$.
The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$0\le a_i \lt 2^m-k$$$).
Print $$$2^m$$$ integers. The $$$j$$$-th integer is the number of choices for $$$s=j-1$$$, modulo $$$998~244~353$$$.
2 2 10 1
1 1 1 1
3 3 20 1 3
3 2 2 2 4 4 5 5
In the first example, the first number can become $$$0$$$ or $$$1$$$, and the second can become $$$1$$$ or $$$2$$$. The four choices give XOR values $$$1,2,0,3$$$, so all answers are $$$1$$$.