11749번 - 형제 게임 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 256 MB | 220 | 60 | 48 | 28.402% |
문제
현성이가 자신의 형 현민이와 게임을 한다. 이 게임은 특정한 맵에서 진행된다.
이 게임에서 사용하는 맵은 N개의 원과 M개의 화살표가 그려져 있는데, 각 화살표는 서로 다른 두 원을 연결하고 있다.
게임을 시작하면, 맨 처음에 말은 1번째 원 위에 있다. 매 턴마다 현민이가 1 이상의 정수를 말한다. 그런 후에는 현성이가 현민이가 말한 수만큼 말을 움직인다. 말은 오직 화살표 방향으로만 이동할 수 있다.
현성이가 말을 움직여서 N번째 원 위로 도착하면 현성이가 이긴다. 다만, 현성이가 말을 더 움직여야 하는 상황에서 N번째 원으로 온 경우는 게임이 끝나지 않는다. 만약 현성이가 말을 움직이다가 더 이상 말을 움직일 수 없는 상황이 온 경우 현민이가 이긴다. 또, 게임이 무한히 반복된다면 현민이의 승리로 간주한다.
현민이는 두뇌 서바이벌 프로그램에서 준우승할 정도로 똑똑하기 때문에 게임을 할 때마다 계속 현민이가 이겼다. 그래서 현민이는 현성이의 멘탈을 위해 조금 봐주기로 했다. 현민이는 현성이를 위해 매 턴을 시작할 때 부르는 수를 a, b, c 중에서 고르기로 했다. 그래도 현성이가 현민이를 이기기에는 역부족이었다.
멘탈이 증발한 현성이는 당신에게 현민이를 이기는 전략을 짜달라고 요청하였다. 현성이를 도와 현민이를 이기는 전략이 있는지 구하고 만약 있다면 최소 몇 턴만에 게임을 끝낼 수 있는지 구하여라.
입력
첫 번째 줄에는 N, M, a, b, c가 주어진다. N은 원의 개수, M은 화살표의 개수, a, b, c는 현민이가 부르는 수를 의미한다. (2 ≤ N ≤ 50, 0 ≤ M ≤ N(N-1), 1 ≤ a, b, c ≤ 100)
두 번째 줄부터 M개의 줄에는 각 화살표의 시작점, 끝점 u, v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 어떤 두 화살표에 대해서도 시작점과 끝점이 완전히 같지는 않다.
출력
만약 현성이가 현민이를 이길 수 없다면 'IMPOSSIBLE'을 출력한다.
그렇지 않은 경우, 현성이가 현민이를 이기기 위해 필요한 최소 턴의 수를 출력한다.
예제 입력 1
3 3 1 2 4 1 2 2 3 3 1
예제 출력 1
IMPOSSIBLE
예제 입력 2
8 12 1 2 3 1 2 2 3 1 4 2 4 3 4 1 5 5 8 4 6 6 7 4 8 6 8 7 8
예제 출력 2
2
힌트
첫 번째 예제에서는 현민이가 1, 2를 번갈아 부르면 게임이 끝나지 않기 때문에 현민이가 이긴다.
두 번째 예제에서는 아래와 같은 전략을 세우면 된다.
- 만약 현민이가 2나 3을 부른다면 한 번만에 N번 원으로 갈 수 있다.
- 만약 현민이가 1을 부른다면 4번 원으로 가는 것이 최적이다. 현성이가 4번 원으로 간다면 현민이가 다음 턴에 무슨 수를 부르던지 한 번에 N번 원으로 갈 수 있다. 만약 현성이가 5번 원으로 간다면 현민이가 2나 3을 부르면 현민이가 이긴다. 현성이가 2번 원으로 간다면 현성이가 이길 수는 있지만 더 많은 턴을 요구한다.
두 번째 예제의 맵
출처
ICPC > Regionals > Asia Pacific > Japan > Asia Regional Contest 2015 in Tsukuba C번
- 문제를 번역한 사람: functionx
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호