$\texttt{ZBRound #9}$

$\texttt{Notes}$

$\texttt{ZBOJ}$ 比赛！

$\texttt{ZBOJ-P1040}$ $\texttt{ZBOJ-P1042}$ 。

难度适中，题目不一定原创。

$\texttt{January 1st, 2020, 8:00 to 11:30}$ 。

$300$ 分。

$\text{OI}$ 赛制。

$\texttt{ProblemSet}$

题目名称	$\color{green}\texttt{Cupa}\color{black}\texttt{ and the Party}$	$\color{gray}\texttt{Skelly}\color{black}\texttt{ and the Target}$	$\color{purple}\texttt{Andr}\color{black}\texttt{ and the Portal}$
时间限制	$1000\text{ms}$	$3000\text{ms}$	$2000\text{ms}$
空间限制	$256\text{MB}$	$256\text{MB}$	$256\text{MB}$
分值	$100$	$100$	$100$
难度	$\color{green}\text{Medium}$	$\color{green}\text{Medium}$	$\color{cyan}\text{Not Easy}$

$\color{green}\texttt{Cupa}\color{black}\texttt{ and the Party}$

$\texttt{Description}$

$\color{green}\texttt{Cupa}$ 是一只爬行者。

$\color{green}\texttt{Cupa}$ $n$ $(x_0,y_0)$ $(x_1,y_1),(x_2,y_2)\cdots(x_n,y_n)$ $(x_i,y_i)$ $\color{green}\texttt{Cupa}$ $(x_a,y_a)$ $\color{green}\texttt{Cupa}$ $\color{green}\texttt{Cupa}$ $\color{green}\texttt{Cupa}$ $\color{green}\texttt{Cupa}$ $\color{green}\texttt{Cupa}$ $(x_0,y_0)$ $(x_i,y_i)$ $\color{green}\texttt{Cupa}$ $(x_a,y_a)$ $max$ 。如果有多个答案，输出任意一个即可。

$\texttt{Input Format}$

$n$ 。

$x_0,y_0$ 。

$n+2$ $i+2$ $x_i,y_i$ 。

$\texttt{Output Format}$

$max$ 。

$x_a,y_a$ ，之间用一个空格隔开。

$\texttt{Sample}$

$\texttt{Input I}$


xxxxxxxxxx
4 3 2
1 3
4 2
5 1
4 1

$\texttt{Output I}$


xxxxxxxxxx
3
4 2

$\texttt{Input II}$


xxxxxxxxxx
3 100 100
0 0
0 0
100 200

$\texttt{Output II}$


xxxxxxxxxx
2
99 100

$\texttt{Input III}$

$\texttt{Output III}$


xxxxxxxxxx
4
10 11

$\texttt{Hint}$

$1$ $\color{green}\texttt{Cupa}$ $(4,2)$ $(4,2),(4,1),(5,1)$ $\color{green}\texttt{Cupa}$ 那里。

$2$ $(1,1)$ 也是一个合法的解（合法的解还有很多）。

$30\%$ $1\leq n\leq 50,0\leq x_i,y_i,x_0,y_0\leq 100$ ；

$60\%$ $1\leq n\leq 10^5,0\leq x_i,y_i,x_0,y_0\leq 2000$ ；

$100\%$ $1\leq n\leq 2\times 10^5,0\leq x_i,y_i,x_0,y_0\leq 10^9$ 。

$0\leq x_a,y_a\leq 10^9$ 。

$\color{gray}\texttt{Skelly}\color{black}\texttt{ and the Target}$

$\texttt{Description}$

$\color{gray}\texttt{Skelly}$ 是一只骷髅。

$\color{gray}\texttt{Skelly}$ $n$ $n-1$ $\color{gray}\texttt{Skelly}$ $i$ $c_{i,1},c_{i,2},c_{i,3}$ $a$ $b$ $b$ $c$ $a,b,c$ $\color{gray}\texttt{Skelly}$ $-1$ 。如果有多个答案，输出任意一个即可。

$\texttt{Input Format}$

$n$ 。

$n$ $i$ $c_{i,1}$ 。

$n$ $i$ $c_{i,2}$ 。

$n$ $i$ $c_{i,3}$

$n+3$ $n-1$ $x,y$ $x$ $y$ 之间有纹路连接。

$\texttt{Output Format}$

$-1$ 。

否则：

$min$ ，表示难度的最小值。

$n$ $p_i$ $i$ $1$ $2$ $3$ 代表蓝色。

$\texttt{Sample}$

$\texttt{Input I}$


xxxxxxxxxx
3
3 2 3
4 3 2
3 1 3
1 2
2 3

$\texttt{Output I}$


xxxxxxxxxx
6
1 3 2

$\texttt{Input II}$

$\texttt{Output II}$


xxxxxxxxxx
-1

$\texttt{Input III}$

$\texttt{Output III}$


xxxxxxxxxx
9
1 3 2 1 3

$\texttt{Hint}$

$20\%$ $3\leq n\leq 10$ ；

$20\%$ $c_{i,j}$ 均相等。

$30\%$ $3\leq n\leq 1000$ 。

$100\%$ $3\leq n\leq 10^5,1\leq c_{i,j}\leq 10^9$ 。

数据保证所有的圆圈可以互相通过纹路连通。

$p_i\in\{1,2,3\}$ 。

$\color{purple}\texttt{Andr}\color{black}\texttt{ and the Portal}$

$\texttt{Description}$

$\color{purple}\texttt{Andr}$ 是一只末影人。

$\color{purple}\texttt{Andr}$ $\color{purple}\texttt{Andr}$ $\color{purple}\texttt{Andr}$ $x$ $\color{purple}\texttt{Andr}$ $x$ $(0,0)$ $\color{purple}\texttt{Andr}$ $(p,0)$ $p$ $(p-1,0)$ $p$ $(p\div 2,0)$ $\color{purple}\texttt{Andr}$ $(0,0)$ $\color{purple}\texttt{Andr}$ $(i,0)$ $1\leq i\leq n,i\in \N$ $(i,0)$ $(0,0)$ $k$ 的点中，横坐标的最大值是多少。

$\texttt{Input Format}$

$n,k$ 。

$\texttt{Output Format}$

$max$ ，表示题目所要求的最大值。

$\texttt{Sample}$

$\texttt{Input I}$


xxxxxxxxxx
11 3

$\texttt{Output I}$


xxxxxxxxxx
5

$\texttt{Input II}$


xxxxxxxxxx
11 6

$\texttt{Output II}$


xxxxxxxxxx
4

$\texttt{Input III}$


xxxxxxxxxx
20 20

$\texttt{Output III}$


xxxxxxxxxx
1

$\texttt{Input IV}$


xxxxxxxxxx
14 5

$\texttt{Output IV}$


xxxxxxxxxx
6

$\texttt{Input V}$


xxxxxxxxxx
1000000 100

$\texttt{Output V}$


xxxxxxxxxx
31248

$\texttt{Hint}$

$1$ $\color{purple}\texttt{Andr}$ $(5,0),(10,0),(11,0)$ $(5,0)$ $(4,0),(1,0)$ $5$ ，所以不是正确答案。

$2$ $\color{purple}\texttt{Andr}$ $(4,0),(5,0),(8,0),(9,0),(10,0),(11,0)$ $(4,0)$ 。

$3$ $\color{purple}\texttt{Andr}$ $(1,0)$ 。

$5\%$ $k=0$ 。

$5\%$ $k=n$ 。

$20\%$ $n\leq 10^4$ 。

$40\%$ $n\leq 10^9$ 。

$60\%$ $n\leq 10^{12}$ 。

$100\%$ $0\leq k<n\leq 10^{18}$ 。