Informatica Online Judge

  합리적인 조세푸스 문제 [1320 / 0528]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 5   Total Tried : 10


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[koistudy.net (32nd 김지성)]

Background

조세푸스 문제는 매우 유명한 문제이다. 이 문제는 다음과 같다.

n명의 사람들이 원형으로 둘러앉아 있다. 1번부터 시작하여 두명씩 짝을 지어 두번째 사람이 나간다. 마지막 한 사람이 남을 때까지 이 과정을 반복한다.

n=5 일때의 예시를 들어보면 다음과 같다.

1,2번 사람 중 2번 사람이 나간다.

3,4번 사람 중 4번 사람이 나간다. 여기까지 남은 사람은 1,3,5번이다.

원형 구조이므로 5,1번 사람 중 1번 사람이 나간다.

3,5번 사람 중 5번 사람이 나간다. 마지막에 남는 사람은 3번이다.

이 문제의 풀이는 매우 다양하며 매우 잘 알려져 있다.

그런데 이 문제는 무조건 두 사람 중 앞사람을 죽인다는 근본적인 문제점이 있다!

개인의 능력이 중요시되는 현대 사회에는 이러한 불합리한 조건은 용납되지 않는다. 정보난민 지성이는 개인의 능력을 고려하여 새로운 조세푸스 문제를 제안하였다.

새로운 문제에는 다음과 같은 규칙이 추가되었다.


1. 항상 초기 인원 n은 홀수로 시작한다.

2. 매번 시행하는 작업은 다음과 같다.

2 - 1. 매번 두명 중 한명을 내보내는 것이 아니라 세명 중 두명을 내보낸다.

2 - 2. 매번 세 명중 한 명은 자동 탈락한다. 각 사람이 탈락할 확률은 1/3으로 동일한다.

2 - 3. 남은 둘은 경기를 하여 우승자가 남고 패배자는 내보낸다.

3. 모든 사람은 개인의 능력을 나타내는 양의 정수 ai(편의상 레이팅이라고 하자) 를 가진다.

4. 레이팅 x인 사람과 y인 사람이 경기를 할 때, x인 사람이 이길 확률은 x/(x+y), y인 사람이 이길 확률은 y/(x+y) 이다.

이 때 각 사람이 마지막까지 남을 확률을 지성이는 알고 싶어 정보킹인 당신에게 부탁했다. 지성이를 도와주고 점수를 획득하자.

Input

첫 줄에 사람의 수 n이 주어진다. (n은 1000 미만의 홀수임이 보장된다.)

둘째 줄에는 각 사람의 레이팅이 순서대로 주어진다. (레이팅은 항상 500이하의 양의 정수암아 보장된다.)

Output

출력은 총 n줄을 하면 된다.

i번째 줄에 i번째 사람이 마지막까지 살아남을 확률을 소숫점 다섯째 자리까지 반올림하여 출력한다.

연산 과정에서 double형을 사용하는 것을 권장한다.

IO Example

입력
5
1 1 1 1 1

출력
0.11111
0.11111
0.11111
0.33333
0.33333

입력2
3
1 2 4

출력2
0.17778
0.33333
0.48889

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]