시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 111 | 61 | 52 | 68.421% |
효빈이는 친구들과 카지노에 방문했다. 효빈이와 함께한 그룹은 총 N명으로 이루어져 있다.
카지노에서 할 게임은 M개의 영역으로 나누어져있는 지도에서 진행된다. 게임이 시작될 때, 각 사람에게는 칩이 1개씩 주어진다.
게임은 총 K개의 라운드로 이루어져 있고, 아래와 같이 진행된다.
K개의 라운드에서 게임에서 제외되지 않으면 게임을 승리한 것이다.
효빈이와 친구들은 적어도 한 사람이 게임을 승리할 확률을 최대로 하려고 한다.
N, M, K가 주어졌을 때, 효빈이와 친구들이 게임을 최적의 방법으로 진행했을 때, 적어도 한 사람이 게임을 승리할 확률을 구하는 프로그램을 작성하시오.
첫째 줄에 N, M, K가 주어진다. (1 ≤ N ≤ 1012, 1 ≤ M, K ≤ 50)
첫째 줄에 적어도 한 사람이 게임을 승리할 확률을 출력한다. 정답과의 절대/상대 오차는 10-3까지 허용한다.
3 2 2
0.75
1 3 3
0.2962962962962962
4 3 2
1.0
5 4 5
0.87109375
1000000000000 2 40
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개 놓는다. 칩을 두 개 놓은 영역이 선택된다고 해도 두 번째 라운드에 적어도 한 명은 게임을 승리할 수 있다.