시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1.5 초 128 MB 150 6 5 14.706%

문제

뱀과 사다리는 유명한 주사위 게임이다. 맨 처음에는 말이 보드의 바깥에 있다. 턴이 시작될 때 $M$면체 주사위를 굴린다. $1$ 이상 $M$ 이하의 자연수가 나오고, 각 자연수가 나올 확률은 $1/M$이다. 나온 자연수만큼 말을 전진시키고 (보드의 바깥에 있으면 나온 자연수에 해당하는 칸으로 이동한다), 뱀이나 사다리가 있으면 그것이 가리키는 칸으로 이동한다. $N$번 칸에 도달하면 게임이 끝난다. 도착점이 $N$번을 넘어가도 도착으로 간주한다.

무한루프에 빠지는 것은 이론적으로 가능하지만, 정상적으로 설계된 게임이라면 어느 칸에 말이 놓여 있든 도착점까지 가는 방법이 존재해야 한다. 그렇지 않은 게임을 “잘못 설계된 게임”이라고 하자.

게임을 끝낼 때까지 주사위를 굴리는 횟수의 기대값은 얼마일까?

입력

첫 줄에 $N$, $M$, 뱀과 사다리의 개수 $S$가 주어진다.($1 \leq N \leq 100$, $1 \leq M \leq 20$, $0 \leq S \leq N/2$) 다음 S줄에는 한 줄에 하나씩 뱀이나 사다리의 시작점과 도착점이 주어진다. (도착점이 시작점보다 작으면 뱀, 크면 사다리다.) 시작점은 $1$ 이상 $N-1$ 이하, 도착점은 $1$ 이상 $N$ 이하이다. 모든 시작점과 도착점 중 중복되는 점은 없다.

출력

게임을 끝낼 때까지 주사위를 굴리는 횟수의 기대값을 출력한다. $10^{-3}$ 이하의 절대 혹은 상대오차를 허용한다. 잘못 설계된 게임이면 $-1$을 출력한다.

예제 입력 1

4 2 1
2 4

예제 출력 1

1.75

예제 입력 2

6 2 3
4 2
5 3
1 6

예제 출력 2

-1

출처

University > KAIST > 2017 KAIST 7th ACM-ICPC Mock Competition E번

  • 데이터를 추가한 사람: doju
  • 문제를 만든 사람: jh05013