Your friend Lina invited you and a bunch of other friends to a costume party to celebrate her success in writing her first program, called "Hello World!". Since the party was boring, you decided to try and guess Lina's position before the celebration comes to an end.
Strangely enough, your friends were standing in a line numbered from $$$1$$$ to $$$N$$$, consecutively from left to right. Initially, no one knows where Lina is, other than her. You can perform the following action at most $$$10^5$$$ times (or the party will be over):
Select one person, ask them where Lina is. If they don't know the answer (or the person is Lina), they will answer with $$$0$$$. Otherwise, they will return:
- $$$-1$$$ (indicating that Lina's position is greater than theirs), or
- $$$1$$$ (indicating that Lina's position is smaller than theirs).
After each query, everyone who knows Lina's position will spread this information to the people next to them (at most two new people will know Lina's position after each query).
Keep in mind that the program is designed to challenge you. Lina can be in any position that is consistent with the answers you receive, so be cautious with your queries.
Your goal is to find Lina's position using as few queries as possible.
The first line contains an integer $$$N (1\leq N\leq 10^5)$$$ – the number of people at the party.
To inquire about the position of friend number $$$i$$$ ($$$1 \leq i \leq N$$$), use the format: "? i". The interactor will respond with:
- $$$0$$$ if the person doesn't know where Lina is (or if the person is Lina),
- $$$-1$$$ if Lina's position is greater than the queried person's position,
- $$$1$$$ if Lina's position is smaller than the queried person's position.
To make a guess about Lina's position, use the format: "! i" ($$$1 \leq i \leq N$$$). You can only make one guess. The interactor will not respond to the guess, and your program should terminate immediately after making the guess.
Keep in mind that the grader is adaptive, meaning it will adjust its behavior based on your queries. Therefore, your queries influence the responses.
After each query or guess, remember to output a newline and flush the output to avoid an idleness limit exceeded verdict. In C++, you can do this with: fflush(stdout) or cout.flush().
Your score will be calculated based on the maximal value of $$$Q$$$, the number of queries made.
- If $$$Q \gt 10^5:$$$ $$$\textrm{Score} = 0$$$.
- If $$$470 \lt Q\leq 10^5:$$$ $$$\textrm{Score}=5+ 95\left(1-\sqrt{\dfrac{Q}{10^5}}\right)$$$
- If $$$Q\leq 470:$$$ $$$\textrm{Score} =100$$$.
5 0 -1 1 0
? 3 ? 2 ? 5 ? 3 ! 3
In the sample test, there are 5 people, and Lina is at position 3.
- At the beginning, no one except Lina knew her position. If you asked anyone at this stage, their responses would be: $$$0, 0, 0,0,0$$$. So the answer to the first query "? $$$3$$$" was $$$0$$$.
- After the first query, Lina revealed her position to her immediate neighbors (positions 2 and 4). The responses became: $$$0,-1,0,1,0$$$. So the answer to the second query "? $$$2$$$" was $$$-1$$$.
- After the second query, the people who knew Lina's position (positions 2, 3, and 4) spread this information further to their neighbors (positions 1 and 5). The responses then became: $$$-1,-1,0,1,1$$$. So the answer to the third query "? $$$5$$$" was $$$1$$$.
- After the third query, since everyone now knows Lina's position, no new information was revealed, so the answers remained unchanged: $$$-1,-1,0,1,1$$$. So the answer to the last query "? $$$3$$$" was $$$0$$$.
- After that, the user successfully guessed Lina's position "! $$$3$$$"
You're given an integer $$$n$$$ and an array of $$$n$$$ elements $$$a_1,a_2...,a_n$$$.
You need to find an array $$$t$$$ of $$$n$$$ elements $$$t_1,t_2...,t_n$$$ such that the following conditions hold :
1 - $$$a_i = t_i + t_{i+1}$$$ $$$\forall i \in [1,n-1] $$$
2 - $$$a_n = t_n + t_1$$$
3 - $$$t[i] \geq 0$$$ $$$\forall i \in [1,n] $$$
The first line contains an integer $$$t$$$ $$$( 1\leq t\leq 10^5)$$$, the number of test cases.
The first line of each test case contains the integer $$$n$$$ $$$( 2\leq n\leq 10^6)$$$.
The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,…,a_n$$$ $$$( 0\leq a_i\leq 10^{9})$$$.
It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$3\times10^6$$$
If there doesn't exist such an array $$$t$$$ print $$$-1$$$ and return.
If there is exactly $$$one$$$ array $$$t$$$ satisfying the conditions print $$$t_1,t_2,...,t_n$$$ and return.
If there are $$$many$$$ arrays satisfying the conditions just print how many are there and return.
(One can prove that the number of such arrays is $$$fini$$$).
- (10 points) $$$ 2\leq n\leq 10^3$$$ and $$$ 0\leq a_i\leq 10^3$$$.
- (10 points) $$$ 2\leq n\leq 10^6$$$ and $$$n$$$ is odd.
- (15 points) $$$ 2\leq n\leq 10^2$$$.
- (65 points) No additional constraints.
2 5 3 5 7 9 6 2 5 5
1 2 3 4 5 6
- Note that in the first testcase, it's easy to prove that there is one unique array $$$t$$$ which is $$${1,2,3,4,5}$$$, since :
$$$t[1]+t[2]=a[1]=3$$$
$$$t[2]+t[3]=a[2]=5$$$
$$$t[3]+t[4]=a[3]=7$$$
$$$t[4]+t[5]=a[4]=9$$$
$$$t[5]+t[1]=a[5]=6$$$
- In the second testcase, the arrays are : $$$\{0,5\},\{1,4\},\{2,3\},\{3,2\},\{4,1\},\{5,0\}.$$$
Given $$$n$$$ gears, numbered from $$$1$$$ to $$$n$$$ such that for each $$$i$$$ $$$( 1 \leq i \leq n-1)$$$ the $$$i-th$$$ gear is directly connected to the $$$(i+1)-th$$$ gear. Each gear has a radius $$$r_i$$$ and is initially rotated by $$$m$$$ degrees in clockwise direction.
It is given that for every $$$i, j (1 \leq i, j \leq n)$$$ , $$$r_i$$$ divides $$$r_j$$$ or $$$r_j$$$ divides $$$r_i$$$.
There are $$$q$$$ queries, for each query $$$j$$$, Ahmed rotates the gear of index $$$a_j$$$ by $$$b_j$$$ degrees in clockwise direction. Given three integers $$$n$$$, $$$m$$$ and $$$q$$$, and the three arrays $$$r$$$, $$$a$$$ and $$$b$$$. Print after each query the number of gears that have degree $$$0$$$.
The first line of the input contains three integers $$$n, q and m (1 \leq n, q \leq 10^5; 0 \leq m \leq 359)$$$.
The second line of the input contains $$$n$$$ space separated integers, $$$r_1, r_2,..., r_n$$$ $$$( 1 \leq r_i \leq 10^9)$$$.
Each of the next q lines contains 2 integers $$$X$$$ and $$$Y$$$ $$$(1 \leq X \leq n; 0 \leq Y \leq 10^9)$$$, the index of the rotated gear and the number of degrees it was rotated respectively.
For each query, print the number of gears that have degree $$$0$$$.
($$$15$$$ Points) $$$1\leq n,q\leq 1000$$$,
($$$35$$$ Points) $$$m=0$$$.
($$$50$$$ Points) No additional constraints.
4 3 20 2 2 1 8 3 340 2 360 1 10
1 1 0
If gear $$$A$$$ is connected directly to gear $$$B$$$, rotating gear $$$A$$$ with $$$Y$$$ degrees will rotate gear $$$B$$$ by $$$-Y * r_A / r_B$$$ degrees.
If gear $$$A$$$ is connected directly to gear $$$B$$$, then gear $$$B$$$ is connected directly to gear $$$A$$$.
In the example:
After the first query, the angles become respectively: 190 -150 0 -22.5.
after the second query, the angles become respectively: 190 210 0 67.5.
after the third query, the angles become respectively: 200 200 20 -25.