[Solution] Water the Trees solution codeforces

Water the Trees solution codeforces – There are 𝑛n trees in a park, numbered from 11 to 𝑛n. The initial height of the 𝑖i-th tree is 𝑖hi.

You want to water these trees, so they all grow to the same height.

[Solution] Water the Trees solution codeforces

The watering process goes as follows. You start watering trees at day 11. During the 𝑗j-th day you can:

  • Choose a tree and water it. If the day is odd (e.g. 1,3,5,7,1,3,5,7,…), then the height of the tree increases by 11. If the day is even (e.g. 2,4,6,8,2,4,6,8,…), then the height of the tree increases by 22.
  • Or skip a day without watering any tree.

Note that you can’t water more than one tree in a day.

Your task is to determine the minimum number of days required to water the trees so they grow to the same height.

You have to answer 𝑡t independent test cases.

[Solution] Water the Trees solution codeforces

The first line of the input contains one integer 𝑡t (1𝑡21041≤t≤2⋅104) — the number of test cases.

The first line of the test case contains one integer 𝑛n (1𝑛31051≤n≤3⋅105) — the number of trees.

The second line of the test case contains 𝑛n integers 1,2,,𝑛h1,h2,…,hn (1𝑖1091≤hi≤109), where 𝑖hi is the height of the 𝑖i-th tree.

It is guaranteed that the sum of 𝑛n over all test cases does not exceed 31053⋅105 (𝑛3105∑n≤3⋅105).

Output

For each test case, print one integer — the minimum number of days required to water the trees, so they grow to the same height.

Example
input

Copy
3
3
1 2 4
5
4 4 3 5 5
7
2 5 4 8 3 7 4
output

Copy
4
3
16

Water the Trees solution codeforces

Consider the first test case of the example. The initial state of the trees is [1,2,4][1,2,4].

  1. During the first day, let’s water the first tree, so the sequence of heights becomes [2,2,4][2,2,4];
  2. during the second day, let’s water the second tree, so the sequence of heights becomes [2,4,4][2,4,4];
  3. let’s skip the third day;
  4. during the fourth day, let’s water the first tree, so the sequence of heights becomes [4,4,4][4,4,4].

Thus, the answer is 44.

 

For Solution

Click here

Leave a Comment