몬티의 홀
면접 대비시간 제한1초메모리 제한1024 MB
d개의 문 중 s개를 고른 뒤 몬티가 빈 문 e개를 열면 다시 s개를 선택해 얻을 수 있는 최고 승률을 구합니다.
문제
당신은 오래전 사라진 도시 아래의 깊은 지하 묘지를 몇 시간째 탐험했고, 마침내 그 끝에 다다랐다. 언데드 마법사 몬티의 홀이다. 그의 잠들지 못한 영혼이 당신 앞에 모습을 드러내고, 당신은 전투를 준비한다.
그런데 백 년 만에 처음으로 자신을 찾아온 탐험가가 당신이라는 사실이 드러나고, 그는 지독하게 지루해져 있다. 싸우는 대신 그는 자신의 유물을 걸고 게임을 제안한다. 홀에는 닫힌 문이 개 있고 그중 하나만 유물로 이어진다(물론 몬티는 어느 문인지 안다). 진행 방식은 다음과 같다.
- 당신은 닫힌 문 중 개를 고른다.
- 몬티는 당신이 고르지 않았고 빈 방으로 이어지는 문 개를 연다.
- 남은 닫힌 문 중에서 당신은 원하는 대로 개의 선택을 바꿀 수 있다(원한다면 지금 선택을 그대로 유지해도 된다).
- 몬티가 유물이 있는 방으로 이어지는 문을 공개한다.
유물이 있는 문이 당신이 고른 문 중에 있으면 당신이 이기고, 다치지 않은 채 유물을 가져갈 수 있다. 그렇지 않으면 몬티가 당신을 염소로 변하게 할 것이다. 그러니 오늘은 운이 따라 주기를 바라는 수밖에 없다.
입력
입력은 다음과 같다.
- 한 줄에 정수 , , 가 주어진다(, ). 는 몬티의 홀에 있는 문의 수, 는 당신이 고를 수 있는 문의 수, 는 2단계에서 몬티가 여는 문의 수다.
출력
최적으로 플레이했을 때 몬티의 게임에서 이길 확률을 출력한다. 답의 절대 오차 또는 상대 오차는 이하여야 한다.