You are given an array $$$a$$$ of $$$n$$$ distinct positive integers. Unfortunately, the array is way past its prime, so you have decided to help it relive "the good old days"!
The array remembers that in the "the good old days" it had a sum of elements greater than or equal to a given threshold $$$s$$$. To help the array, you are allowed to perform a sequence of operations. In one operation, you may choose any positive integer $$$x$$$ which is not already present in the array, and append it to the end of $$$a$$$.
In a stroke of genius and insecurity, you have come to the rational conclusion that once the array realizes that the sum of its elements is greater than or equal to $$$s$$$, it will no longer allow you to perform any more operations and leave forever. To postpone the inevitable departure of the array, you have decided to make the helping process as lengthy as possible. More formally, you would like to maximize the number of operations before the array realizes that the sum of its elements is greater than or equal to $$$s$$$.
What is the maximum final length of array $$$a$$$?
The first line of input contains two integers $$$n$$$ and $$$s$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le s \le 10^{18})$$$ — the length of the initial array, and the given threshold for the sum. The second line of input contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^{12}$$$) — the elements of the initial array.
Print one integer, the maximum possible final length of the array.
- Subtask 1 (20 points): $$$1\le n \le 1000$$$, $$$1\le s \le 10^9$$$;
- Subtask 2 (30 points): $$$1\le n \le 10^5$$$, $$$1\le s \le 10^{12}$$$;
- Subtask 3 (50 points): No further constraints
3 17 6 1 3
6
5 28 6 8 1 5 9
5
- In the first sample, a way to get an array of size $$$6$$$ is to append, in order, integers $$$4$$$, $$$2$$$ and $$$7$$$, giving us the array $$$a=[6,1,3,4,2,7]$$$. When $$$7$$$ is appended, the sum of the elements will become $$$6+1+3+4+2+7=23$$$, which is greater than or equal to $$$s=17$$$.
- In the second sample, the sum of the elements of the array is $$$6+8+1+5+9=29$$$, which is already greater than or equal to $$$s=28$$$.
Binary Search Search (BSS) is a cross between Breadth First Search and Binary Search. Its pseoudocode can be found below:
read n
queue of pairs q
push(q,pair(1,n))
while(q is not empty){
pair current = front(q)
mid = (current.first + current.second) / 2
print mid
if(mid > current.first)
push(q,pair(current.first, mid - 1))
if(mid < current.second)
push(q,pair(mid + 1, current.second))
pop_front(q)
}
For example, if $$$n=7$$$, this algorithm will print [$$$4$$$ $$$2$$$ $$$6$$$ $$$1$$$ $$$3$$$ $$$5$$$ $$$7$$$].
Even though BSS doesn't have any practical applications, you are curious as to how long it takes for this algorithm to print certain integers. More formally, you are given $$$t$$$ testcases, each testcase containing two integers $$$n$$$ and $$$k$$$. For each testcase, print one integer $$$p$$$ — the position of $$$k$$$ in the array printed by BSS.
The first line of input contains one integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of testcases. Each testcase contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 10^{18}$$$) — as described in the statement.
For each testcase, print one integer $$$p$$$ — the position of $$$k$$$ in the array printed by BSS.
- Subtask 1 (20 points): $$$1 \le t,n \le 1000$$$;
- Subtask 2 (30 points): $$$1 \le t \le 1000$$$, $$$1 \le n \le 10^9$$$;
- Subtask 3 (24 points): $$$1 \le t \le 10^4$$$;
- Subtask 4 (26 points): No further constraints
7 7 1 7 2 7 3 7 4 7 5 4 1 4 4
4 2 5 1 6 2 4
For $$$n=7$$$, BSS will print [$$$4$$$ $$$2$$$ $$$6$$$ $$$1$$$ $$$3$$$ $$$5$$$ $$$7$$$]. $$$1$$$ is the fourth printed integer, $$$2$$$ is the second, $$$3$$$ is the fifth, $$$4$$$ is the first and $$$5$$$ is the sixth.
For $$$n=4$$$, BSS will print [$$$2$$$ $$$1$$$ $$$3$$$ $$$4$$$]. $$$1$$$ is the second printed integer and $$$4$$$ is the fourth.
Following the unfortunate passing of ET Glob's grandma, our friendly extraterrestrial has inherited $$$n$$$ plates. Each plate is coloured with one of $$$k$$$ colours $$$1,2, \ldots, k$$$. He has also inherited his grandma's cupboard, which conveniently has a capacity of exactly $$$n$$$ plates.
ET Glob's little brother wanted to help with storing the plates, so he randomly and untidily piled some of them in the cupboard. When ET Glob realized that his brother had ruined his feng shui, he decided to store the rest of the plates himself. ET Glob knows the current configuration of the cupboard, which can represented as an array $$$a$$$ of $$$n$$$ integers. If $$$a_i$$$ is equal to $$$0$$$, then the $$$i$$$-th slot in the cupboard is empty. Otherwise, $$$a_i$$$ is equal to the colour of the plate in the $$$i$$$-th slot.
To restore his feng shui, ET Glob would like to store his plates in a tidy fashion. In his opinion, the final configuration of the plates is tidy if and only if the number of plates which have a different colour than the plate to their left is minimized.
Additionally, across all such final configurations, ET Glob would like to choose one which requires moving the least plates from the initial configuration. Let $$$a$$$ be the array denoting the initial configuration of the cupboard and $$$b$$$ be the array denoting the final configuration of the cupboard. The number of plates that have to be moved to get from $$$a$$$ to $$$b$$$ is equal to the number of positions $$$i$$$, $$$1 \le i \le n$$$, where $$$a_i \neq 0$$$ and $$$a_i \neq b_i$$$.
To help Glob, you will have to find the minimum amount of plates from the initial configuration which have to be moved, and one possible final configuration which requires moving the minimum amount of plates. If there are multiple possible final configurations, you may print any.
- The first line of input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le k \le 20$$$) — the number of plates, and the number of colours, respectively.
- The second line of input contains $$$n$$$ integers $$$a_i$$$ ($$$0 \le a_i \le k$$$) — the initial configuration of the cupboard.
- The third line of input contains $$$k$$$ integers $$$p_i$$$, the number of plates of each colour ($$$0 \le p_i \le n$$$, $$$\Sigma p_i = n$$$).
On the first line of output print one integer $$$x$$$ — the minimum number of positions $$$i$$$ ($$$1 \le i \le n$$$) in which $$$a_i \neq 0$$$ and $$$a_i \neq b_i$$$. On the second line of output print $$$n$$$ space separated integers — one possible optimal final configuration. If there are multiple possible final configurations, you may print any.
- Subtask 1 (13 points): $$$1 \le n,k \le 10$$$;
- Subtask 2 (11 points): $$$1 \le k \le 5$$$;
- Subtask 3 (18 points): $$$1 \le k \le 10$$$;
- Subtask 4 (27 points): $$$1 \le n \le 100$$$;
- Subtask 5 (31 points): No further constraints.
8 3 0 1 0 1 3 2 0 0 3 2 3
2 1 1 1 3 3 3 2 2
5 4 1 4 0 0 0 2 0 1 2
1 1 1 3 4 4
In the first sample, $$$[1,1,1,3,3,3,2,2]$$$ is one possible final configuration which differs from the original configuration in exactly $$$2$$$ positions, namely $$$i_1=4$$$ and $$$i_2=6$$$. It can be proven that there are no final configurations which differ by less then $$$2$$$ elements.