#5715. 「BalticOI 2026」距离

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

题目译自 BalticOI 2026 Day2「Distances」

给定两个整数 $n$ 和 $k$。你需要选择 $n$ 个互不相同的整点（即横纵坐标均为整数的点），使得平面上恰好有 $k$ 对点之间的欧几里得距离为整数。回顾一下，点 $(x_{1}, y_{1})$ 和 $(x_{2}, y_{2})$ 之间的欧几里得距离为：

$$\sqrt{\left(x_{1}-x_{2}\right)^{2}+\left(y_{1}-y_{2}\right)^{2}}$$

可以证明，在该任务的限制条件下，一定存在符合要求的解。

输入格式

唯一的一行包含两个整数 $n$ 和 $k$。

输出格式

输出 $n$ 行，第 $i$ 行包含两个整数，表示第 $i$ 个点的坐标 $x$ 和 $y$。每个坐标的绝对值必须不超过 $10^{9}$。

如果存在多个解，你可以输出其中任意一个。

样例

输入

3 2

输出

1 1
1 2
2 2

点 $(1, 1)$ 和 $(1, 2)$ 之间的欧几里得距离为 $1$。点 $(1, 2)$ 和 $(2, 2)$ 之间的距离也为 $1$。然而，点 $(1, 1)$ 和 $(2, 2)$ 之间的距离为 $\sqrt{2}$，不是一个整数。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq n \leq 100$
• $0 \leq k \leq n(n-1) / 2$

详细子任务附加限制及分值如下表所示。

子任务	附加限制	分值
$1$	$n \leq 4$	$11$
$2$	$k=n(n-1) / 2$	$4$
$3$	$k=0$	$6$
$4$	$k \leq n$	$19$
$5$	$k \leq n(n-1) / 8$	$22$
$6$	无附加限制	$38$