题目背景

使用说明

---

题目中的 $(A,B)$ 代表一条从 $A$ 连到 $B$ 的对角线。

定义正多边形的顶点 $A$ 到顶点 $B$ 的 eJ 距离为点 $A$ 顺时针走到点 $B$ 需要的边数和点 $A$ 逆时针走到点 $B$ 需要的边数的最大值。根据这个定义，也可以拓展出正多边形的顶点 $A$ 到一条正多边形的对角线 $B$ 的 eJ 距离的定义，即点 $A$ 顺时针走到对角线 $B$ 的一个端点（离的最近的端点）需要的边数和逆时针走需要的边数的最大值。

比如点 $0$ 到对角线 $(0,5)$ 的 eJ 距离为 $5$，顺时针走需要经过 $5$ 条边，逆时针要经过 $2$ 条，答案为 $\max\{5,2\}=5$。

题目描述

给定一个 $N$ 边形，点顺时针编号为 $0 \sim N-1$，现在小 A 画了 $n-3$ 条对角线，保证这 $n-3$ 条对角线除了顶点外没有额外交点。

现在小 A 想让小 J 猜猜哪条对角线离点 $0$ 的 eJ 距离最近，并回答这个距离。

小 J 并不能通过读心术知道答案，所以他只能找小 A 索要一些线索。小 A 给了小 J $n$ 的值，并且答应小 J 可以找小 A 询问一对顶点之间是否有对角线，但小 J 的询问次数有限制。

小 J 还要 AK eJOI，所以这个问题就交给了你。

交互规则

你需要调用 triangulation.h 头文件。

int solve(int n)

• 这个函数只能被调用一次。
• $n$：多边形顶点个数。
• 假设答案对角线为 $(a,b)$，这个函数应该返回 $a \times n+b$。
• 如果有多条对角线离点 $0$ 最近，可以只返回其中一条。

solve 函数可以调用若干次下面这个函数：

int query(int x, int y)

• $x,y$：代表一组询问。
• $0 \le x,y \le n-1$。
• 如果 $(x,y)$ 存在，返回 $1$，否则返回 $0$。

7

提示

样例 1

样例输入格式仅包含一个整数 $n$。

调用函数	返回值
solve(7)
query(0,3)	$0$
query(0,5)	$1$
query(1,5)
	solve 函数返回 $1 \times7+5=12$
	正确

数据规模与约定

对于 $100\%$ 的数据，$5 \le n \le 100$。

假设 $q$ 为你单组数据的询问次数，令 $w=\dfrac{n \times (n-3)}{2}$，你单组数据的分数为：

• 询问不合法，答案错误或 $w<q$，你会得到 $0\%$ 的分数。
• $n<q \le w$，你会得到 $10+60 \times \dfrac{w-q}{w-n}\%$ 的分数。
• $q \le n$，你会得到 $100\%$ 的分数。

感谢

checker & grader。

说明

翻译自 eJOI 2020 Day1 B Triangulation。