격자의 각 칸에는 사람이 살거나 살지 않는다. 행은 위에서 아래로 , 열은 왼쪽에서 오른쪽으로 의 번호가 붙어 있다. 격자점의 좌표는 로 나타내며, , 이다.
에서 까지 격자선을 따라 이동하는 경로를 하나 출력해야 한다. 한 번의 이동으로 상하좌우로 인접한 격자점으로 이동할 수 있으며, 격자 밖으로 나갈 수 없다.
사람이 사는 각 칸에 대하여, 그 칸을 이루는 네 꼭짓점 중 하나 이상을 경로가 방문했다면 그 칸에서 비용 이 발생한다. 한 칸의 꼭짓점을 여러 번 방문해도 그 칸의 비용은 한 번만 계산한다. 경로의 비용은 비용이 발생한 칸의 수이다.
구체적인 점수 계산 방식은 Scoring 섹션을 참고한다.
입력은 다음과 같은 형식으로 주어진다.
각 테스트 케이스마다 다음 두 줄을 출력한다.
는 길이가 인 문자열이며, 각 문자는 U, D, L, R 중 하나이다. 각각 현재 격자점에서 위, 아래, 왼쪽, 오른쪽으로 한 칸 이동함을 뜻한다.
가 나타내는 이동은 에서 시작하여 항상 격자 안에 있어야 하고, 마지막에는 에 도착해야 한다.
이 문제의 채점은 각 서브태스크별로 독립적으로 이루어지며, 아래의 근사비 기준은 모든 서브태스크에 동일하게 적용된다.
각 테스트 케이스의 최적 비용을 , 참가자가 출력한 유효한 경로의 실제 비용을 라고 하자. 다음과 같이 근사비 를 정의한다.
첫 번째 테스트 케이스에는 사람이 사는 칸이 없으므로 출력한 경로의 비용은 이다.
두 번째 테스트 케이스에서는 왼쪽 칸에 사람이 살며, 시작점 이 그 칸의 꼭짓점이므로 어떤 경로를 선택해도 비용이 적어도 이다. 예시 경로의 비용은 이다.
세 번째 테스트 케이스에서는 사람이 사는 칸이 존재하지만, 출력한 경로는 그 칸의 어떤 꼭짓점도 방문하지 않는다. 따라서 경로의 비용은 이다.
각 테스트 케이스는 다음과 같은 형식으로 주어진다.
각 는 길이가 인 문자열이며, 각 문자는 0 또는 1이다.
, 인 칸 에 대하여, 의 번째 문자가 1이면 그 칸에 사람이 살고, 0이면 사람이 살지 않는다.
는 출력한 경로의 실제 비용과 정확히 같아야 한다. 또한 다음 조건을 만족해야 한다.
0 또는 1이다.각 서브태스크에 포함된 모든 테스트 케이스의 중 최댓값을 그 서브태스크의 라고 한다. 아래 조건 중 만족하는 가장 높은 비율만큼 해당 서브태스크의 배점을 얻는다.
조건 | 득점 비율 |
|---|---|
모든 테스트 케이스에서 | |
그 외 |
마지막 조건에서 , , 는 각각 동일한 테스트 케이스의 값이다. 최종 점수는 네 서브태스크에서 얻은 점수의 합이다.
출력한 경로가 유효하지 않거나, 함께 출력한 비용이 실제 경로 비용과 다르면 해당 제출의 점수는 점이다.
| 3 | 15 | 추가 조건: 각 테스트 케이스에서 이다. |
| 4 | 65 | 추가 조건: 각 테스트 케이스에서 이다. |
네 번째 테스트 케이스에서는 최적 비용이 이고 출력한 경로의 비용은 이다. 따라서 이 테스트 케이스의 근사비는
이다.
예시 입력에 포함된 모든 테스트 케이스의 근사비가 이하이므로, 이 예시 출력은 모든 서브태스크에서 최고 득점 비율 조건을 만족한다.