유클리드 TSP

유클리드 순회 외판원 문제(Euclidean TSP)를 푸는 Arora-Mitchell 근사 알고리즘은 1998년에 Sanjeev Arora와 Joseph S. B. Mitchell이 각각 독립적으로 발견했다. 이 알고리즘은 $d$차원에서 최적 순회 경로의 길이를 $1 + 1/c$배 이내로 근사하고, 실행 시간은

$n\left(\log n\right)^{O\left(\left(c\sqrt{d}\right)^{d-1}\right)}$

이다. 여기서 $n$은 순회 경로에 있는 노드의 수다.

미로슬라바는 컴퓨터 보안 회사에서 일하는데, 유럽 곳곳에 있는 데이터 센터의 공유 암호 키를 갱신할 때가 됐다. 미로슬라바는 전용기를 빌려 유럽의 모든 주요 공항에서 기다리는 직원에게 키를 전달하려 한다. 물론 최대한 빨리 돌아오고 싶다.

회사에는 1초에 $p \cdot 10^{9}$번의 연산을 수행하는 컴퓨터가 있다. 유럽을 2차원 평면으로 근사하면 이 컴퓨터에서 알고리즘은 정확히

$\frac{n\left(\log_{2} n\right)^{c\sqrt{2}}}{p \cdot 10^{9}}$

초 동안 돌고, 최적 순회 경로의 $(1 + 1/c)$ 근사를 내놓는다.

$c$는 미로슬라바가 직접 정하는 매개변수인데, 양쪽 극단이 모두 손해다. $c$를 너무 작게 잡으면 알고리즘은 금방 끝나지만 날아다녀야 하는 경로가 길어진다. 너무 크게 잡으면 경로는 짧아지지만 컴퓨터 앞에서 기다리는 시간이 길어진다.

미로슬라바는 예전 회사에서 유럽 주요 공항 전체의 최적 순회 경로가 $s$미터라는 사실을 알아냈다. 다만 직급이 낮아서 실제 경로가 무엇인지는 모른다. 전용기의 속도가 초속 $v$미터이므로, 매개변수 $c$로 얻은 경로를 도는 데는 $s(1 + 1/c)/v$초가 걸린다. 착륙해서 키 사본을 남기고 다시 이륙하는 시간은 0으로 본다.

미로슬라바가 최적의 매개변수 $c$를 골랐을 때, 알고리즘을 실행하고 키를 모두 전달하는 데 걸리는 시간을 구하시오.

첫째 줄에 네 수가 주어진다.

• 정수 $n$ ($4 \le n \le 10^{6}$): 공항의 수
• 실수 $p$ ($0.001 \le p \le 5000$): 컴퓨터가 1초에 수행하는 연산 횟수를 십억으로 나눈 값
• 실수 $s$ ($10^{6} \le s \le 10^{9}$): 유럽 공항 전체를 도는 최적 순회 경로의 길이(미터)
• 실수 $v$ ($50 \le v \le 900$): 전용기의 속도(초속 미터)

모든 실수는 소수점 아래 자릿수가 10자리 이하다.

키를 모두 전달하는 데 걸리는 가장 짧은 시간 $t$(초)와 그 시간을 만드는 매개변수 $c$를 공백 하나로 구분해 한 줄에 출력한다. 두 값 모두 소수점 아래 여섯째 자리까지 반올림해 출력한다.

총 시간은 $c > 0$에서 아래로 볼록하므로 최솟값과 그 최솟값을 만드는 매개변수는 유일하다.