엉멈섯싀 저주

시간 제한1초메모리 제한1024 MB

요약
수열에 따라 각 정다각형이 이전 다각형을 포함하는 가장 작은 크기가 되도록 그릴 때 마지막 외접원 반지름의 자연로그를 구한다.
난이도

어려움10점 중 8점

유형
기하, 수학, 배열, 완전 탐색
정답자
아직 제출이 없습니다

문제

엉엉이의 저주, 멈뭄미믜 저주, 섯섯시싀 저주에 차례로 걸렸었던 현철이는 섯섯시싀 저주, 멈뭄미믜 저주, 엉엉이의 저주를 무사히 풀어내 끝난 줄 알고 안심하고 있었다. 그러나 모든 저주의 배후였던 세진이는 이런 현철이의 허를 찔러 새로운 저주인 엉멈섯싀 저주를 내렸다.

세진이는 양의 정수 KK와 길이 NN의 수열 A_1,A_2,⋯ ,A_NA\_1,A\_2,\cdots ,A\_N을 줬다. 모든 A_iA\_i는 11, 33, 44, 혹은 KK의 배수 중 하나이다. 이제 현철이는 NN개의 정다각형 P_1,P_2,⋯ ,P_NP\_1,P\_2,\cdots ,P\_N을 다음 규칙에 따라 차례대로 그린다.

  1. 다각형 P_1P\_1은 외접원의 반지름이 11인 정A_1A\_1각형이다.
  2. i≥2i\ge 2에 대해, 다각형 P_iP\_i는 다각형 P_i−1P\_{i-1}을 변 혹은 내부에 들어가도록 하는 가장 작은 크기의 정A_iA\_i각형이다. 만약, 그런 다각형이 여러 가지라면 아무거나 하나 그린다.
  3. 이때, A_i=1A\_i=1이라면 정11각형 대신 원을 생각한다.

마지막으로 완성된 P_NP\_N의 외접원의 반지름을 구해보자.

입력

첫 번째 줄에 정수 N(1≤N≤105)N(1\le N\le 10^5), K(5≤K≤106)K(5\le K\le 10^6)가 공백으로 구분되어 주어진다.

두 번째 줄에 NN개의 정수 A\_1,A\_2,\cdots ,A\_N(A\_i\in\left( \left\\{ 1,3,4 \right\\}\cup\left\\{ mK\mid m\in\mathbb{Z}\_{\gt 0}\land mK\le 10^{9} \right\\} \right))이 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 정답을 출력한다. 단, 수가 너무 커질 수 있으므로 답에 ln⁡\ln을 취한 값을 출력한다. 즉, P_NP\_N의 외접원의 반지름이 tt라면 ex=te^x=t를 만족하는 xx를 출력한다.

정답과의 절대/상대 오차는 10−910^{-9}까지 허용한다.

예제4

  1. 예제 1

    입력
    1 6
    6
    
    예상 출력
    0
    
  2. 예제 2

    입력
    3 5
    1 4 3
    
    예상 출력
    0.911492789
    
  3. 예제 3

    입력
    8 6
    1 3 12 4 6 30 3 198
    
    예상 출력
    1.801879359
    
  4. 예제 4

    입력
    9 13
    3 4 39 13 1 169 4 2210 65
    
    예상 출력
    0.544430939