P9815 wbyblD

> Problem D. I do not want to be hacked!!!

There are $n+2$ points in a line, numbered $0\sim n+1$. For point $i$, there are two integers $a_i, b_i$, where $0\le i\le n+1$. Initially, define $a_0=b_0=a_{n+1}=b_{n+1}=0$. Suppose you are currently at point $x$, and the current moving direction is $y$. Initially, $x=0, y=1$. You will move in the following way until after some change of $x, y$ you get $x=0, y=-1$ or $x=n+1, y=1$. - If $y=1$, first increase $x$ by $1$. Then if $a_x>0$, set $y$ to $-1$; otherwise, keep $y$ unchanged. Finally, decrease $a_x$ by $1$. - If $y=-1$, first decrease $x$ by $1$. Then if $b_x>0$, set $y$ to $1$; otherwise, keep $y$ unchanged. Finally, decrease $b_x$ by $1$. Ask which point number $x$ will be at when the process ends. In fact, in the end, $x$ can only be at point $0$ or point $n+1$.

This problem has multiple sets of testdata. The first line contains a positive integer $T$, the number of test cases, followed by $T$ test cases. For each test case, the first line contains a positive integer $n$. Then follow $n$ lines, each containing two non-negative integers $a_i, b_i$, representing the initial values of $a_i, b_i$.

For each test case, output one line with one integer, indicating which point number $x$ will be at when the process ends.

#### Sample Explanation For the $1$st sample test case, $(x,y)$ changes as $(0,1)\to (1,1)\to (1,-1)\to (0,-1)$. For the $2$nd sample test case, $(x,y)$ changes as $(0,1)\to (1,1)\to (2,1)\to (2,-1)\to (1,-1)\to (1,1)\to (2,1)\to (3,1)\to (3,-1)\to (2,-1)\to (2,1)\to (3,1)\to (4,1)$. For the $3$rd sample test case, $(x,y)$ changes as $(0,1)\to (1,1)\to (2,1)\to (2,-1)\to (1,-1)\to (1,1)\to (2,1)\to (2,-1)\to (1,-1)\to (0,-1)$. #### Constraints and Notes For the first $30\%$ of the test points, it is guaranteed that $n,a_i,b_i\le 10$. For the first $60\%$ of the test points, it is guaranteed that $\sum n\le 5000$. For the other $20\%$ of the test points, it is guaranteed that $T=10$, $n=10^5$, and $a_i,b_i$ are generated uniformly at random within the specified range. In particular, it is guaranteed that for all test points except this part, $T\ne 10$. For all test points, it is guaranteed that $1\le T\le 10^4$, $1\le n\le 10^5$, $1\le \sum n\le 10^6$, $0\le a_i,b_i\le 10^6$. Translated by ChatGPT 5