시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
10 초 | 128 MB | 17 | 1 | 1 | 16.667% |
최흉최악의 해커 yum3은 팰린드롬에 집착하는 경향이 있다(정작 자신의 이름은 팰린드롬이 아니다).
어느 날 yum3은 도시 s에서 출발하여 도시 t로 여행을 떠나게 되었다. 이 세계의 도시와 도시 사이에 있는 모든 길에는 알파벳 대문자가 하나 적혀 있다. 같은 두 도시 사이에 길이 여러 개 존재할 수는 있지만, 시작점과 도착점이 같은 길은 없다.
yum3은 도시 t에 도착할 때까지는 현재 도시에서 인접한 길 중 하나로 균등한 확률로 이동하며, 같은 도시나 길을 여러 번 지나도 상관없다. 단, 도시 t에 도착하거나 도시 t로 갈 수 없는 어떤 도시에 이르게 되면 여행을 즉시 멈춘다. 그리고 t에 도착했으면서 출발지부터 지나온 길에 적혀있던 글자들을 순서대로 나열하여, 만약 그것이 팰린드롬이면 lucky하다고 느낀다. 만약 t에 도착할 수 없게 되거나 경로가 팰린드롬을 이루지 않으면 lucky하지 못하다.
yum3이 lucky한 여행을 할 수 있을 확률은 얼마일까?
첫째 줄에 테스트 케이스의 개수 T(≤ 100)가 주어진다. 이어서 각 테스트 케이스가 여러 줄에 걸쳐 주어진다.
각 테스트 케이스는 빈 줄로 시작하고, 이어서 한 줄에 도시의 개수 n, 길의 개수 m이 주어진다(2 ≤ n ≤ 12, 0 ≤ m ≤1000). 이어서 m개의 줄에 각 길의 정보 정수 u, v(0 ≤ u, v < n, u ≠ v), 알파벳 대문자 w가 주어지는데 이는 도시 u에서 도시 v로 가는 일방향 길이 존재하며 그 길에 적힌 글자가 w라는 의미이다. 이어서 하나의 줄에 질문의 개수를 의미하는 정수 q(≤ 150)가 주어지고, 이어서 q개의 줄에 질문 s, t(0 ≤ s, t < n, s ≠ t)가 주어지는데 이는 출발지가 도시 s, 도착지가 도시 t라는 의미이다.
각 테스트 케이스마다 첫째 줄에 양식에 맞게 테스트 케이스 번호를 출력하고, 이어서 각 줄마다 질문에 대한 답을 출력한다. 각 값은 정답과 10-4 미만의 오차가 나면 정답으로 인정된다.
2 4 3 0 1 A 1 2 A 2 3 A 2 0 3 2 0 5 4 1 2 B 2 3 D 2 4 A 2 0 B 2 1 3 1 0
Case 1: 1.000000 0.000000 Case 2: 0.000000 0.333333
ICPC > Regionals > Asia Pacific > Thailand > 2013 ACM-ICPC Asia Phuket Regional Programming Contest H번