만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

몬티의 홀

면접 대비

시간 제한1초메모리 제한1024 MB

요약
d개의 문 중 s개를 고른 뒤 몬티가 빈 문 e개를 열면 다시 s개를 선택해 얻을 수 있는 최고 승률을 구합니다.
난이도

보통10점 중 5점

유형
확률, 수학, 그리디
정답자
아직 제출이 없습니다

문제

당신은 오래전 사라진 도시 아래의 깊은 지하 묘지를 몇 시간째 탐험했고, 마침내 그 끝에 다다랐다. 언데드 마법사 몬티의 홀이다. 그의 잠들지 못한 영혼이 당신 앞에 모습을 드러내고, 당신은 전투를 준비한다.

그런데 백 년 만에 처음으로 자신을 찾아온 탐험가가 당신이라는 사실이 드러나고, 그는 지독하게 지루해져 있다. 싸우는 대신 그는 자신의 유물을 걸고 게임을 제안한다. 홀에는 닫힌 문이 dd개 있고 그중 하나만 유물로 이어진다(물론 몬티는 어느 문인지 안다). 진행 방식은 다음과 같다.

  1. 당신은 닫힌 문 중 ss개를 고른다.
  2. 몬티는 당신이 고르지 않았고 빈 방으로 이어지는 문 ee개를 연다.
  3. 남은 닫힌 문 중에서 당신은 원하는 대로 ss개의 선택을 바꿀 수 있다(원한다면 지금 선택을 그대로 유지해도 된다).
  4. 몬티가 유물이 있는 방으로 이어지는 문을 공개한다.

유물이 있는 문이 당신이 고른 문 중에 있으면 당신이 이기고, 다치지 않은 채 유물을 가져갈 수 있다. 그렇지 않으면 몬티가 당신을 염소로 변하게 할 것이다. 그러니 오늘은 운이 따라 주기를 바라는 수밖에 없다.

입력

입력은 다음과 같다.

  • 한 줄에 정수 dd, ss, ee가 주어진다(1≤d,s,e≤1061 \le d,s,e \le 10^{6}, s+e<ds + e < d). dd는 몬티의 홀에 있는 문의 수, ss는 당신이 고를 수 있는 문의 수, ee는 2단계에서 몬티가 여는 문의 수다.

출력

최적으로 플레이했을 때 몬티의 게임에서 이길 확률을 출력한다. 답의 절대 오차 또는 상대 오차는 10−610^{-6} 이하여야 한다.

예제3

  1. 예제 1

    입력
    3 1 1
    
    예상 출력
    0.666667
    
  2. 예제 2

    입력
    8 4 2
    
    예상 출력
    0.75
    
  3. 예제 3

    입력
    15 4 2
    
    예상 출력
    0.32592593