You are given an array of $$$n$$$ integers, and you will perform $$$k$$$ operations on it.
Each operation consists of replacing each element with the sum of all the other elements. In particular, all of the following will occur simultaneously:
- For each index $$$i$$$, the element $$$a_i$$$ will be replaced with $$$a_1 + \dots + a_{i-1} + a_{i+1} + \dots + a_n$$$.
For example, applying the operation to the array $$$[1, 3, 5, 4]$$$ gives $$$[3+5+4, 1+5+4, 1+3+4, 1+3+5] = [12,10,8,9]$$$.
After applying $$$k$$$ operations to the array, find the maximum difference between any two elements of the resulting array. (The difference between two numbers $$$a$$$ and $$$b$$$ is defined as $$$|a-b|$$$.)
The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.
The first line of each test case contains two space-separated integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq k \leq 10^9$$$) — the size of the array. The second line of each test case contains $$$n$$$ space-separated integers $$$a_1$$$, $$$a_2$$$, $$$\dots$$$, $$$a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the elements of the array.
The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, output one integer — the maximum difference between any two elements of the resulting array.
3 4 1 1 3 5 4 1 1000 2020 10 100000 1 1 1 1 1 1 1 1 1 1
4 0 0
The first test case is described in the statement. The maximum difference occurs between the numbers $$$8$$$ and $$$12$$$.
In the second test case, there is only one number in the array, so the answer will be $$$0$$$ (regardless of the value of $$$k$$$).
There is a grid of arrows with $$$n$$$ rows and $$$m$$$ columns. A move consists of swapping two adjacent arrows that point at each other. (Two cells are adjacent if they share a side.) What is the maximum number of moves that can be performed?
The input consists of a single test case. The first line of each test case consists of two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 1000$$$) — the number of rows and the number of columns in the grid, respectively.
The next $$$n$$$ lines each contain a string of length $$$m$$$. Each character of this string is one of the characters $$$\texttt{ \lt }$$$, $$$\texttt{ \gt }$$$, $$$\texttt{v}$$$, $$$\texttt{^}$$$, representing an arrow pointing left, right, down, and up, respectively.
Output a single integer — the maximum number of moves that can be performed.
3 3 ^v< v^> ><>
2
6 4 >>vv >>vv >>vv ^^<< ^^<< ^^<<
0
In the second test case, there is no pair of adjacent cells in the grid that contain arrows pointing at each other, so the answer is $$$0$$$.
You are given a rearrangement of the string abcdefghijklmnopqrstuvwxyz. Call it $$$s$$$. You can perform the following operation on $$$s$$$ as many times as you want:
- Sort any substring of $$$s$$$ in increasing order. (Recall that $$$a$$$ is a substring of $$$b$$$ if $$$a$$$ can be obtained by deleting some (possibly zero) characters from the beginning and end of $$$b$$$.)
The string is called easy if you can delete some of the characters in $$$s$$$ to make $$$s$$$ equal to the string ezpc. Is it possible to make $$$s$$$ easy after some (possibly zero) operations?
The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 5000$$$) — the number of test cases.
The only line of each test case consists of a single string $$$s$$$ — the initial string. $$$s$$$ is a rearrangement of the string abcdefghijklmnopqrstuvwxyz.
For each test case, output YES if it is possible to make $$$s$$$ easy after some (possibly zero) operations. Otherwise, output NO.
3 ezpcabdfghijklmnoqrstuvwxy zaepbcdfghijklmnoqrstuvwxy orzgvlkbenwyqjmdfsctxhiaup
YES YES NO
In the first test case, $$$s$$$ is already easy (so you don't need to perform any operations). You can delete the last $$$22$$$ characters of $$$s$$$, and you will be left with the string ezpc.
In the second test case, you can make $$$s$$$ easy with one operation: zaepcbdefgh... $$$\rightarrow$$$ aezpbcdefgh....
Now, you can delete the first character, the fourth character, and the last $$$20$$$ characters in $$$s$$$ to make the string ezpc: _ezp_c___.... Here the deleted letters are represented with _.
It can be shown that it is impossible to make the string in the third test case easy.
There are $$$n^2$$$ points on the coordinate plane, at the locations $$$$$$ \begin{matrix} (1,1), & (1,2), & \cdots & (1,n), \\ (2,1), & (2,2), & \cdots & (2,n), \\ \vdots & \vdots & \ddots & \vdots \\ (n,1), & (n,2), & \cdots & (n,n). \\ \end{matrix} $$$$$$ More formally, the initial set of points $$$S = \{(i,j) \mid 1 \leq i, j \leq n\}$$$.
You want to move each point to a different point such that
- the distance each point moves is at least $$$\sqrt{d}$$$, and
- the set of resulting points equals the set of initial points. That is, after all the points have moved, they occupy the same locations as before. (More formally, the final set of points equals $$$S$$$.)
Given $$$n$$$ and $$$d$$$, find any such movement or report that it does not exist.
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 150$$$) — the number of test cases.
The only line of each test case contains two space-separated integers $$$n$$$ and $$$d$$$ ($$$2 \leq n \leq 300$$$, $$$1 \leq d \leq 10^9$$$) — the range of points and the square of the minimum distance each point must move, respectively.
The sum of $$$n$$$ over all test cases does not exceed $$$300$$$.
For each test case, if such a movement is impossible, output NO.
Otherwise, output YES followed by $$$n^2$$$ lines. Each line should contain four space separated integers $$$x_i$$$, $$$y_i$$$, $$$x'_i$$$, $$$y'_i$$$ ($$$1 \leq x_i, y_i, x'_i, y'_i \leq n$$$), representing that the point $$$(x_i, y_i)$$$ moves to the point $$$(x'_i, y'_i)$$$. The resulting points should satisfy the conditions in the problem statement.
If there are multiple possible movements, print any of them.
5 2 1 2 2 2 3 4 1 5 15
YES 1 1 1 2 1 2 2 2 2 2 2 1 2 1 1 1 YES 1 1 2 2 1 2 2 1 2 1 1 2 2 2 1 1 NO YES 1 1 1 2 1 2 1 1 1 3 1 4 1 4 1 3 2 1 2 2 2 2 2 1 2 3 2 4 2 4 2 3 3 1 3 2 3 2 3 1 3 3 3 4 3 4 3 3 4 1 4 2 4 2 4 1 4 3 4 4 4 4 4 3 NO
The picture below shows the movement for the first test case. Each point moves at least $$$\sqrt{1}$$$ units, and the set of resulting points is the set of initial points.
You are given two strings $$$s$$$ and $$$t$$$. An operation consists of the following:
- pick two characters in different positions, replace one of them with o, and replace the other one with any lowercase English letter.
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases.
The first line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 2000$$$) — the length of $$$s$$$ and $$$t$$$.
The next two lines contain the strings $$$s$$$ and $$$t$$$ of length $$$n$$$, consisting of lowercase English letters. Additional constraint on the input: $$$s \neq t$$$.
For each test case, output YES if it is possible to turn $$$s$$$ into $$$t$$$ using these operations. Otherwise, output NO. You can print each letter of YES and NO in any case (upper or lower).
2 3 qrs orz 4 ezpc icpc
YES NO
In the first test case, we can pick the characters q and s in qrs, turn q into o, and turn s into z. The resulting string is orz.
In the second test case, it can be shown that it is impossible to turn $$$s$$$ into $$$t$$$.
You are given an integer $$$n$$$. Output any string of lowercase English letters with length at most $$$300$$$ that has exactly $$$n$$$ palindromic substrings.
Recall that $$$p$$$ is a substring of $$$q$$$ if $$$p$$$ can be obtained by removing several characters (possibly none) from the beginning and from the end of $$$q$$$. Also recall that a palindrome is a string that reads the same backwards as forwards. For example, aba and o are palindromes, but ab and aaba are not.
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 5 \cdot 10^3$$$) — the number of test cases.
The only line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^4$$$).
For each test case, output one string of lowercase English letters with length at most $$$300$$$ that has exactly $$$n$$$ palindromic substrings.
We have a proof that, under the given constraints, such a string always exists.
6 1 11 12 13 21 25
o kannawoah abacaba feelssadman howtomakegoodsamples anutforajaroftuna
You have an infinitely long digital panel. Each digit consists of $$$7$$$ segments, which can be turned on or off to display different numbers. The picture shows how all $$$10$$$ decimal digits are displayed.
In this picture, the segments that are turned on are marked black. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.
The only line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$).
The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, output two space-separated positive integers — the minimum and maximum possible values of the number on the panel, respectively.
3 2 3 4
1 1 7 7 4 11
By turning on two segments, the only number you can display is $$$1$$$.
By turning on three segments, the only number you can display is $$$7$$$.
By turning on four segments, the smallest number you can display is $$$4$$$ and the largest number you can display is $$$11$$$.
There are $$$n$$$ stacks of apples, and the $$$i$$$th stack has $$$a_i$$$ apples.
You can shoot an arrow at any nonempty stack. As a result, the number of apples in the stack undergoes one of the following events with equal probability ($$$50\%$$$ chance):
- The number of apples decreases by $$$1$$$, or
- the number of apples becomes $$$0$$$.
Every time you have a choice of which stack to shoot at, you will always shoot at the stack that minimizes the expected value of the total number of arrows you fire. Find the expected value of the number of arrows you fire (until all stacks are empty).
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.
The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the number of stacks of apples.
The next line of each test case contains $$$n$$$ space-separated integers $$$a_1, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the number of apples in each stack.
The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, output one real number — the expected number of arrows you fire.
Your answer will be considered correct if its absolute or relative error doesn't exceed $$$\mathbf{10^{-4}}$$$. Namely, if your answer is $$$a$$$, and the jury's answer is $$$b$$$, then your answer is accepted if and only if $$$\frac{|a-b|}{\max (1,|b|)} \leq 10^{-4}$$$.
2 4 1 1 1 1 1 2
4.0000 1.5000
In the first test case, no matter which stack you fire at, the resulting number of apples will be $$$0$$$. Therefore, you will always use four arrows.
In the second test case, there is an equal probability of using $$$1$$$ or $$$2$$$ arrows.
Given two integers $$$a$$$ and $$$b$$$, find any nonnegative integer $$$x$$$ such that $$$x \text{ OR } a = x \text{ XOR } b$$$, or determine that none exist.
Here $$$\text{OR}$$$ represents the bitwise OR operation and $$$\text{XOR}$$$ represents the bitwise XOR operation.
The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases.
The only line of each test case contains two integers $$$a$$$ and $$$b$$$ ($$$1 \leq a, b \leq 10^{18}$$$) — the values given.
For each test case, output any nonnegative integer $$$x$$$ ($$$0 \leq x \leq 10^{18}$$$) such that $$$x \text{ OR } a = x \text{ XOR } b$$$. If no such $$$x$$$ exist, output $$$-1$$$.
7 1 1 10 3 10 12 9 15 15 8 12 1 19 1
0 -1 -1 -1 7 -1 18