10053번 - 필승 전략 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 8 초 | 128 MB | 101 | 26 | 24 | 26.667% |
문제
원숭이와 멍멍이는 보드게임을 하고 있다. 보드판은 여러개의 위치로 나뉘며 각 위치는 알파벳 소문자 1개 (a, b, c, d, ...) 로 이름이 붙여져 있고, 게임말을 사용해 현재 위치를 표시한다. 이 게임은 매 라운드마다 다음과 같은 2개의 과정을 거친다.
- 원숭이가 선택을 한다. 게임말의 현재 위치에 따라 원숭이가 고를 수 있는 선택지들이 정해지고, 그 중의 하나를 선택해야 한다. 선택지는 보드판 위의 위치들의 집합이다.
- 멍멍이가 선택을 한다. 멍멍이는 첫 번째 과정에서 원숭이가 선택한 선택지 안에 있는 위치들 중에서 하나를 선택한 후 게임말을 그 위치로 움직인다. 이 위치가 다음 라운드의 위치가 된다.
첫 번째 라운드를 시작하기 전에, 원숭이와 멍멍이는 각각 위치를 하나 고른다. 멍멍이가 고른 위치는 게임말의 시작위치가 된다. 원숭이가 고른 위치는 게임이 끝나는 위치가 된다. 원숭이는 멍멍이가 움직이는 게임말을 자기가 고른 위치에 오도록 만들면 승리한다. 더 스릴넘치는 게임을 위해 두 사람은 돈을 걸고 플레이한다. 원숭이가 이기면 멍멍이는 원숭이에게 전재산을 주어야 한다. 하지만 원숭이는 매 라운드가 끝날 때 마다 멍멍이에게 일정 금액을 주어야 한다. 따라서 이 게임은 원숭이가 게임말을 끝위치로 오게 만들어 원숭이가 승리하든지, 아니면 원숭이의 돈이 다 떨어져서 패가망신하든지 둘 중 하나로 끝나게 된다.
원숭이와 멍멍이는 항상 최적의 전략으로 게임을 플레이한다. 원숭이는 항상 게임을 이기는 쪽으로 선택을 하고, 멍멍이는 원숭이가 이기는 것을 막도록 노력한다.
원숭이는 모든 경우의 시작위치와 끝위치에 대해서 자기가 게임을 이길 수 있는지, 이길 수 있다면 몇 라운드만에 이길 수 있는지 알고 싶어졌다.
입력
입력으로 한 개의 테스트케이스가 주어진다. 첫 번째 줄에는 보드판 위의 위치의 개수 n (1 ≤ n ≤ 25) 이 주어진다. n개 위치의 이름은 알파벳 소문자 중 처음 n개를 사용한다. 나머지 n개의 줄에는 각 위치 p에 대한 정보가 위치를 나타내는 알파벳 순으로 주어진다. 각 줄의 처음에는 선택지의 개수 m (1 ≤ m < 2n) 이 주어지고, 그 뒤로 m개의 중복되지 않는 문자열이 주어진다. 각 문자열은 하나의 선택지를 나타내며 멍멍이가 선택할 수 있는 위치들을 담고 있다. 문자열의 길이는 1 이상이며 각 글자는 알파벳 순으로 정렬되어 주어지고, 중복되는 글자는 없다. 테스트 케이스에 주어지는 선택지 개수의 합은 최대 106 이다.
출력
위치를 나타내는 알파벳 순으로 각 위치 p에 대해 한 줄을 출력한다. 각 줄 마다 위치를 나타내는 알파벳 순으로 각 위치 q에 대해 시작위치가 p이고 끝위치가 q인 게임을 원숭이가 이길 수 있는 최소 라운드 수를 출력한다. 원숭이가 패가망신하는 경우엔 -1을 출력한다.
예제 입력 1
2 2 ab b 1 b
예제 출력 1
0 1 -1 0
출처
ICPC > World Finals > ACM-ICPC World Finals 2014 D번
- 문제를 번역한 사람: ntopia
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호