레이팅 미적용농부 존은 농장 운영의 모든 면에서 매우 믿음직하지만, 단 한 가지 예외가 있다. 그는 잔디를 제때, 논리적으로 깎는 데는 형편없다.
농장은 정사각형 단위 칸들로 이루어진 커다란 2차원 격자이다. FJ는 시각 \(t = 0\)에 이 칸들 중 하나에서 출발하여 그 칸의 잔디를 깎는데, 처음에는 이 칸만이 잔디가 깎인 유일한 칸이다. FJ의 이후 잔디 깎기 패턴은 \(N\)개의 지시로 이루어진 수열로 표현된다. 예를 들어 첫 번째 지시가 "W 10"이면, 시각 \(t = 1\)부터 \(t = 10\)까지(즉, 다음 10단위 시간 동안) FJ는 서쪽으로 한 칸씩 이동하며 그 과정에서 잔디를 깎는다. 이 단계들을 마치면 시각 \(t = 10\)에 서쪽으로 10칸 떨어진 곳에 있게 되며, 지나온 모든 칸의 잔디를 깎은 상태가 된다.
FJ의 진행이 너무 느려서, 그가 깎은 잔디 일부는 그가 잔디 깎기를 모두 마치기 전에 다시 자랄 수도 있다. 시각 \(t\)에 깎인 잔디는 시각 \(t + x\)에 다시 자라난다.
FJ의 잔디 깎기 패턴은 같은 칸을 여러 번 다시 방문하게 할 수도 있지만, 그는 잔디가 이미 깎여 있는 칸을 만난 적이 한 번도 없다고 말한다. 즉, 그가 어떤 칸을 방문할 때마다, 같은 칸에 대한 가장 최근 방문은 잔디가 다시 자라 있을 만큼 최소 \(x\)단위 시간 이전이어야 한다.
FJ의 관찰이 유효하게 유지되는 \(x\)의 최댓값을 구하시오.
Problem credits: Brian Dean
Problem credits: Brian Dean
입력의 첫째 줄에 \(N\)(\(1 \leq N \leq 100\))이 주어진다. 나머지 \(N\)개의 줄에는 각각 'D S' 형태의 지시가 하나씩 주어진다. 여기서 D는 방향을 나타내는 문자(N=북, E=동, S=남, W=서)이고, S는 그 방향으로 이동하는 걸음 수(\(1 \leq S \leq 10\))이다.
FJ가 잔디가 깎인 칸을 밟는 일이 없도록 하는 \(x\)의 최댓값을 출력한다. FJ가 어떤 칸도 두 번 이상 방문하지 않는다면 -1을 출력한다.
mowing.in · 출력을 쓸 파일 mowing.out6
N 10
E 2
S 3
W 4
S 5
E 810In this example, FJ steps on a cell at time 17 that he stepped on earlier at
time 7; therefore, \(x\) must be at most 10 or else the grass from his first visit
would not yet have grown back. He also steps on a cell at time 26 that he also
visited at time 2; hence \(x\) must also be at most 24. Since the first of these
two constraints is tighter, we see that \(x\) can be at most 10.
riseoj 작성
출처 올림피아드 > USACO > 2015-2016 > January > Bronze