아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

동전 토너먼트

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

요약
도둑 x명이 1번부터 x번 자리에, 자객 y명이 x+1번부터 x+y번 자리에 서서, 매 경기 가장 큰 번호의 참가자가 floor(k/2) 자리 참가자와 겨루는 토너먼트에서 자객이 우승할 확률을 구한다.
난이도

보통10점 중 7점

유형
확률, 동적 계획법, 수학, 재귀
정답자
아직 제출이 없습니다

문제

도둑 길드가 주최하는 동전 던지기 토너먼트가 열린다. 도둑 xx명과 암살자 yy명, 모두 x+yx + y명이 참가한다. 처음에 각 참가자는 11부터 x+yx + y까지의 정수로 표시되는 위치에 서 있다. 참가자가 둘 이상 남아 있는 동안 경기가 진행된다. 각 경기에서는 가장 큰 번호의 위치에 서 있는 참가자 AA를 선택한다. 그 위치를 kk라 하자. 참가자 AA는 공정한 동전을 던져 위치 ⌊k/2⌋\lfloor k / 2 \rfloor로 이동하려 한다. 그 위치에는 현재 참가자 BB가 서 있다. 앞면이 나오면 AA가 BB의 위치로 이동하고 BB는 토너먼트에서 탈락한다. 뒷면이 나오면 AA가 탈락하고 BB는 같은 위치에 남는다. 마지막까지 남은 참가자가 우승자이다.

암살자 대표단은 등록에 늦어서 도둑들이 11부터 xx까지의 위치를 차지했고, 암살자들은 x+1x + 1부터 x+yx + y까지의 위치를 배정받았다. 토너먼트 회계 담당자는 모든 경기에서 공정한 동전을 사용할 때, 즉 앞면과 뒷면이 나올 확률이 각각 1/21 / 2이고 모든 동전 던지기가 서로 독립일 때 암살자가 우승할 확률을 미리 알고 싶어 한다. 이 확률을 구하여라.

입력

첫째 줄에 두 정수 xx와 yy가 주어진다. xx는 도둑의 수, yy는 암살자의 수이다 (1≤x,y≤1 000 0001 \le x, y \le 1\,000\,000).

출력

구한 확률을 소수로 출력한다. 절대 오차 또는 상대 오차가 10−610^{-6} 미만이면 정답으로 인정된다.

예제2

  1. 예제 1

    입력
    1 1
    
    예상 출력
    0.5
    
  2. 예제 2

    입력
    5 3
    
    예상 출력
    0.312500000000