問題一覧 > 通常問題

No.1125 Without Parallelogram

レベル : / AI推定難易度 : 2000 / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 256 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 17
作問者 : e869120 / テスター : Thistle
お気に入りにしたユーザー ProblemId : 4638 / 自分の提出
問題文最終更新日: 2020-07-17 23:25:16
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 258 (順位表) の他の問題:

Problem Statement

Output 1 set of coordinates of $N$ points satisfying the following conditions. Here, the coordinates of the $i$-th $(1 \leq i \leq N)$ point are denoted by $(x_i, y_i)$.

  • $x_i, y_i$ are integers.
  • $0 \leq x_i, y_i \leq N + 40$.
  • The coordinates of all points are pairwise distinct. That is, $(x_i, y_i) \neq (x_j, y_j)$ $(i \neq j)$.
  • No choice of $4$ points forms a parallelogram.
If there are multiple outputs satisfying the conditions, any of them will be accepted.
It can also be proved that at least 1 answer always exists under the constraints of this problem.

Important Note

In this problem, "$4$ points form a parallelogram" means that the following condition is satisfied.

  • When the $4$ points are arranged in a suitable order and taken as vertices $A, B, C, D$ in that order, it can happen that $AB$ and $CD$ are parallel and the lengths of $AB$ and $CD$ are equal.
That is, as in the examples below, points may form a parallelogram even if the area is $0$.

Example 1
 The $4$ points $(0, 0), (1, 1), (3, 3), (4, 4)$ form a parallelogram.
 This is because the condition is satisfied when we let $A(0,0), B(1,1), C(4,4), D(3,3)$.
Example 2
 The $4$ points $(0, 0), (1, 1), (3, 3), (5, 5)$ do not form a parallelogram.
 This is because there is no arrangement of the $4$ points that satisfies the condition.

Input

$N$

On line $1$, an integer $N$ is given.

Output

Output $N$ points in the following format.

$x_1$ $y_1$
$x_2$ $y_2$
$x_3$ $y_3$
: :
$x_N$ $y_N$

That is, output over $N$ lines, where line $i$ contains the coordinates $x_i, y_i$ of the $i$-th point, separated by a space.
The output must satisfy the following conditions.

  • $x_i, y_i$ are integers.
  • $0 \leq x_i, y_i \leq N + 40$.
  • The coordinates of all points are pairwise distinct. That is, $(x_i, y_i) \neq (x_j, y_j)$ $(i \neq j)$
  • No choice of $4$ points forms a parallelogram.

Constraints

  • $1 \leq N \leq 3000$
  • All inputs are integers

Sample

Sample 1
Input
4
Output
0 0
3 1
3 2
7 5

The output is as shown in the figure below.

Sample 2
Input
1
Output
0 0

When $N = 1$, any output will be accepted as long as $x_1, y_1$ are integers satisfying $0 \leq x_1, y_1 \leq 41$.

Sample 3
Input
6
Output
0 0
1 28
9 24
11 46
25 37
42 17

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。