시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 243 | 87 | 80 | 42.781% |
수빈이는 여행을 좋아한다. 더 이상 지구에서 여행할 곳이 없어진 수빈이는 N차원 우주로 여행을 떠났다. 우주의 각 점은 좌표 N개로 이루어 지며, 각각의 좌표는 1부터 N까지 인덱스가 매겨져 있다.
수빈이는 원점(모든 좌표가 0인 곳)에서 여행을 시작하며, 아래와 같은 방법으로 움직인다.
수빈이는 여행을 떠나기 전에 여행 계획을 작성해 놓았고, 같은 점을 두 번 이상 방문하는지 아닌지 알아보려고 한다.
수빈이가 여행 계획에서 고른 좌표 인덱스와, 좌표가 증가하는 방향으로 이동했는지, 감소하는 방향으로 이동했는지가 주어진다. 수빈이가 첫 번째 점과 마지막 점을 포함한 모든 점을 중복해서 방문하지 않게 방문할 수 있다면 1을, 아니면 0을 구하는 프로그램을 작성하시오.
첫째 줄에 N (1 ≤ N ≤ 1,000,000,000)이 주어진다.
둘째 줄에는 수빈이의 여행 계획의 길이 M (1 ≤ M ≤ 50)이 주어진다.
셋째 줄에는 수빈이가 여행 계획에서 고른 좌표의 인덱스가 순서대로 주어진다.
넷째 줄에는 증가하는 방향으로 이동할 것인지, 감소하는 방향으로 이동할 것인지를 나타내는 문자열이 주어지며, +는 증가하는 방향, -는 감소하는 방향을 나타낸다.
모든 점을 중복해서 방문하지 않을 수 있으면 1을, 아니면 0을 출력한다.
1 1 1 +
1
2 4 1 2 1 2 ++--
0
3 5 1 2 3 1 2 +++--
1
예제 2의 경우에 (0,0) -> (1,0) -> (1,1) -> (0,1) -> (0,0)으로 이동하게 되어서 (0, 0)을 두 번 방문하게 되고, 예제 3의 경우에는 (0,0,0) -> (1,0,0) -> (1,1,0) -> (1,1,1) -> (0,1,1) -> (0,0,1) 으로 방문하게 되어서 모든 점을 중복하지 않게 방문한다.