시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB111615268.421%

문제

효빈이는 친구들과 카지노에 방문했다. 효빈이와 함께한 그룹은 총 N명으로 이루어져 있다.

카지노에서 할 게임은 M개의 영역으로 나누어져있는 지도에서 진행된다. 게임이 시작될 때, 각 사람에게는 칩이 1개씩 주어진다.

게임은 총 K개의 라운드로 이루어져 있고, 아래와 같이 진행된다.

  1. 각 플레이어는 M개의 영역 중 하나에 칩을 놓는다.
  2. 딜러가 M개의 영역 중에 하나를 랜덤으로 고른다.
  3. 딜러가 고른 영역에 칩을 놓은 사람은 게임에서 제외된다.

K개의 라운드에서 게임에서 제외되지 않으면 게임을 승리한 것이다.

효빈이와 친구들은 적어도 한 사람이 게임을 승리할 확률을 최대로 하려고 한다. 

N, M, K가 주어졌을 때, 효빈이와 친구들이 게임을 최적의 방법으로 진행했을 때, 적어도 한 사람이 게임을 승리할 확률을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, M, K가 주어진다. (1 ≤ N ≤ 1012, 1 ≤ M, K ≤ 50)

출력

첫째 줄에 적어도 한 사람이 게임을 승리할 확률을 출력한다. 정답과의 절대/상대 오차는 10-3까지 허용한다.

예제 입력 1

3 2 2

예제 출력 1

0.75

예제 입력 2

1 3 3

예제 출력 2

0.2962962962962962

예제 입력 3

4 3 2

예제 출력 3

1.0

예제 입력 4

5 4 5

예제 출력 4

0.87109375

예제 입력 5

1000000000000 2 40

예제 출력 5

0.9094947017729282

힌트

예제 1의 경우에 총 3명이 참가하고, 2개의 영역이 있다.

첫 번째 라운드에 1번 영역에 칩을 하나 놓고, 2번 영역에 칩을 두 개 놓는다.

0.5의 확률로 1번 영역이 선택된다. 이제, 남은 사람의 수는 2명이다. 두 사람이 1번과 2번 영역에 각각 칩을 놓으면, 항상 적어도 1명이 게임을 승리할 수 있다.

0.5의 확률로 2번 영역이 선택된다. 이제, 남은 사람의 수는 1명이다. 이 사람이 두 번째 라운드에서 승리할 확률을 0.5이다.

따라서, 정답은 0.5*1 + 0.5*0.5 = 0.75 이다.

예제 2의 경우에 1명이 참가한다. 따라서, 각 라운드에서 생존할 확률은 (2/3)이다. 따라서, 게임을 승리할 확률은 (2/3)^3 이다.

예제 3의 경우에 최적의 전략은 첫 번째 라운드에 한 영역에 칩을 두 개 놓고, 다른 두 영역에 칩을 1개 놓는다. 칩을 두 개 놓은 영역이 선택된다고 해도 두 번째 라운드에 적어도 한 명은 게임을 승리할 수 있다.

출처