問題一覧 > 通常問題

No.2493 K-th in L2 with L1

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 144
作問者 : KumaTachiRen / テスター : shinchan
0 ProblemId : 9454 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-09-13 22:39:08

問題文

QQ 個の問題を解いてください.i (1iQ)i\ (1\leq i\leq Q) 個目の問題は次です.

  • 問題:非負整数 DiD_i および正整数 KiK_i が与えられます. xyxy 平面上で原点 (0,0)(0,0) とのマンハッタン距離が DiD_i である格子点(xx 座標と yy 座標がともに整数である点)を良い点と呼ぶことにします. 次の 22 条件をみたす良い点 PP が存在するか判定し,存在するならばそのような点を一つ求めてください.
    • 良い点のうち,原点とのユークリッド距離が「PP と原点のユークリッド距離」未満であるものの個数は KiK_i 個未満.
    • 良い点のうち,原点とのユークリッド距離が「PP と原点のユークリッド距離」以下であるものの個数は KiK_i 個以上.
    (上の条件は平たく言うと「原点とのユークリッド距離が良い点の中で KiK_i 番目に小さい」と言えます.)

マンハッタン距離/ユークリッド距離とは
  • 二点 (x1,y1),(x2,y2)(x_1,y_1),(x_2,y_2) 間のマンハッタン距離は x1x2+y1y2|x_1-x_2|+|y_1-y_2| で定義されます.
  • 二点 (x1,y1),(x2,y2)(x_1,y_1),(x_2,y_2) 間のユークリッド距離は (x1x2)2+(y1y2)2\sqrt{(x_1-x_2)^2+(y_1-y_2)^2} で定義されます.

入力

QQ
D1 K1D_1\ K_1
D2 K2D_2\ K_2
 \ \vdots
DQ KQD_Q\ K_Q

  • 1Q1001\leq Q\leq 100
  • 0Di1000\leq D_i\leq 100
  • 1Ki10001\leq K_i\leq 1000
  • 入力は全て整数

出力

各問題について,条件をみたす良い点が存在しないならば

No
と出力してください. 存在するならば一つ求め,それを (x,y)(x,y) としたとき
Yes
x yx\ y
と出力してください.なお条件をみたす良い点が複数存在するときはどれを出力しても構いません.

サンプル

サンプル1
入力
9
2 3
2 7
3 14
100 1
100 10
100 100
100 1000
0 1
0 2
出力
Yes
1 -1
Yes
0 2
No
Yes
50 -50
Yes
-49 51
Yes
38 -62
No
Yes
0 0
No

11 番目の問題について,良い点は下図左の 88 個です.このうち条件をみたすものは (1,1),(1,1),(1,1),(1,1)(-1,-1),(-1,1),(1,-1),(1,1) です.
また 33 番目の問題について,良い点は下図右の 1212 個です.このうち条件をみたすものは存在しません.

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