시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1.5 초 128 MB 170 20 5 16.667%

문제

뱀과 사다리는 유명한 주사위 게임이다. 맨 처음에는 말이 보드의 바깥에 있다. 턴이 시작될 때 $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$ 이하이다. 모든 시작점과 도착점 중 중복되는 점은 없다.

출력

게임을 끝낼 때까지 주사위를 굴리는 횟수의 기대값을 출력한다. 미리 구해 놓은 정답의 1/10배보다 크거나 같고, 10배보다 작거나 같으면 정답이다.

예제 입력 1

4 2 1
2 4

예제 출력 1

1.75

출처

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

  • 데이터를 추가한 사람: doju
  • 잘못된 조건을 찾은 사람: jh05013