| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 37 | 28 | 24 | 72.727% |
Albert는 용돈 벌이를 위해 주변의 회사 빌딩에서 종종 사내 야식 도시락 배달을 하곤 한다.
빌딩은 총 $F$층이고 총 $N$명의 직원이 야근을 하고 있다. 각 층은 동서로 $W$ 칸, 남북으로 $L$ 칸 격자 모양으로 구성된 개방형 오피스로 총 $W \times L$ 개의 칸으로 나뉘어져있다. 직원들은 1번부터 $N$번까지 번호가 붙어있고, $i$ 번째 직원은 $Z_i$층에 위치하며 해당 층의 $(X_i, Y_i)$ 칸에서 야근을 하고 있다 - 이 때 1ドル \le X_i \le W$ 이고 1ドル \le Y_i \le L$ 이다. Albert는 $S_Z$층의 $(S_X, S_Y)$ 칸에 위치한 사내 편의점에서 $N$개의 도시락을 받은 후, $N$명의 직원에게 도시락을 하나씩 배달해야한다. 층간 이동을 위해서는 각 층의 네 곳 구석에 설치된 에스컬레이터를 이용하면 된다 - 즉, 각 층의 $(1, 1),ドル $(W, 1),ドル $(1, L),ドル $(W, L)$ 칸에 에스컬레이터가 있다.
예를 들어 $F = 5,ドル $W = 4,ドル $L = 3,ドル $N = 4,ドル $S_Z = 2,ドル $S_X = 1,ドル $S_Y = 2,ドル 그리고 $Z = [1, 1, 5, 5],ドル $X = [2, 3, 2, 3],ドル $Y = [2, 3, 3, 1]$ 이라 하자. 아래 그림은 각 층의 오피스를 나타내는데, 동서 방향은 좌우로 1번부터 4번칸, 남북 방향은 상하로 1번부터 3번칸을 나타낸다.
Albert는 편의점에서 도시락을 $N$개 받은 이후 최대한 빨리 모든 직원에게 도시락을 하나씩 배달하고 싶다. Albert가 빌딩 내에서 이동하는데 걸리는 시간은 아래와 같다.
직원에게 도시락을 전달하기 위해서는 해당 직원이 있는 칸까지 이동해야 하며, 도시락을 전달하는데 걸리는 시간은 0초라하자. 또한, 필요하다면 이동 중에 직원이 일하는 칸을 지나가도 무방하며 마찬가지로 에스컬레이터가 설치된 칸을 지나가도 된다 (즉, 층간 이동을 하지 않고 그냥 지나가도 괜찮다).
위 예제에서 Albert가 4명의 직원에게 도시락을 전달하는 순서는 총 4! = 24가지 가능하다. 그 중 두 가지 방법에 대하여 배달에 소요되는 총 시간을 살펴보면 아래와 같다.
이 예제에서 방법 1이 가장 빠른 시간 안에 모든 직원에게 도시락을 배달할 수 있는 방법이다.
Albert가 모든 직원에게 도시락을 배달하는데 필요한 최소 시간을 구해보자.
입력 첫 줄에 테스트 케이스의 수 $T$가 주어진다.
각 테스트 케이스의 첫 줄에는 $F,ドル $W,ドル $L,ドル 그리고 $N$이 공백으로 구분되어 주어진다. 둘째 줄에는 편의점의 위치인 $S_Z,ドル $S_X,ドル $S_Y$가 공백으로 구분되어 주어진다. 다음 $N$줄에 걸쳐 각 줄에 3개의 정수가 주어지는데, $i$번째 직원의 위치인 $Z_i,ドル $X_i,ドル $Y_i$가 공백으로 구분되어 주어진다.
각 테스트 케이스의 정답인 도시락을 모두 배달하는데 드는 최소 시간을 각 줄에 출력한다.
4 3 8 7 3 2 1 2 1 4 4 1 7 6 3 5 7 1 10 4 3 1 2 2 1 10 2 1 1 2 1 5 3 1 10 2 7 1 2 2 1 3 1 1 4 2 1 5 1 1 6 2 1 7 1 1 8 2 1 9 1 5 4 3 4 2 1 2 1 2 2 1 3 3 5 2 3 5 3 1
22 12 14 20
예제 1:
예제 2: 이 경우 에스컬레이터를 이용할 필요가 없다. 2, 3, 1번 순서로 배달하는게 최적의 방법이다.
예제 3: 추가 설명 없음.
예제 4: 본문에서 다루었다.