매장에 새로운 큐브가 나왔다.

이 큐브는 N각뿔의 형태로 생겼다. 각뿔의 꼭짓점을 P, 밑면의 꼭짓점들을 A1, A2, A3, ... AN 이라고 하자.

점 P에서 쥐가 움직이기 시작하는데, 쥐는 모서리를 따라서만 움직이고 다른 꼭짓점을 만나면 아무 곳으로나 간다. (예를 들어, A1에서 P에 도착하면 A1, A2, A3, ... AN중 아무 곳으로나 가고 각각의 확률은 1/N 이다.)

우리의 목표는 쥐가 K번 움직였을 때 점 P에 있을 확률을 구하는 것이다.

입력

출력

입출력 예

입력

5 2

출력

0.333333

입출력 보충

5 2 인 경우

P A1 P
P A1 A2
P A1 A5
P A2 P
P A2 A1
P A2 A3
P A3 P
P A3 A2
P A3 A4
P A4 P
P A4 A3
P A4 A5
P A5 P
P A5 A1
P A5 A4

총 15가지가 있고,

P A1 P
P A2 P
P A3 P
P A4 P
P A5 P

이 중 5가지이므로

5/15 = 약 0.333333 이다.

출처:에이급 수학
추천:cube