問題一覧 > 通常問題

No.2493 K-th in L2 with L1

レベル : / AI推定難易度 : 650 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 147
作問者 : KumaTachiRen / テスター : shinchan
お気に入りにしたユーザー ProblemId : 9454 / 自分の提出
問題文最終更新日: 2023-09-13 22:39:08
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 407 (順位表) の他の問題:

Problem Statement

Solve $Q$ problems. The $i\ (1\leq i\leq Q)$-th problem is as follows.

  • Problem: You are given a non-negative integer $D_i$ and a positive integer $K_i$. On the $xy$-plane, a lattice point (a point whose $x$-coordinate and $y$-coordinate are both integers) whose Manhattan distance from the origin $(0,0)$ is $D_i$ is called a good point. Determine whether there exists a good point $P$ satisfying the following $2$ conditions, and if one exists, find one such point.
    • The number of good points whose Euclidean distance from the origin is less than "the Euclidean distance between $P$ and the origin" is less than $K_i$.
    • The number of good points whose Euclidean distance from the origin is at most "the Euclidean distance between $P$ and the origin" is at least $K_i$.
    (Put plainly, the above conditions say that "its Euclidean distance from the origin is the $K_i$-th smallest among the good points".)

What are Manhattan distance and Euclidean distance?
  • The Manhattan distance between two points $(x_1,y_1),(x_2,y_2)$ is defined as $|x_1-x_2|+|y_1-y_2|$.
  • The Euclidean distance between two points $(x_1,y_1),(x_2,y_2)$ is defined as $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$.

Input

$Q$
$D_1\ K_1$
$D_2\ K_2$
$\ \vdots$
$D_Q\ K_Q$

  • $1\leq Q\leq 100$
  • $0\leq D_i\leq 100$
  • $1\leq K_i\leq 1000$
  • All input values are integers.

Output

For each problem, if no good point satisfying the conditions exists, print

No
. If one exists, find one and, denoting it by $(x,y)$, print
Yes
$x\ y$
. If multiple good points satisfy the conditions, you may print any of them.

Sample

Sample 1
Input
9
2 3
2 7
3 14
100 1
100 10
100 100
100 1000
0 1
0 2
Output
Yes
1 -1
Yes
0 2
No
Yes
50 -50
Yes
-49 51
Yes
38 -62
No
Yes
0 0
No

For the $1$-st problem, the good points are the $8$ points shown on the left of the figure below. Among them, those satisfying the conditions are $(-1,-1),(-1,1),(1,-1),(1,1)$.
For the $3$-rd problem, the good points are the $12$ points shown on the right of the figure below. None of them satisfies the conditions.

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