The only difference between the two versions is that in this version $$$n \leq 1000$$$ and the sum of $$$n$$$ over all test cases does not exceed $$$1000$$$.
A terminal is a row of $$$n$$$ equal segments numbered $$$1$$$ to $$$n$$$ in order. There are two terminals, one above the other.
You are given an array $$$a$$$ of length $$$n$$$. For all $$$i = 1, 2, \dots, n$$$, there should be a straight wire from some point on segment $$$i$$$ of the top terminal to some point on segment $$$a_i$$$ of the bottom terminal. You can't select the endpoints of a segment. For example, the following pictures show two possible wirings if $$$n=7$$$ and $$$a=[4,1,4,6,7,7,5]$$$.
A crossing occurs when two wires share a point in common. In the picture above, crossings are circled in red.
What is the maximum number of crossings there can be if you place the wires optimally?
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.
The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 1000$$$) — the length of the array.
The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — the elements of the array.
The sum of $$$n$$$ across all test cases does not exceed $$$1000$$$.
For each test case, output a single integer — the maximum number of crossings there can be if you place the wires optimally.
474 1 4 6 7 7 522 11132 2 2
6 1 0 3
The first test case is shown in the second picture in the statement.
In the second test case, the only wiring possible has the two wires cross, so the answer is $$$1$$$.
In the third test case, the only wiring possible has one wire, so the answer is $$$0$$$.
You are given an array $$$a$$$ of distinct integers.
In one operation, you may either:
- choose a nonempty prefix$$$^{\text{∗}}$$$ of $$$a$$$ and replace it with its minimum value, or
- choose a nonempty suffix$$$^{\text{†}}$$$ of $$$a$$$ and replace it with its maximum value.
Note that you may choose the entire array $$$a$$$.
For each element $$$a_i$$$, determine if there exists some sequence of operations to transform $$$a$$$ into $$$[a_i]$$$; that is, make the array $$$a$$$ consist of only one element, which is $$$a_i$$$. Output your answer as a binary string of length $$$n$$$, where the $$$i$$$-th character is $$$1$$$ if there exists a sequence to transform $$$a$$$ into $$$[a_i]$$$, and $$$0$$$ otherwise.
$$$^{\text{∗}}$$$A prefix of an array is a subarray consisting of the first $$$k$$$ elements of the array, for some integer $$$k$$$.
$$$^{\text{†}}$$$A suffix of an array is a subarray consisting of the last $$$k$$$ elements of the array, for some integer $$$k$$$.
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 one integer $$$n$$$ ($$$2 \leq n \leq 2\cdot 10^5$$$) — the size of the array $$$a$$$.
The second line of each test case contains $$$n$$$ integers, $$$a_1,a_2,\dots,a_n$$$ ($$$1 \leq a_i \leq 10^6$$$). It is guaranteed that all $$$a_i$$$ are distinct.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.
For each test case, output a binary string of length $$$n$$$ — the $$$i$$$-th character should be $$$1$$$ if there exists a sequence of operations as described above, and $$$0$$$ otherwise.
361 3 5 4 7 2413 10 12 2071 2 3 4 5 6 7
100011 1101 1000001
In the first sample, you can first choose the prefix of size $$$3$$$. Then the array is transformed into
| 1 | 4 | 7 | 2 |
| 1 | 4 | 7 |
| 1 |
It can be shown that it is impossible to transform $$$a$$$ into $$$[3]$$$.
Alice gives you an array $$$a$$$ of size $$$n$$$. You can perform the following operation any number of times (including zero):
- Choose two distinct indexes $$$i$$$ and $$$j$$$, such that $$$a_j \le a_i$$$ and replace $$$a_i$$$ with $$$a_i-a_j$$$.
Bob being the troublemaker he is, orders you to change $$$\textbf{exactly one}$$$ element in the array before performing the above operation. Your goal is to maximize the gcd of the whole array, $$$gcd(a_1,a_2,...,a_n)$$$.
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.
The first line of each testcase contains a single integer $$$n$$$ ($$$2\le n\le 10^5$$$) — the size of the array $$$a$$$.
The second line contains $$$n$$$ integers $$$a_1$$$,$$$a_2$$$,…,$$$a_n$$$ ($$$1\le a_i\le 10^9$$$) — the elements of array $$$a$$$.
The sum of $$$n$$$ over all testcases does not exceed $$$10^6$$$.
Output a single integer for each testcase — the maximum possible value of $$$gcd(a_1,a_2,...,a_n)$$$.
325 554 4 4 2 473 6 12 990 9 12 15
5 4 3
One day, Abu Al-Nar decided to venture into the real estate business, more specifically, he want to build towers. To be fair to the people in Haret Al-Nar, Abu Al-Nar asked people how tall they wanted their towers, with each tower's height measured in blocks.
Abu Hussain, a well-known architect and engineer in Haret Al-Dab3 and other harat, heard about this and visited Abu Al-Nar. After a long discussion, they discovered that there are $$$n$$$ people in Haret Al-Nar, each wanting a tower with $$$a_i$$$ blocks, and Abu Hussain already owns $$$m$$$ towers, each with $$$b_i$$$ blocks.
Being a smart engineer, which is rare, Abu Hussain decided to build on top of his existing towers and give them to Abu Al-Nar. He plans to do that by adding blocks to the towers he already have, but he can only add a total of $$$k$$$ blocks. After making these adjustments, he would sell the towers.
What is the maximum number of people who can buy towers from Abu Hussain?
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Each test case consists of three lines:
The first line of each test case contains a three integers $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$), $$$m$$$ ($$$1 \le m \le 2 \cdot 10^5$$$) and $$$k$$$ ($$$0 \le k \le 10^{18}$$$) — the number of towers for Haret Al-Nar, the number of towers Abu Hussain has, and the total number blocks Abu Hussain can add respectively.
The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — $$$a_i$$$ denotes the $$$i$$$-th person in Haret Al-Nar wants a tower that contains exactly $$$a_i$$$ blocks.
The third line contains $$$m$$$ integers $$$b_1, b_2, \dots, b_m$$$ ($$$1 \le b_i \le 10^9$$$) — $$$b_i$$$ denotes the $$$i$$$-th tower Abu Hussain has is $$$b_i$$$ blocks.
The sum of the values of $$$n$$$, $$$m$$$ over all test cases does not exceed $$$10^6$$$.
for each test case print the maximum number of people that can buy from Abu Hussain.
31 3 465 8 104 5 32 10 10 51 10 8 5 102 3 18 23 3 10
1 4 0
One day Abu Shehab heard that his enemies are plotting revenge on him, so he decided to contact his favorite spy to gather intel and do reconnaissances before the enemies attack.
The spy, codenamed Abu Ibrahim, launched Operation Roya. He stole key documents revealing the enemy's infrastructure and discovered that their territory was a regular convex polygon with $$$n$$$ vertices, strictly enclosed by a circle of radius $$$r$$$.
A polygon with 4 vertices inside a circle of radius r. He reported this to Abu Shehab, who ordered him to continue gathering intel. Abu Ibrahim's mission was clear: infiltrate the enemy territory just once, observe as much as possible, document everything in a single attempt, and escape safely.
He studied the guards' schedule, and Abu Shehab gave him the green light for a single entry at 04:00 A.M. Now, Abu Ibrahim now has a problem, he has to choose exactly one point on the circle that provides the maximal view angle of the polygon so he can see as much as possible.
His objective is to determine the maximum view angle he could achieve from any point on the circle. Given the polygon's vertices and the enclosing circle, what is the largest possible view angle he can obtain?
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases.
The only line of each test case contains two integers $$$n$$$ ($$$3 \le n \le 10^6$$$) and $$$r$$$ ($$$1 \le r \le 2 \cdot 10^6$$$) — the number of vertices of the polygon and the radius of the circle respectively.
For each test case, print the maximal view angle in radians of the polygon from a point on the circle.
Your answer will be considered correct if its absolute or relative error doesn't exceed $$$10^{-6}$$$.
34 139 193 8
2.356194490 2.792526803 2.094395102
You are given three positive (greater than zero) integers $$$c$$$, $$$d$$$ and $$$x$$$.
You have to find the number of pairs of positive integers $$$(a, b)$$$ such that equality $$$c \cdot lcm(a, b) - d \cdot gcd(a, b) = x$$$ holds. Where $$$lcm(a, b)$$$ is the least common multiple of $$$a$$$ and $$$b$$$ and $$$gcd(a, b)$$$ is the greatest common divisor of $$$a$$$ and $$$b$$$.
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.
Each test case consists of one line containing three integer $$$c$$$, $$$d$$$ and $$$x$$$ ($$$1 \le c, d, x \le 10^7$$$).
For each test case, print one integer — the number of pairs ($$$a, b$$$) such that the above equality holds.
4 1 1 3 4 2 6 3 3 7 2 7 25
4 3 0 8
In the first example, the correct pairs are: ($$$1, 4$$$), ($$$4,1$$$), ($$$3, 6$$$), ($$$6, 3$$$).
In the second example, the correct pairs are: ($$$1, 2$$$), ($$$2, 1$$$), ($$$3, 3$$$).