시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1.75 초 (추가 시간 없음) 1024 MB 89 50 32 60.377%

문제

홍익대학교 바로 뒤편에 위치한 와우산의 와우약수터는 아직도 폐쇄되어있다. 와우산의 정기가 그대로 흘러나오는 약수를 다시 회복하기 위한 "와우 프로젝트"의 일원으로 파견된 당신은, 와우산의 산신령을 소환하기 위한 "약수 의식"을 준비했다. 약수 의식은 다음과 같은 순서로 이루어진다.

  1. $1$~$9$의 숫자가 적혀있는 $N$장의 카드를 준비하고, 모든 카드를 잘 섞어 뒤집어 놓는다.
  2. 뒤집히지 않은 카드 중, 하나의 카드를 무작위로 골라 뒤집는다. 이것을 뒤집힌 카드가 딱 한 장 남을 때까지 반복한다.
  3. 지금까지 뒤집은 카드의 숫자들을 뒤집은 순서대로 읽었을 때 나오는 정수를 $x$라고 하자. 예를 들어 $1, 2, 3$을 순서대로 뽑았다면, $x = 123$이 된다.
  4. 마지막으로 뒤집혀있는 한 장의 카드를 마저 뒤집는다. 이 카드에 적혀있는 수가 $x$의 약수여야, 이 의식은 성공이다.

과연 약수 의식이 성공할 확률은 얼마나 될까?

입력

첫째 줄에 카드의 개수 $N$ ($2 \le N \le 16$)이 주어진다.  

다음 줄에 각 카드에 적혀있는 숫자 $a_1, a_2, \dots, a_N$ ($1 \le a_i \le 9$)이 주어진다.

출력

약수 의식이 성공할 확률을 출력한다. 절대 오차 또는 상대 오차가 $10^{-6}$ 이하면 정답으로 간주한다.

예제 입력 1

3
1 2 3

예제 출력 1

0.6666666667

총 $6$가지의 경우의 수가 존재하며, 카드를 뽑는 순서에 따라 의식의 성공 여부는 다음과 같다.

  • $1, 2$, 남은 카드 $3$ : $3$은 $X=12$의 약수이다.
  • $2, 1$, 남은 카드 $3$ : $3$은 $X=21$의 약수이다.
  • $1, 3$, 남은 카드 $2$ : $2$는 $X=13$의 약수가 아니다.
  • $3, 1$, 남은 카드 $2$ : $2$는 $X=31$의 약수가 아니다.
  • $2, 3$, 남은 카드 $1$ : $1$은 $X=23$의 약수이다.
  • $3, 2$, 남은 카드 $1$ : $1$은 $X=32$의 약수이다.

예제 입력 2

9
1 2 3 4 5 6 7 8 9

예제 출력 2

0.4667107584

출처

Camp > ICPC Sinchon Algorithm Camp > 2021 ICPC Sinchon Winter Algorithm Camp Contest - 중급 F번