問題一覧 > 通常問題

No.2597 Yet Another Topological Problem

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 10
作問者 : tko919tko919 / テスター : suisensuisen
5 ProblemId : 9022 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-12-25 00:32:16

問題文

正の既約分数 $p/q$ が与えられます。以下の条件を満たす曲線 $C$ が存在するか判定し、存在する場合はひとつ構成してください。

  • $C$ の端点は相異なる $x$ 軸上の $2$ 点で、片方は原点である。
  • $C$ の端点の距離を $D>0$ と置く。 $x$ 軸に平行で端点がともに $C$ 上にあり、長さが $\dfrac{Dp}{q}$ である線分が存在しない。
出力方法に関しては、"出力" のチャプターを読んでください。

用語の補足

曲線とは $[0,1] \to \mathbb{R}^2$ の連続写像のことを指し、曲線 $C$ の端点とは $C(0),C(1)$ の $2$ 点を指す。

入力

$p\ q$

  • 入力は全て整数
  • $1 \leq p< q \leq 500$
  • $p,q$ は互いに素

出力

条件を満たす曲線が存在しないならば Impossible と出力せよ。
存在するならば、まず 1 行目に Possible と出力せよ。 その後、以下の形式で構成し曲線を出力せよ。

$L$
$x_0\ y_0$
$x_1\ y_1$
$\vdots$
$x_L\ y_L$
これは、曲線として $(x_0,y_0),(x_1,y_1),\ldots,(x_L,y_L)$ をこの順に通る折れ線を選ぶことを意味する。

出力は次の条件を満たしている必要がある。
  • $0\leq |x_i|,|y_i|\leq 250000,x_i,y_i$ は整数 $(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$
また、曲線の長さ $L$ は、 $1≤L≤250000$ を満たす必要がある。
もとの問題で条件を満たす曲線が存在するならば、この出力形式のもとでも存在することが証明できる。

サンプル

サンプル1
入力
2 3
出力
Possible
6
0 0
0 -1
1 -1
1 0
1 1
2 1
2 0



この場合 $D=2$ であり、$x$ 軸に平行な長さ $\frac{4}{3}$ の線分で端点が $C$ に属するものが存在しません。よって、条件を満たしています。

サンプル2
入力
1 3
出力
Impossible

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