시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 335 85 42 32.812%

문제

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

이런 문제를 생각해볼 수 있다. "도착하기 위해 주사위를 굴려야 하는 횟수의 기댓값은 얼마일까?" 하지만 우리는 이 문제를 푸는 게 아니라, 이 문제의 테스트케이스를 만들어야 한다.

정답이 50,000,000,000,000,000,000 이상인 테스트케이스를 만들어 보자.

입력

입력은 없다.

출력

첫 줄에 자연수 N, M, S를 출력한다. N은 100 이하, M은 20 이하, S는 N/2 이하여야 한다.

다음 S줄에는 한 줄에 하나씩 뱀이나 사다리의 시작점과 도착점을 출력한다. (도착점이 시작점보다 작으면 뱀, 크면 사다리이다.) 시작점은 1 이상 N-1 이하, 도착점은 1 이상 N 이하여야 한다. 모든 시작점과 도착점 중 중복되는 점은 없어야 한다.

말이 어느 칸에 놓여 있어도 게임을 끝낼 수 있음이 보장되어야 한다. 심지어 도달 자체가 불가능한 칸에 일부러 말을 놓거나, 뱀이나 사다리의 시작점에 말을 올려 놓고 뱀/사다리를 타지 않은 채로 시작해도 게임을 끝낼 수 있어야 한다. 전혀 이해할 수 없는 조건이지만, 구데기컵이니까 그러려니 하자.

아래 예제 출력은 형식에 맞는 출력을 보여주는 것일 뿐, 정답이 아님에 유의하라.

예제 입력 1


						

예제 출력 1

4 2 1
2 4

출처

Contest > 구데기컵 > 제1회 구데기컵 😨번

제출할 수 있는 언어

Text

채점

  • 예제는 채점하지 않는다.