Given a sequence of length $$$n$$$, you need to select a number of mutually disjoint intervals from it such that the sum of the intervals divided by the number of intervals is maximized. Output the maximum value and the maximum number of intervals that can be selected in this case.
An interval can be obtained by deleting zero or more integers from the beginning and zero or more integers from the end of the sequence.
It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{x}{y}$$$ where $$$x$$$ and $$$y$$$ are integers and $$$y \not\equiv 0\pmod{10^{18} + 9}$$$. Output the integer equal to $$$x\cdot y^{-1}\pmod {10^{18} + 9}$$$.
In other words, output such an integer $$$a$$$ that $$$0 \leq {a} \lt 10^{18} + 9$$$ and $$$a\cdot y \equiv x \pmod{10^{18} + 9}$$$.
Each test contains multiple test cases. The first line contains a single integer t $$$(1\leq{t}\leq{10^6})$$$— the number of test cases. The description of the test cases follows.
The first line of each test case contains $$$1$$$ integer $$$n(1\leq{n}\leq{10^6})$$$.
The second line contains $$$n$$$ integers $$$a_1,a_2,a_3,...,a_n(-10^6\leq{a_i}\leq{10^6})$$$ representing the sequence.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.
For each test case, output the maximum value and the maximum number of intervals that can be selected in this case.
4 4 4 1 -5 3 3 1 -1 1 2 1 1 2 -1 -1
5 1 1 2 2 1 1000000000000000008 2
In the last test case, the optimal strategy is to choose the intervals [$$$1$$$,$$$1$$$] and [$$$2$$$,$$$2$$$]. The maximum value is $$$\frac{((-1)+(-1))}{2} = -1$$$ and two intervals are chosen .
You are given five positive integers: $$$x,y,z,k,d$$$. In each turn, you can choose one of the following two operations:
- Multiply $$$x$$$ by $$$k$$$ and add $$$d$$$ to $$$y$$$: $$$x = x \times k,~y = y + d$$$;
- Multiply $$$y$$$ by $$$k$$$ and add $$$d$$$ to $$$x$$$: $$$y = y \times k,~x = x + d$$$;
Your task is to calculate the minimum number of turns required to make $$$x \times y\ge z$$$.
The only line contains five positive integers $$$x,y,z,k,d~(1\le x,y,z,d\le 10^{12},~2\le k\le 10^{12})$$$.
For each set of input data, output a single number — the minimum number of turns required to make $$$x \times y\ge z$$$.
1 2 40 2 2
2
You have an array $$$a$$$ of $$$n$$$ integers. You need to answer how many intervals there are where at least one number occurs an odd number of times in this interval.
An interval can be obtained by deleting zero or more integers from the beginning and zero or more integers from the end of the array.
Each test consists of several test cases. The first line contains a single integer $$$t(1\leq{t}\leq{10^6})$$$—the number of test cases. Then follows the description of the test cases.
The first line of each test case contains an integer $$$n(1\leq{n}\leq{10^6})$$$ — the length of the sequence.
The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n(1\leq{a_i}\leq{10^6})$$$ — the array $$$a$$$ itself.
It is guaranteed that the sum of the value of $$$n$$$ for all test cases does not exceed $$$10^6$$$.
For each test, output a single integer, the number of eligible intervals.
2 4 1 1 1 1 5 1 2 3 2 3
6 14
Inspired by a concept from Belmaxii, Clamee formulated the following problem:
You have a string p which is composed of the pattern "xtu" repeated $$$n$$$ times, and another string $$$q$$$ which is made up of lowercase letters. The task is to determine the number of times the string $$$q$$$ appears as a subsequence within the given string $$$p$$$.
A string $$$s$$$ is considered a subsequence of string $$$t$$$ if it can be obtained by removing some (potentially none) characters from $$$t$$$. Subsequences are distinct if a character present at a certain position in $$$t$$$ is excluded in one subsequence but included in another.
Each test is comprised of multiple test cases. The initial line presents an integer $$$T~(1\le T \le 10^5)$$$, which is the tally of test cases.
In each of the subsequent $$$T$$$ lines, you will find an integer $$$n~(1\le n \le 10^{18})$$$, representing the number of repetitions, followed by a string $$$q~(1\le |q| \le 3\cdot n, 1\le \sum |q| \le 10^6)$$$. The string $$$q$$$ consists of lowercase letters.
For each test case, you are to output a single line containing the count of occurrences of the string q, computed modulo $$$998244353$$$.
5 1 t 114514 xtuxtu 3 xtuxt 1919810 utx 19260817 xtc
1 564946452 6 607962364 0
In the third test case, the given string $$$p$$$ is "xtuxtuxtu",the given string $$$q$$$ is "xtuxt" you can choose subsequence following:
xtuxtuxtu
xtuxtuxtu
xtuxtuxtu
xtuxtuxtu
xtuxtuxtu
xtuxtuxtu
Xiangtan University is gearing up for an election to choose its student union president. The candidates are Donald Trump and Joe Biden. The university is divided into $$$n$$$ electoral constituencies. The i-th constituency possesses $$$a_i$$$ votes. In this electoral system, the candidate who secures the majority in a constituency seizes all the votes from that particular constituency.
As a student at Xiangtan University, Clamee has been provided with the information regarding the number of votes in each constituency. He is curious to know whether any legal difference in the number of votes can definitively determine the result in each electoral constituency without ambiguity. In other words, she wants to understand if the vote count differences are sufficient to ensure a unique election outcome in every single constituency.
The initial line of the input provides a single integer $$$n~(1\le n \le 10^5)$$$, indicating the total number of electoral constituencies.
The following line lists $$$n$$$ integers: $$$a_1, a_2, \ldots, a_n~(1 \le a_i,~\sum{a_i} \le 2^{31}-1, )$$$, each representing the vote count for the ith electoral constituency.
For each test case, output "YES" (without quotes) if all legal difference in the number of votes can uniquely determine the outcome of each electoral constituency, and "NO" (without quotes) otherwise.
4 1 2 3 4
NO
4 114 515 1919 810
YES
In the first test case, $$$+1+2-3+4=-1-2+3+4=4$$$, so the answer is "NO".
In the second test case, all legal difference in the number of votes can uniquely determine the outcome of each electoral constituency, so the answer is "YES".
Given four rectangles, can you piece them together without overlap to form a perfect square?
The first line contains an integer $$$T~(1 \le T \le 1000)$$$, representing the number of test cases.
Each subsequent test case spans four lines, with each line containing two integers $$$a,b~(1 \le a , b \le 10^4)$$$, indicating the length and width of a rectangle, respectively.
Output the result of each case line by line. If it can be formed, print "Yes"; otherwise, print "No".
2 1 1 1 2 1 3 2 5 1 4 1 4 1 4 1 4
No Yes
Please note the special memory limit for this problem.
This problem is adapted from Paper Grading.
Nearly all the students in No.84 University are asked to take a compulsory course called JL and pass the exam, which says that hundreds of students will take part in this final exam together. The teacher organizing the course is always trying to find a more efficient and fair way to grade students' test papers. In this year, you are appointed to write a program to grade papers.
Now you are given the Book of Requirement which is a dictionary consists of $$$n$$$ strings in lowercase letters, denoted by $$$s_1,s_2,\ldots,s_n$$$ in order. However, any character in the dictionary can now be changed. For example, for the string "aabbc". if we change its third character to "c", the string will become "aacbc".
The scoring criterion is given as follow. A student and his/her test paper are described as a string $$$q$$$ in lowercase letters together with two integral coefficients $$$l$$$ and $$$r$$$ . The student's final score should be the number of strings $$$s_i$$$ in the Book of Requirement with $$$l\le i \le r$$$ such that $$$s_i$$$ has a prefix equals to $$$q$$$ .
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n,m \le 10^5$$$) where $$$n$$$ is the number of strings in the Book of Requirement and $$$m$$$ is the total number of modifications and students.
The following $$$n$$$ lines are $$$n$$$ non-empty strings $$$s_1,s_2,\ldots,s_n$$$ indicating all string in the book, whose total length is up to $$$10^5$$$.
Then the following $$$m$$$ lines describe all modifications and students that are asked to grade in time sequence. Each line of them starts with an integer $$$opt (1 \le opt \le 2)$$$. If $$$opt=1$$$, it follows two integers $$$i , j$$$ and one character $$$c$$$ describing a modification to replace the $$$j$$$-th character of the $$$i$$$-th string in the book with $$$c$$$, where $$$1 \le i \le n$$$ and $$$1 \le j \le len(i)$$$ . $$$len(i)$$$ means the length of $$$i$$$-th string , and $$$c$$$ is a lowercase character.
If $$$opt=2$$$ , it follows a non-empty string $$$q$$$ and two non-negative integers $$$l'$$$ and $$$r'$$$, where $$$1 \le l' \le r' \le n$$$.
To get the real $$$l$$$ and $$$r$$$ representing a student as above, you need to apply formula below
- $$$l' = \big((l' \oplus LastAns) \bmod n\big)+1 $$$
- $$$r' = \big((r' \oplus LastAns) \bmod n\big)+1 $$$
- $$$l = min(l',r')$$$
- $$$r = max(l',r')$$$
The variable $$$LastAns$$$ represents the answer obtained from the most recent operation $$$2$$$ and is initialized to $$$0$$$.
It is guaranteed that the total length of $$$q$$$ provided in the input is up to $$$10^5$$$ .
For each student, output a single line containing the score of his/her test paper.
3 3 aaa bbb aac 2 aab 1 3 1 1 3 b 2 aab 1 3
0 1
This problem is an enhanced edition of the "Planar" problem from the HNOI2010.
You are given $$$n$$$ pairs of numbers, where the i-th pair is $$$(x_i,y_i)$$$.
Construct a undirected graph according to the following method:
$$$\forall i,j\in [1,n]$$$, there is an edge between node $$$i$$$ and node $$$j$$$ if and only if either $$$x_i \lt x_j \lt y_i \lt y_j$$$ or $$$x_j \lt x_i \lt y_j \lt y_i$$$.
Determine if this graph is a bipartite graph.
A graph is bipartite if and only if it does not contain an odd cycle.
Each test consists of multiple test cases. The initial line presents a single integer $$$T~(1\le T\le 10^5)$$$ , which denotes the quantity of test cases
In the context of each test instance, the initial line presents a single integer $$$n~(1\le n,\sum n\le 5 \cdot 10^5)$$$, representing the quantity of pairs to be evaluated. Subsequently, $$$n$$$ lines follow, with each delineating the specifics of a distinct pair. On the i-th line, a pair of integers $$$x_i,~y_i~(1\le x_i\le y_i \le 10^{18})$$$ is provided.
If the graph is bipartite, print "YES". Otherwise, print "NO".
2 3 1 4 2 5 3 6 3 1 2 3 4 5 6
NO YES
You have a permutation $$$P$$$ consisting of $$$n$$$ unique numbers ranging from $$$0$$$ to $$$n-1$$$, inclusive. The set $$$P$$$ is defined as $$$P = \{p_1, p_2, \ldots, p_n\}$$$. The function $$$mex(S)$$$ is introduced to find the smallest non-negative integer that is not contained within a subset $$$S$$$ of $$$P$$$. For any interval $$$[i, j]$$$ within $$$P$$$, where $$$1 \le i \le j \le n$$$, the function $$$g(i, j)$$$ is defined as the mex of the subset of $$$P$$$ formed by the elements $$$p_i, p_{i+1}, \ldots, p_j$$$. Your goal is to determine the total count of intervals $$$[i, j]$$$ such that $$$g(i, j) = k$$$, where k is a non-negative integer.
To illustrate this with an example, consider $$$n = 5$$$ and $$$P = \{0, 1, 2, 3, 4\}$$$. We are interested in finding the number of intervals where $$$g(i, j) = 1$$$. The only interval that satisfies $$$g(0,0) = 1$$$ is $$$[0,0]$$$.
The initial line of the input presents an integer $$$t~(1 \le t \le 10^4)$$$, which denotes the quantity of test cases. For each test case, the first line introduces a single integer $$$n~(2 \le n \le 10^6)$$$, representing the size of the permutation. Subsequently, the second line contains $$$n$$$ unique integers, ranging from $$$0$$$ to $$$n-1$$$, representing the permutation $$$P$$$.
It is assured that the cumulative total of $$$n$$$ values across all test cases will not surpass $$$1,000,000$$$.
For each test case, you are required to output $$$n+1$$$ integers. These integers represent the solutions for $$$k$$$, ranging from $$$0$$$ to $$$n$$$.
1 5 0 1 2 3 4
10 1 1 1 1 1
Given $$$n$$$ points on a one-dimensional coordinate system, the coordinates of the $$$i$$$-th point are $$$x_i$$$ and the weights are $$$v_i$$$.The $$$n$$$ points are numbered $$$1$$$ through $$$n$$$ in the order of the sample inputs. Define $$$f(i,j)$$$ as the cost of traveling from the $$$i$$$-th point to the $$$j$$$-th point.
$$$f(i,j)=\left\{ \begin{matrix} x_i-x_j+v_i-v_j~,&x_i \gt x_j \\ x_j-x_i+v_j-v_i~,&x_i \lt x_j \end{matrix} \right. $$$
You need to visit all the points exactly once, starting at point $$$1$$$ and ending at point $$$n$$$. You need to answer the minimum total cost of all access sequences, and how many different access sequences can achieve this cost.
The number of legal access sequences may be large, so output the number of legal access sequences modulo $$$998244353$$$.
Each test contains multiple test cases. The first line contains a single integer $$$t~(1\leq{t}\leq{5\cdot 10^3})$$$—the number of test cases. The description of the test cases follows.
Each test case consists of three lines.
The first line of each test case contains a single integer $$$n~(2\leq{n}\leq{5\cdot 10^3})$$$.
The second line of each test case contains $$$n$$$ distinct integers $$$x_1,x_2,...,x_n~(1\leq{x_i}\leq{10^9})$$$.
The third line of each test case contains $$$n$$$ integers $$$v_1,v_2,...,v_n~(1\leq{v_i}\leq{10^9})$$$.
It is guaranteed that the sum of the values of $$$n$$$ for all sets of input data does not exceed $$$5\cdot 10^3$$$.
For each test case, output the minimum total cost of all access sequences, and how many different access sequences can achieve this cost.
3 5 1 2 3 4 5 7 2 3 5 1 5 5 3 4 1 2 7 8 6 5 7 10 75 52 80 73 77 34 96 15 16 24 4 10 13 35 10 19 87 34 93 41
-2 1 7 1 78 16
Xiangtan University students absolutely adore the pig's trotter rice from Lianjian, which is a dish composed of pig's trotters and rice. They currently offer $$$n$$$ varieties of pig's trotter rice, with the deliciousness level of the i-th variety being $$$a_i$$$.
For these $$$n$$$ varieties of pig's trotter rice, there is a concept known as the discord degree $$$D$$$. The discord degree is calculated by sorting all the deliciousness levels from smallest to largest, and then taking the maximum difference between consecutive items, as follows
$$$$$$D = \max\big\{a_2-a_1,~a_3-a_2,~\ldots~,~a_n-a_{n-1}\big\}$$$$$$
You, as a prospective seller of pig's trotter rice at Lianjian, do not wish for the discord degree $$$D$$$ of all the pig's trotter rice you sell to be too high. Therefore, you are considering introducing new combinations of pig's trotters and rice. You currently have $$$X$$$ types of pig's trotters, with the deliciousness level of the i-th type being $$$x_i$$$, and $$$Y$$$ types of rice, with the deliciousness level of the j-th type being $$$y_j$$$.
You can create a new variety of pig's trotter rice by choosing any one type of pig's trotter and any one type of rice. For example, if you select the i-th type of pig's trotter and the j-th type of rice, the deliciousness level of the new combination would be $$$x_i \times y_j$$$.
Now, you want to calculate the minimum possible discord degree $$$D$$$ after adding any number of new combinations of pig's trotters and rice.
The problem consists of a single test case, with the first line containing three integers, $$$n~(2 \le n \le 10^3)$$$,$$$~X,~Y,~(1 \le ~X,~Y \le 10^{3})$$$; the second line contains $$$n$$$ integers $$$a_i,~(1 \le a_i \le 10^{6})$$$; the third line contains $$$X$$$ integers $$$x_i,~(1 \le x_i \le 10^{6})$$$; and the fourth line contains $$$Y$$$ integers $$$y_i,~(1 \le y_i \le 10^{6})$$$.
It is guaranteed that the sum of $$$n,~X,~Y$$$ does not exceed $$$10^3$$$.
3 3 3 11 45 14 191 98 10 192 608 17
31