Deceptive Dice

최근 마을에 사기꾼들이 들끓어서, 사정을 모르는 관광객들을 꼬드겨 간단한 주사위 게임을 돈을 걸고 하게 만들고 있다. 게임은 이렇다. 눈에 1, 2, . . . , n개의 점이 찍힌 n면체 주사위와 양의 정수 k가 주어진다. 주사위를 굴린 뒤 선택을 해야 한다. 첫 번째 선택은 그만 굴리는 것이다. 두 번째 선택은 주사위를 다시 굴리는 것이며, 주사위는 모두 k번까지만 굴릴 수 있다는 제약이 있다. 점수는 마지막으로 굴렸을 때 나온 점의 개수다.

사기꾼들이 이 게임에서 관광객보다 잘하는 것은 당연하다. 확률적 재앙에 반대하는 운동의 자랑스러운 지지자인 당신은, 사기꾼을 금지하는 대신 관광객에게 정보를 제공해서 이 문제에 맞서기로 한다.

여러 n과 k 값에 대해 관광객이 얻을 수 있는 최대 기댓값을 찾아볼 수 있는 팸플릿을 만든다. 관광객이 사기꾼보다 준비가 잘 되어 있다면 사기꾼들도 곧 사기를 그만둘 것이다!

전단의 배치는 끝났고 유통 경로도 마련해 두었다. 이제 남은 일은 전단에 적을 숫자를 계산하는 것뿐이다.

주사위의 면 수와 굴릴 수 있는 횟수가 주어졌을 때, 게임을 최적으로 플레이했을 때의 기댓값(즉, 평균 점수)을 계산하라.

• 한 줄에 두 정수 1 ≤ n ≤ 100, 주사위의 면 수, 그리고 1 ≤ k ≤ 100, 주사위를 굴릴 수 있는 횟수가 주어진다.

최적으로 플레이했을 때의 기댓값을 출력한다. 답의 절대 오차 또는 상대 오차는 10−7 이하여야 한다.