동전 전달 게임
시간 제한2초메모리 제한128 MB
원형으로 앉은 N명의 학생 중 K번 학생부터 시작해 좌우로 편향된 확률로 코인이 전달될 때, N번 학생이 코인을 처음 받는 순서가 가장 마지막이 될 확률을 구합니다.
문제
N명의 학생이 원탁에 1번부터 N번까지 순서대로 앉아 있다. i번 학생의 오른쪽에는 i+1번 학생이 있고, N번 학생의 오른쪽에는 1번 학생이 있다.
처음에는 K번 학생이 동전을 받는다. 어떤 학생이 동전을 받으면, 그 학생은 정해진 확률에 따라 바로 오른쪽 학생 또는 바로 왼쪽 학생에게 동전을 넘긴다. 각 학생이 오른쪽 학생에게 동전을 넘길 확률은 서로 다를 수 있다.
모든 학생이 적어도 한 번 동전을 받은 순간 게임이 끝난다. 이때 마지막으로 처음 동전을 받은 학생이 승자가 된다.
1번부터 N-1번 학생까지의 오른쪽 전달 확률이 주어질 때, N번 학생이 승자가 될 확률을 구하라. N번 학생의 전달 확률은 필요하지 않다. N번 학생이 모든 다른 학생보다 먼저 동전을 받으면 N번 학생은 승자가 될 수 없고, 모든 다른 학생이 먼저 동전을 받은 뒤 N번 학생이 동전을 받으면 그 순간 게임이 끝나기 때문이다.
입력
첫째 줄에 학생 수 N과 처음 동전을 받는 학생 번호 K가 주어진다.
- 1 <= N <= 50
- 1 <= K <= N
둘째 줄에는 1번 학생부터 N-1번 학생까지, 각 학생이 오른쪽 학생에게 동전을 넘길 확률이 순서대로 주어진다. 확률이 P라면 왼쪽 학생에게 넘길 확률은 1-P이다.
각 확률은 최대 소수점 둘째 자리까지 주어지며, 0 또는 1은 주어지지 않는다.
출력
N번 학생이 승자가 될 확률을 출력한다.
정답과의 절대 오차 또는 상대 오차가 10^-6 이하이면 정답으로 인정된다.