← 返回题目列表

Codeforces · 311/A

A. 最近的一对

中文机器翻译题面 查看原题

目前Tiny正在学习计算几何。当试图解决一个名为“平面上最接近的点对”的问题时,他发现给出错误时间复杂度的代码被接受,而不是超过时间限制。

问题如下。给定平面上的 n 个点,找到一对距离最小的点。 (x1, y1) 和 (x2, y2) 之间的距离为 $$\sqrt{(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}}$$。

意外代码的伪代码如下:

这里,tot可以看作是代码的运行时间。由于计算机每秒只能运行有限数量的操作,因此 tot 不应超过 k,以免超出时间限制。

你是一位伟大的黑客。您能帮Tiny生成一个测试数据并让代码得到Time Limit Exceeded吗?

输入

单行,包含两个空格分隔的整数 n 和 k (2 ≤ n ≤ 2000, 1 ≤ k ≤ 109)。

输出

如果不存在让给定代码获得 TLE 的数据,则打印“无解”(不带引号); else 打印n行,第i行包含两个整数xi,yi (|xi|, |yi| ≤ 109),代表第i个点的坐标。

必须满足以下条件:

- 所有点必须不同。
- |xi|, |yi| ≤ 109。
- 运行给定代码后,tot 的值应大于 k。

示例

输入 #1

4 3

输出 #1

0 0
0 1
1 0
1 1

输入 #2

2 100

输出 #2

no solution