시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 59 | 20 | 18 | 40.909% |
이 문제에서 두 지점 사이의 거리는 택시 거리로 계산된다. 두 점 $(x_1, y_1)$과 $(x_2, y_2)$ 사이의 택시 거리는 $(|x_1 - x_2| + |y_1 - y_2|)$이다.
앤디를 싫어하는 싸이컴 부원 $N$명이 앤디를 공격하려고 한다. 각 부원이 앤디를 공격할 때, 다음과 같은 성질을 가진다.
앤디를 물리치려면 $N$명의 공격력의 합이 앤디의 체력 $k$ 이상이 되어야 한다.
예를 들어, $k=23$이고 아래와 같이 위치하는 경우를 생각하자. 아래 예시는 예제 1과 같다.
위와 같은 위치에서 앤디를 공격할 수 있는 사람은 1과 2 뿐이므로 앤디가 받는 공격량은 17이다. 여기서 3번을 왼쪽으로 5만큼 움직였을 때, 앤디가 받는 공격이 25가 되므로 앤디를 물리칠 수 있고, 이 경우가 최적이다.
$k$와 앤디를 포함한 싸이컴 부원 $N+1$명의 위치 및 시야 방향이 주어질 때, 앤디를 물리치기 위해 필요한 $N$명의 이동 거리의 합의 최솟값을 출력하라. 단, 여러 명이 같은 위치에 존재해도 문제가 없으며, 공간에는 제약이 없어 얼마든지 원하는 방향으로 이동할 수 있다고 가정한다.
첫 줄에 두 정수 $N$과 $k$가 주어진다.
둘째 줄에 앤디의 좌표 $X_0$와 $Y_0$가 주어진다.
셋째 줄부터 $N+2$번째 줄까지 $N$명의 좌표 정보와 시야 정보가 주어진다. 구체적으로 $i+2$번째 줄에는 $i$번째 부원의 좌표 $X_i$와 $Y_i$, 그리고 보는 방향 $S_i$가 주어진다. $S_i$는 0, 1, 2, 3 중 하나이며, 각각 $+x$, $-x$, $+y$, $-y$ 방향을 의미한다.
앤디를 물리치기 위해 필요한 $N$명의 이동 거리의 합의 최솟값을 출력한다.
3 23 5 5 5 11 3 12 9 1 6 1 0
5
문제 이미지의 방향은 아래와 같다.
High School > 서울과학고등학교 > SciOI 2022 E번