[BOJ 13252] 카지노
View as PDF효빈이는 친구들과 카지노에 방문했다. 효빈이와 함께한 그룹은 총 N명으로 이루어져 있다.</p>
카지노에서 할 게임은 M개의 영역으로 나누어져있는 지도에서 진행된다. 게임이 시작될 때, 각 사람에게는 칩이 1개씩 주어진다.
게임은 총 K개의 라운드로 이루어져 있고, 아래와 같이 진행된다.
- 각 플레이어는 M개의 영역 중 하나에 칩을 놓는다.
- 딜러가 M개의 영역 중에 하나를 랜덤으로 고른다.
- 딜러가 고른 영역에 칩을 놓은 사람은 게임에서 제외된다.
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개의 영역이 있다.</p>
첫 번째 라운드에 1번 영역에 칩을 하나 놓고, 2번 영역에 칩을 두 개 놓는다.
0.5의 확률로 1번 영역이 선택된다. 이제, 남은 사람의 수는 2명이다. 두 사람이 1번과 2번 영역에 각각 칩을 놓으면, 항상 적어도 1명이 게임을 승리할 수 있다.
0.5의 확률로 2번 영역이 선택된다. 이제, 남은 사람의 수는 1명이다. 이 사람이 두 번째 라운드에서 승리할 확률을 0.5이다.
따라서, 정답은 0.51 + 0.50.5 = 0.75 이다.
예제 2의 경우에 1명이 참가한다. 따라서, 각 라운드에서 생존할 확률은 (2/3)이다. 따라서, 게임을 승리할 확률은 (2/3)^3 이다.
예제 3의 경우에 최적의 전략은 첫 번째 라운드에 한 영역에 칩을 두 개 놓고, 다른 두 영역에 칩을 1개 놓는다. 칩을 두 개 놓은 영역이 선택된다고 해도 두 번째 라운드에 적어도 한 명은 게임을 승리할 수 있다.
Comments