wbyblD
题目背景
> D题,我不要被hack!!!
题目描述
有 $n+2$ 个点排成一排,编号为 $0\sim n+1$。对于第 $i$ 号点有两个整数 $a_i,b_i$,其中 $0\le i\le n+1$。规定初始时 $a_0=b_0=a_{n+1}=b_{n+1}=0$。
设你当前在第 $x$ 号点,当前的移动方向为 $y$,初始时 $x=0,y=1$。
你将按如下方式移动直到 $x,y$ 某一次变化后满足 $x=0,y=-1$ 或 $x=n+1,y=1$。
- 若 $y=1$,首先将 $x$ 增加 $1$,此时若 $a_x>0$ 则将 $y$ 变成 $-1$,否则 $y$ 不变,最后再将 $a_x$ 减少 $1$。
- 若 $y=-1$,首先将 $x$ 减少 $1$,此时若 $b_x>0$ 则将 $y$ 变成 $1$,否则 $y$ 不变,最后再将 $b_x$ 减少 $1$。
问最后结束时 $x$ 会在第几号点,事实上,最后 $x$ 仅可能在第 $0$ 号点或第 $n+1$ 号点。
输入输出格式
输入格式
本题有多组测试数据。第一行输入一个正整数 $T$,表示测试数据组数,接下来分别输入 $T$ 组数据。
对于每组测试数据,第一行输入一个正整数 $n$。
接下来 $n$ 行每行输入两个非负整数 $a_i,b_i$,表示 $a_i,b_i$ 的初始值。
输出格式
对于每组测试数据输出一行一个整数表示最后结束时 $x$ 会在第几号点。
输入输出样例
输入样例 #1
3
1
1 1
3
0 1
1 1
1 0
3
0 1
2 3
4 5
输出样例 #1
0
4
0
说明
#### 样例解释
对于样例第 $1$ 组数据,$(x,y)$ 依次为 $(0,1)\to (1,1)\to (1,-1)\to (0,-1)$。
对于样例第 $2$ 组数据,$(x,y)$ 依次为 $(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)$。
对于样例第 $3$ 组数据,$(x,y)$ 依次为 $(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)$。
#### 数据范围与约定
对于前 $30\%$ 的测试点,保证 $n,a_i,b_i\le 10$。
对于前 $60\%$ 的测试点,保证 $\sum n\le 5000$。
对于另外 $20\%$ 的测试点,保证 $T=10$,$n=10^5$,$a_i,b_i$ 在指定范围内均匀随机生成。特别的,保证除该档部分分外所有测试点满足 $T\ne 10$。
对于所有测试点,保证 $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$。