No.2493 K-th in L2 with L1
レベル :
/ AI推定難易度 : 650
/ 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 147
作問者 :
KumaTachiRen
/ テスター :
shinchan
タグ : / 解いたユーザー数 147
作問者 :
shinchan
問題文最終更新日: 2023-09-13 22:39:08
English (AI translation)
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$.
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もしくは右上の雲マークをクリックしてアカウントを作成してください。