問題一覧 > 通常問題

No.2923 Mayor's Job

レベル : / AI推定難易度 : 625 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 155
作問者 : mymelochan / テスター : 👑 loop0919 hirayuu_yc tnodino kusirakusira 👑 KA37RI uruzunyaa
お気に入りにしたユーザー ProblemId : 11056 / 自分の提出
問題文最終更新日: 2024-10-12 14:06:52
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
第3回緑以下コンテスト (順位表) の他の問題:

Problem Statement

You are the mayor of Midori-ika City, which has $N$ shrines. The $i$-th shrine has a history of $H_i$ years and is located at the point $(X_i,Y_i)$.

Since Midori-ika City currently has too many shrines, you have decided to perform the following operation some number of times to reduce the number of shrines. $1$ operation consists of the following steps.

  1. Choose distinct shrines $i,j$ that have not yet been removed. Here, $H_i \lt H_j$ must hold and the Euclidean distance between the shrines must be at most $K$.
  2. Remove shrine $i$. Shrine $j$ remains as it is.

You may perform this operation as many times as you like, as long as it is possible ($0$ times is also allowed).

When you perform the operations so as to minimize the number of remaining shrines, find how many shrines remain.

The Euclidean distance between the points $(x_1,y_1)$ and $(x_2,y_2)$ is defined as $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$.

Constraints

  • $1\leq N \leq 2000$
  • $1\leq K \leq 10^9$
  • $1\leq H_i \leq 10^9$
  • $1\leq X_i,Y_i \leq 10^9$
  • All inputs are integers.

Input

$N \ K$
$H_1 \ \ H_2 \ ... \ H_N$
$X_1 \ Y_1$
$X_2 \ Y_2$
:
$X_N \ Y_N$

Output

Print the answer on $1$ line.

Sample

Sample 1
Input
4 2
13 7 2 16
1 1
1 3
2 4
11 10
Output
2

First, let $i=3, j=2$.

Here, the Euclidean distance between shrine $3$ and shrine $2$ is $\sqrt{2} \leq K$, and furthermore $H_3 \lt H_2$, so the operation can be performed. As a result, shrine $3$ is removed.

Next, perform the operation with $i=2, j=1$ to remove shrine $2$.

Shrine $4$ is too far from the other shrines, so no operation can be performed with it and any other shrine.

After this sequence of operations, the number of remaining shrines is $2$. There is no way to reduce the shrines further, so print $2$.

Sample 2
Input
3 2
1 2 2
1 1
1 1
1 3
Output
2

Multiple shrines may exist at the same coordinates.

Also, shrine $2$ and shrine $3$ have equal histories, so the operation cannot be performed on them.

Sample 3
Input
19 8
70 90 200 93 73 47 87 115 193 102 50 47 146 11 134 178 175 185 41
13 10
20 13
15 29
23 27
25 17
20 12
11 27
16 12
16 26
18 14
14 2
9 6
15 5
22 1
11 22
14 20
19 18
30 18
18 24
Output
4

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