Евклідова TSP#7855

Евклідова TSP

1 секунда

128 мегабайтів

Дуже легка

Відомий алгоритм апроксимації Арори-Мітчелла для Евклідової задачі комівояжера (Евклідова TSP) був незалежно відкритий Сандживом Аророю та Джозефом С. Б. Мітчеллом у $1998$ році. Він дозволяє наближено знайти значення оптимального туру TSP у $d$ -вимірному просторі з точністю до коефіцієнта $1 + \frac{1}{c}$ 1 + \frac{1}{c} за час

де $n$ — кількість вузлів (вершин) у маршруті.

Мирослава працює в компанії з комп'ютерної безпеки, й настав час оновити спільний криптографічний ключ у багатьох дата-центрах по всій Європі. Для цього Мирослава планує орендувати приватний літак і доставити ключ співробітникам, які чекають у всіх основних аеропортах Європи. Вона хоче повернутися якнайшвидше.

У компанії Мирослави є комп'ютер, здатний виконувати $p$ мільярдів операцій на секунду. Оскільки Європу можна уявити у вигляді двовимірної площини, будемо вважати, що алгоритм Арори-Мітчелла працює саме

секунд на цьому комп'ютері, щоб отримати $(1 + \frac{1}{c})$ (1 + \frac{1}{c})-апроксимацію оптимального маршруту.

Мирослава помітила, що $c$ — це параметр алгоритму, який можна використати на свою користь, однак треба бути дуже обережною з його вибором. Якщо $c$ буде надто малим, алгоритм завершиться швидко, але сама подорож Європою триватиме занадто довго. Якщо ж вибрати занадто велике $c$ , доведеться довго чекати відповіді від комп'ютера, у той час як можна було б летіти.

Мирослава раніше працювала в іншій компанії і знає, що оптимальний тур усіма великими аеропортами Європи має довжину $s$ метрів, проте сам маршрут їй невідомий. Якщо швидкість літака $v$ метрів на секунду, то для подолання туру, знайденого алгоритмом із параметром $c$ , потрібно $s \cdot (1 + \frac{1}{c}) / v$ s \cdot (1 + \frac{1}{c}) / v секунд. Для простоти припустимо, що Мирослава може приземлятися, залишати копію ключа й одразу злітати з кожного аеропорту миттєво.

Скільки часу потрібно Мирославі на запуск алгоритму і роздачу всіх ключів, якщо вона вибере оптимальний параметр $c$ ?

Вхідні дані

Вхід містить один рядок із чотирма числами:

ціле число $n$ ( $4 \leq n \leq 1 0^{6}$ 4 \le n \le 10^6) — кількість аеропортів;
дійсне число $p$ ( $0.001 \leq p \leq 5000$ 0.001 \le p \le 5000) — кількість мільярдів операцій, які комп'ютер може виконати за секунду;
дійсне число $s$ ( $1 0^{6} \leq s \leq 1 0^{9}$ 10^6 \le s \le 10^9) — довжина оптимального туру по аеропортах у метрах;
дійсне число $v$ ( $50 \leq v \leq 900$ 50 \le v \le 900) — швидкість літака у метрах за секунду.

Всі дійсні числа містять не більше $10$ знаків після десяткової крапки.

Вихідні дані

Виведіть в одному рядку мінімальний можливий час $t$ у секундах для розподілу ключів і значення параметра $c$ , який Мирослава повинна використати для досягнення часу $t$ . Ваша відповідь повинна мати абсолютну або відносну похибку не більше $1 0^{- 6}$ 10^{-6}.

Приклади

Приклад 1

Приклад 2