問題一覧 > 通常問題

No.2597 Yet Another Topological Problem

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : （AC するまで非表示） / 解いたユーザー数 10
作問者 : tko919 / テスター : suisen
お気に入りにしたユーザー ProblemId : 9022 / 自分の提出
問題文最終更新日: 2023-12-25 00:32: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
Advent Calendar Contest 2023 (順位表) の他の問題:

Problem Statement

You are given a positive irreducible fraction $p/q$. Determine whether there exists a curve $C$ satisfying the following conditions, and if one exists, construct one.

  • The endpoints of $C$ are $2$ distinct points on the $x$-axis, one of which is the origin.
  • Let $D>0$ be the distance between the endpoints of $C$. There does not exist a line segment parallel to the $x$-axis, with both endpoints on $C$, whose length is $\dfrac{Dp}{q}$.
For the output method, read the "Output" section.

Supplementary notes on terminology

A curve is a continuous map $[0,1] \to \mathbb{R}^2$, and the endpoints of a curve $C$ are the $2$ points $C(0),C(1)$.

Input

$p\ q$

  • All inputs are integers.
  • $1 \leq p< q \leq 500$
  • $p,q$ are coprime.

Output

If no curve satisfying the conditions exists, print Impossible.
If one exists, first print Possible on the first line. Then, output the constructed curve in the following format.

$L$
$x_0\ y_0$
$x_1\ y_1$
$\vdots$
$x_L\ y_L$
This means choosing, as the curve, the polyline that passes through $(x_0,y_0),(x_1,y_1),\ldots,(x_L,y_L)$ in this order.

The output must satisfy the following conditions.
  • $0\leq |x_i|,|y_i|\leq 250000,x_i,y_i$ are integers $(0 \leq i \leq L)$
  • $|x_i-x_{i+1}|+|y_i-y_{i+1}|=1(0 \leq i \leq L-1)$
  • $(x_0,y_0)=(0,0),x_L \neq 0,y_L=0$
Also, the length $L$ of the curve must satisfy $1≤L≤250000$.
It can be proved that if a curve satisfying the conditions exists in the original problem, then one also exists under this output format.

Sample

Sample 1
Input
2 3
Output
Possible
6
0 0
0 -1
1 -1
1 0
1 1
2 1
2 0



In this case, $D=2$, and there is no line segment parallel to the $x$-axis of length $\frac{4}{3}$ whose endpoints belong to $C$. Therefore, the conditions are satisfied.

Sample 2
Input
1 3
Output
Impossible

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