← 返回题目列表

Codeforces · 2068/H

H. 雕像

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

某城市的市长想要在城市周围的十字路口放置 $$$n$$$ 雕像。城市中的交叉点在所有点 $$$(x, y)$$$ 上都有整数坐标。交叉点之间的距离使用曼哈顿距离测量,定义如下: $$\text{distance}((x_1, y_1), (x_2, y_2)) = |x_1 - x_2| + |y_1 - y_2|.$$

市议会对雕像的放置提出了以下要求:

  • 第一个雕像放置在$$$(0, 0)$$$;
  • 第$$$n$$$个雕像放置在$$$(a, b)$$$;
  • 对于 $$$i = 1, \dots, n-1$$$,第 $$$i$$$ 个雕像与第 $$$(i+1)$$$ 个雕像之间的距离为 $$$d_i$$$。

允许在同一个路口放置多个雕像。

帮助市长找到 $$$n$$$ 雕像的有效排列,或者确定它不存在。

输入

第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 50$$$) — 雕像的数量。

第二行包含两个整数 $$$a$$$ 和 $$$b$$$ ($$$0 \le a, b \le 10^9$$$) — 必须放置第 $$$n$$$ 雕像的交叉点坐标。

第三行包含 $$$n-1$$$ 整数 $$$d_1, \dots, d_{n-1}$$$ ($$$0 \le d_i \le 10^9$$$) — 第 $$$i$$$ 个雕像与第 $$$(i+1)$$$ 个雕像之间的距离。

输出

如果 $$$n$$$ 雕像的排列有效,则打印 $$$\texttt{YES}$$$。否则,打印 $$$\texttt{NO}$$$。

如果存在有效排列,请在以下 $$$n$$$ 行中打印有效排列。这些行中的第 $$$i$$$ 必须包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ — 第 $$$i$$$ 雕像放置的交叉点的坐标。如果存在多个有效排列,您可以打印任何有效排列。

示例

输入
复制

3
5 8
9 0

输出
复制

NO

输入
复制

4
10 6
7 8 5

输出
复制

YES
0 0
6 -1
11 2
10 6

注意

在 第一个样本,这 3 个雕像没有有效的排列。

在 第二个样本,示例输出如下图所示。请注意,这并不是 4 座雕像的唯一有效排列。