You are fighting the final dragon boss in Minecraft. The dragon has health points $$$n$$$, and you have a sword with the following properties:
- In the $$$i$$$-th attack, if $$$i$$$ is a multiple of $$$3$$$, deal $$$2$$$ points of damage; otherwise, deal $$$1$$$ point of damage.
Your initial health point is $$$m$$$ initially. Every time after you hit the dragon, if the health points of the dragon are less than $$$1$$$, it is defeated. Otherwise, it immediately rebounds $$$k$$$ $$$(k \lt m)$$$ points of damage to you. If your health point is less than $$$1$$$, you are defeated and cannot take any action.
In addition, you can use bandages any number of times. When you use a bandage, it restores your health to $$$m$$$. Note that using a bandage and attacking are independent.
Find the minimum number of bandages required to defeat the dragon.
The first line contains a single integer $$$t$$$ ($$$1 \le t\le 100$$$), the number of test cases.
The only line of each test case contains three integers $$$n,m,k$$$ ($$$1\le n,k\le 100$$$, $$$k \lt m \le 101$$$).
For each test case, output the minimum number of bandages required to defeat the dragon.
44 3 24 3 110 7 396 101 23
1 0 3 17
In the first test case, the optimal action is:
- Attack.
- Use a bandage.
- Attack.
- Attack.
After that, the dragon is defeated. The number of bandages used is $$$1$$$.
OwlBear comes to destroy the village with an ancient-mythical shield in hand.
To protect the village, the villagers had set $$$n$$$ cannons indexed from $$$0$$$ to $$$n-1$$$. Cannon $$$i$$$ $$$(0 \le i \le n-1)$$$ can deal $$$a_i$$$ damage in one shot.At one second, cannons can shoot simultaneously .
OwlBear is full of brute force, so he is not smart. At the $$$k$$$-th second, he uses his shield to protect himself from getting hit by the $$$((k-1) \bmod n)$$$ -th cannon shot.
You need to answer $$$q$$$ queries. Each query gives you an integer $$$h$$$, and you need to find the minimum number of seconds so that villagers can take to deal more or equal to $$$h$$$ damage to the Owlbear.
The first line contains an int $$$t$$$ $$$(1 \le t \le 10^4)$$$, the number of test cases.
Each test case contains the following lines.
The first line contains an int $$$n$$$ $$$(2 \le n \le 10^5)$$$, the number of cannons villagers set.
The second line contains $$$n$$$ integers $$$a_0,a_1,...,a_{n-1}$$$ $$$(1 \le a_i \le 10^{6})$$$, the damage each cannon can deal in one shot.
The third line contains a single integer $$$q$$$ $$$(1 \le q \le 2 \cdot 10^5)$$$, the number of times OwlBear comes to destroy the village.
The next $$$q$$$ lines contain a single integer $$$h$$$ $$$(1 \le h \le 10^{9})$$$, the minimum damage after which OwlBear will run away.
It is guaranteed that the sum of $$$n$$$ and $$$q$$$ over all test cases will not exceed $$$2 \cdot 10^5$$$.
For each test case, output in a new line — the minimum number of seconds so that villagers can take to deal more or equal to $$$h$$$ damage to the Owlbear.
142 3 2 7427412012
3 1 12 1
For the $$$1$$$-st query, $$$h=27$$$ and $$$a=[2,3,2,7]$$$.
- After the $$$1$$$-st second, OwlBear will take $$$0+3+2+7=12$$$ damage.
- After the $$$2$$$-nd second, OwlBear will take $$$2+0+2+7=11$$$ damage.
- After the $$$3$$$-rd second, OwlBear will take $$$2+3+0+7=12$$$ damage.
The sum of the damages is $$$12+11+12=35$$$, which is greater than $$$h=27$$$.
This is the easy version of this problem. The only difference is that in this version you only need to construct any matrix satisfying the given conditions.
You are given an integer $$$n$$$. You need to construct an $$$n \times n$$$ matrix $$$a$$$ that satisfies all of the following conditions :
- $$$1 \le a_{i,j} \le 1000$$$ for all $$$1 \le i,j \le n$$$.
- $$$\gcd(a_{i,j}$$$ $$$,$$$ $$$i+j) \gt 1$$$ for all $$$1 \le i,j \le n$$$, here $$$\gcd$$$ means greatest common divisor.
- The bitwise XOR of all numbers of the matrix $$$a$$$ equals $$$0$$$.
The first line of input contains an integer $$$t$$$ $$$(1 \le t \le 100)$$$ — the number of testcases.
The first line of each testcase contains a single integer $$$n$$$ $$$(2 \le n \le 500)$$$.
It is guaranteed that the sum of $$$n$$$ over all testcases does not exceed $$$500$$$.
For each testcase, print an $$$n \times n$$$ matrix $$$a$$$ that satisfies all the given conditions.
If there are multiple answers, print any one of them.
It can be proved that atleast one such matrix exists under the given constraints.
223
12 12 12 12 4 6 8 3 2 5 2 10 6
This is the hard version of this problem. The only difference is that in this version you need to construct any matrix with the least sum of elements.
You are given an integer $$$n$$$. You need to construct an $$$n \times n$$$ matrix $$$a$$$ that satisfies all of the following conditions :
- $$$1 \le a_{i,j} \le 1000$$$ for all $$$1 \le i,j \le n$$$.
- $$$\gcd(a_{i,j}$$$ $$$,$$$ $$$i+j) \gt 1$$$ for all $$$1 \le i,j \le n$$$, here $$$\gcd$$$ means greatest common divisor.
- The bitwise XOR of all numbers of the matrix $$$a$$$ equals $$$0$$$.
In addition, there is another condition: the matrix should have the least sum of elements.
The first line of input contains an integer $$$t$$$ $$$(1 \le t \le 100)$$$ — the number of testcases.
The first line of each testcase contains a single integer $$$n$$$ $$$(2 \le n \le 500)$$$.
It is guaranteed that the sum of $$$n$$$ over all testcases does not exceed $$$500$$$.
For each testcase, print an $$$n \times n$$$ matrix $$$a$$$ that satisfies all the given conditions.
If there are multiple answers, print any one of them that has the least sum of elements.
It can be proved that atleast one such matrix exists under the given constraints.
12
2 3 3 2
This is the easy version of this problem. In this version, you need to find the minimum possible cost.
Sanjay wanted to solve a problem, but since he had no friends, he handed it over to you. Please solve it for him.
Given an array $$$a$$$ of length $$$n$$$, the cost $$$c$$$ is defined as:
$$$$$$ c = a_1 \cdot 1 + a_2 \cdot 2 + \dots + a_{n} \cdot n $$$$$$
Your task is to find the minimum possible cost that can be achieved after applying any number of left cyclic shift operations on the array.
A left cyclic shift operation moves each element of the array one position to the left, with the first element moving to the end.
For example, $$$$$$ a = [1, 2, 3, 4] \quad$$$$$$ after one left shift becomes $$$$$$a = [2, 3, 4, 1] $$$$$$
- The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^5)$$$ — the number of test cases.
- For each test case:
- The first line contains an integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ — the size of the array.
- The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ $$$(-10^9 \leq a_i \leq 10^9)$$$ — the elements of the array.
- The sum of $$$n$$$ across all test cases does not exceed $$$10^5$$$.
- For each test case, print a single integer — the minimum cost in all possible left cyclic shifts of the array.
241 2 3 431 -1 1
22 0
In the second test case, after performing $$$2$$$ left cyclic shifts, the array becomes $$$[1, 1, -1]$$$, which results in the minimum cost.
This is the hard version of this problem. In this version, you need to answer multiple queries.
Wuhudsm got irritated because Sanjay kept proposing too many questions to him. So Wuhudsm decided to give Sanjay a tough question. Wuhudsm told Sanjay that he cannot ask any more questions until he solves this one. Since he had no friends, he handed it over to you. Please solve it for him.
Given an array $$$a$$$ of length $$$n$$$, the cost $$$c$$$ is defined as:
$$$$$$ c = a_1 \cdot 1 + a_2 \cdot 2 + \dots + a_{n} \cdot n $$$$$$
You are given $$$q$$$ queries of two types:
- 1 p x — Set the value of $$$ a_p$$$ to $$$x $$$.
- 2 k — Find the cost if the array is shifted left cyclically exactly $$$k$$$ times. Note: we do not actually perform any shift operation on this array.
A left cyclic shift operation moves each element of the array one position to the left, with the first element moving to the end.
For example, $$$$$$ a = [1, 2, 3, 4] \quad$$$$$$ after one left shift becomes $$$$$$a = [2, 3, 4, 1] $$$$$$
- The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^5)$$$ — the number of test cases.
- For each test case:
- The first line contains an integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ — the size of the array.
- The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ $$$(-10^9 \leq a_i \leq 10^9)$$$ — the elements of the array.
- The third line contains an integer $$$q$$$ $$$(1 \leq q \leq 10^5)$$$ — the number of queries.
- Then $$$q$$$ lines follow. The $$$i$$$-th line contains the $$$i$$$-th query is given either as
- 1 p x $$$(1 \leq p \leq n, -10^9 \leq x \leq 10^9)$$$
- 2 k $$$(0 \leq k \leq 10^9) $$$
The sum of $$$n$$$ and $$$q$$$ across all test cases does not exceed $$$10^5$$$.
For each query of type $$$2$$$, print the answer to this query in a new line.
241 2 3 432 21 1 52 331 -1 132 21 3 -10000000002 1000000000
22 32 0 -1999999998
In the first query of the first test case, if the array $$$a$$$ is left shifted $$$2$$$ times, $$$a=[3, 4, 1, 2]$$$.
We get $$$ c = 3 \cdot 1 + 4 \cdot 2 + 1 \cdot 3 + 2 \cdot 4 = 3 + 8 + 3 + 8 = 22 $$$.
This is an interactive problem.
There is a secret sequence $$$p_1, p_2, \cdots, p_{n}$$$, which is a permutation of $$$\{1,2,\cdots,n\}$$$.
We will define $$$ \text{idx}(x) $$$ as the index where the value $$$x$$$ is located.
You can ask two types of queries in the following format:
- "1 x y"
This means that you select two integers $$$x$$$, $$$y$$$ ($$$1 \le x,y \le n$$$), and ask if the condition $$$\text{idx}(x) \lt \text{idx}(y)$$$ holds.
- "2 x y z"
This means that you select three integers $$$x$$$, $$$y$$$, and $$$z$$$ ($$$1 \leq x, y, z \leq n$$$), and ask if $$$\text{idx}(y)$$$ is between $$$\text{idx}(x)$$$ and $$$\text{idx}(z)$$$. In other words, check if $$$\min(\text{idx}(x), \text{idx}(z)) \leq \text{idx}(y) \leq \max(\text{idx}(x), \text{idx}(z))$$$ holds.
Determine the permutation $$$p$$$ using no more than $$$1$$$ query of type $$$1$$$ and no more than $$$16n$$$ queries of type $$$2$$$.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 20$$$). The description of the test cases follows.
The first line of each test case contains one integer $$$n$$$ ($$$3 \le n \le 100$$$). At this moment, the permutation $$$p_1, p_2, \cdots, p_{n}$$$ is chosen.
To ask a type $$$1$$$ query, you need to pick two integers $$$x$$$ and $$$y$$$ ($$$1 \leq x, y \leq n$$$) and print the line of the following form:
- "1 x y"
After that, you receive:
- "1" if $$$\text{idx}(x) \lt \text{idx}(y)$$$ holds;
- "0" otherwise.
To ask a type $$$2$$$ query, you need to pick three integers $$$x, y$$$ and $$$z$$$ ($$$1 \leq x, y, z \leq n$$$) and print the line of the following form:
- "2 x y z"
After that, you receive:
- "1" if $$$\min(\text{idx}(x), \text{idx}(z)) \leq \text{idx}(y) \leq \max(\text{idx}(x), \text{idx}(z))$$$ holds;
- "0" otherwise.
Next, if your program has determined the permutation, print the line of the following form:
- "! $$$p_1\ p_2\ \cdots \ p_n$$$"
Note that this line is not considered a query.
After this, proceed to the next test case.
If the number of queries you use exceeds the limit, your program must terminate immediately, and you will receive the Wrong Answer verdict. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.
After printing a query or the answer for a test case, do not forget to output the end of line and flush the output. Otherwise, you will get the verdict Idleness Limit Exceeded. To do this, use:
- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
- see the documentation for other languages.
The interactor in this task is not adaptive. In other words, the sequence $$$p$$$ is fixed in every test case and does not change during the interaction.
Hacks
To hack, follow the test format below.
The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 20$$$). The description of the test cases follows.
The first line of each test case contains one integer $$$n$$$ ($$$3 \leq n \leq 100$$$).
The second line of each test case contains $$$n$$$ integers $$$p_1,p_2,\cdots,p_{n}$$$, which represent a permutation of integers from $$$1$$$ to $$$n$$$.
2 3 1 1 0 4 0 1 1 1
2 1 1 1 2 1 3 2 1 1 2 ! 2 3 1 2 2 1 4 2 1 2 3 1 4 2 ! 4 3 2 1
In the first test case, the hidden permutation is $$$p=[2,3,1]$$$. We can get $$$\text{idx}(1)=3,\text{idx}(2)=1$$$, and $$$\text{idx}(3)=2$$$.
For the query "2 1 1 1", the jury returns "1" because $$$\min(\text{idx}(1), \text{idx}(1)) \leq \text{idx}(1) \leq \max(\text{idx}(1), \text{idx}(1))$$$ holds;
For the query "2 1 3 2", the jury returns "1" because $$$\min(\text{idx}(1), \text{idx}(2)) \leq \text{idx}(3) \leq \max(\text{idx}(1), \text{idx}(2))$$$ holds;
For the query "1 1 2", the jury returns "0" because $$$\text{idx}(1) \lt \text{idx}(2)$$$ does not hold.
In the second test case, the hidden permutation is $$$p=[4,3,2,1]$$$.
Please note that the example is only for understanding the statement, and the queries in the example do not guarantee to determine the unique permutation.
You have an array $$$a$$$ of $$$n$$$ integers and an integer $$$k$$$.
An array is called good if the arithmetic mean of its elements is not less than $$$k$$$.
You can perform the following operation at most once:
- choose any index $$$i (1 \le i \le n)$$$, and set $$$a_i := a_i + 1$$$.
Now your task is to determine the maximum number of good subarrays of the array $$$a$$$ that can be formed by performing the operation at most once.
The first line of input contains an integer $$$t$$$ $$$(1 \le t \le 10^5)$$$ — the number of testcases.
The first line of each testcase contains two integers $$$n$$$ $$$(1 \le n \le 2\cdot10^5)$$$ and $$$k$$$ $$$(1 \le k \le 10^9)$$$.
The second line of each testcase contains $$$n$$$ integers $$$a_1,a_2,a_3,...,a_n$$$ $$$(1 \le a_i \le 10^9)$$$.
It is guaranteed that the sum of $$$n$$$ over all testcases does not exceed $$$2\cdot10^5$$$.
For each testcase, print the maximum number of good subarrays of the array $$$a$$$ that can be formed by performing the operation atmost once.
35 32 1 1 4 18 547 11 53 56 99 28 75 8410 2173 60 27 67 3 76 52 66 39 27
3 21 54
In the first test case, we can choose $$$i = 4$$$ and make $$$a_4 = a_4 + 1$$$.
After this operation, the array $$$a$$$ becomes $$$[2,1,1,5,1]$$$. Now we have $$$3$$$ subarrays $$$[5],[1,5]$$$ and $$$[5,1]$$$ with an average not less than $$$3$$$.