시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB1731899.783%

문제

N명의 학생이 원탁에 둘러앉아 게임을 하려한다. N명의 학생 중 한 사람이 동전을 받으면서 이 게임은 시작된다. 어떤 사람이 동전을 받았을 때 지정된 특정한 확률로 바로 왼쪽 옆 사람에게 주거나 아니면 오른쪽 옆 사람에게 줄 수 있다. 마찬가지로 동전을 받은 사람 역시 옆사람에게 전달을 하는 식으로 게임은 진행된다. 여기서 왼쪽 혹은 오른쪽 사람에게 줄 확률은 개개인마다 서로 다르다. 이런 식으로 모든 사람이 동전을 적어도 한 번 이상 받은 적이 있으면 게임은 끝나게 되고 마지막으로 동전을 받은 사람이 이 게임의 승자가 된다. 

문제는 N명의 학생이 위 그림과 같은 순서로 둘러앉았을 때, (i번 학생의 오른쪽에 i+1번 학생이 앉고 단, N번 학생 오른쪽은 1번 학생이 앉는 방식) N번 학생이 이 게임의 승자가 될 확률을 구하는 것이다.

입력

첫 줄에는 총 학생의 수 N(1 ≤ N ≤ 50)과 처음 동전을 가지고 있는 사람의 번호 K(1 ≤ K ≤ N)가 주어진다. 두 번째 줄에는 N-1개의 실수가 입력되는데 이는 1번부터 N-1번 학생까지 차례대로 각각의 학생이 오른쪽 학생에게 동전을 줄 확률을 의미한다. (오른쪽 학생에게 동전을 줄 확률이 P라면 왼쪽 학생에게 줄 확률을 1-P가 된다.) 입력되는 확률 값은 최대 소수점 두 자리까지이며 0이나 1인 경우는 없다.

출력

첫 줄에 N번 학생이 승자가 될 확률을 출력한다. 절대/상대 오차는 10-6까지 허용한다.

예제 입력 1

3 1
0.3 0.6

예제 출력 1

0.3000000000

출처

ICPC > Regionals > Northern Eurasia > Northern Eurasia Finals > NEERC 2007 G번

  • 문제를 번역한 사람: author6
  • 빠진 조건을 찾은 사람: dotorya