문어 게임

이미지 출처: wikimedia.org

문어 게임 2022가 시작되었다. Kolkrabbi로도 알려진 Arnar는 거액의 상금을 두고 겨루는 이 흥미진진한 대회에 많은 참가자를 초대했다. 대회는 서로 다른 여러 게임으로 구성된다. 처음에는 참가자가 $1\,234\,567$명이었지만, 지난 네 게임을 치르는 동안 많은 참가자가 대회에서 탈락했다. 따라서 참가자는 $m$명만 남아 있다.

이제 다섯 번째 게임을 시작할 차례이며, 참가자들은 한 줄로 선다. 줄 맨 앞에 선 사람은 다름 아닌 Hlini이다. 그는 다음 게임이 열리는 방으로 들어가 자신이 발판 위에 서 있다는 것을 알아차린다. 방 반대편에는 또 다른 발판이 있고, 그 사이에는 커다란 다리가 놓여 있다. 하지만 이는 평범한 다리가 아니다. 다리는 $n$개의 줄로 이루어져 있으며, 각 줄에는 두 개의 유리 칸이 있다. 따라서 참가자는 각 줄에서 밟을 유리 칸 하나를 선택하며 유리 다리를 건너야 한다.

유리 칸들은 똑같아 보이지만, 실제로도 같다고 가정하는 것은 매우 위험하다. 각 줄의 한 칸은 강화유리로 되어 있어 한 사람의 무게를 견딜 수 있다. 다른 칸은 강화유리가 아니므로 그 칸을 밟은 사람의 무게로 깨진다. 그러면 그 사람은 아래로 떨어져 게임에서 탈락한다.

Arnar가 게임 규칙을 설명하자 Hlini는 이렇게 말한다. ``이건 그냥 반반이야. 건너거나, 못 건너거나 둘 중 하나잖아.'' Arnar는 앞으로 한 걸음 내디딜 때마다 올바르게 추측할 확률이 절반이므로 그렇지 않다고 설명한다. Hlini를 제외한 모든 참가자는 완벽한 기억력을 지니고 있다. 모든 참가자는 완벽한 균형 감각을 지니고 있다.

많은 관중이 현장에 있으며, 각 게임이 끝났을 때 참가자가 몇 명 남을지 추측하는 것이 관중들 사이에서 흔히 즐기는 놀이이다. 게임이 끝났을 때 남아 있을 것으로 기대되는 참가자 수는 얼마인가?

점수

그룹 | 점수 | 제한

1 | 10 | 다리는 단 하나의 줄로 이루어져 있다.

2 | 20 | Hlini만 유일하게 남은 참가자이다.

3 | 30 | $0 \leq n, m \leq 10$

4 | 30 | $0 \leq n, m, \leq 1000$

5 | 10 | 추가 제한이 없다.

입력은 두 정수 $n$와 $m$가 주어지는 한 줄로 이루어진다. 전자는 다리의 줄 수이고 후자는 게임의 참가자 수이며, $0 \leq n \leq 10^6$이고 $0 \leq m \leq 10^6$이다.

게임이 끝났을 때 남아 있을 것으로 기대되는 사람의 수를 나타내는 실수 하나를 한 줄에 출력한다. 출력한 수의 절대 오차 또는 상대 오차가 $10^{-6}$ 이하이면 정답으로 간주한다. 이는 충분히 정확하기만 하다면 소수점 아래 몇 자리까지 출력하는지는 중요하지 않다는 뜻이다.