Евклідове TSP
Знаменитий алгоритм апроксимації Арори-Мітчелла для евклідової задачі комівояжера (евклідова TSP) був незалежно розроблений Санджевою Аророю та Джозефом С. Б. Мітчеллом у 1998 році. Цей алгоритм може приблизно обчислити значення оптимального шляху TSP у вимірі d з точністю до коефіцієнта 1 + 1 / c.
де n - кількість вершин у шляху.
Мирослава працює в компанії комп'ютерної безпеки, і настав час оновити загальний криптографічний ключ у багатьох центрах обробки даних по всій Європі. Для цього вона планує орендувати приватний літак і доставити ключ співробітникам, які чекають на нього в усіх великих європейських аеропортах. Вона хоче повернутися якомога швидше.
У компанії Мирослави є комп'ютер, здатний виконувати p мільярдів операцій на секунду. Оскільки ми можемо апроксимувати Європу двовимірною площиною, припустимо, що алгоритм Арори-Мітчелла працює точно
секунд на цьому комп'ютері для отримання точної (1 + 1 / c) - апроксимації оптимального маршруту.
Мирослава помітила, що c є параметром алгоритму, який може бути їй корисним, однак слід бути дуже обережною при виборі правильного його значення. Якщо вона візьме занадто мале значення c, то алгоритм завершиться дуже швидко, але час, який вона проведе в Європі, буде занадто великим. З іншого боку, встановлення занадто високого значення змусить її чекати відповіді від комп'ютера, в той час як вона може літати в цей час.
Мирослава раніше працювала в іншій компанії, і звідти вона знає, що довжина оптимального туру по всіх великих європейських аеропортах займає s метрів, однак вона не мала достатньо високого положення в компанії, щоб знати фактичний тур. З огляду на швидкість v приватного літака в метрах на секунду, Мирославі потрібно s * (1 + 1 / c ) / v секунд для завершення туру, створеного алгоритмом, запущеним з параметром c. Для простоти ми припускаємо, що Мирослава може приземлитися, залишити копію особистого ключа і вилетіти з кожного аеропорту в одну мить.
Скільки часу займе у Мирослави, щоб спочатку запустити алгоритм, а потім розподілити всі ключі, припускаючи, що вона вибирає оптимальний параметр c?
Вхідні дані
Рядок містить чотири числа:
число n (4 ≤ n ≤
10^6) - кількість аеропортів;дійсне число p (0.001 ≤ p ≤ 5000) - кількість мільярдів операцій, яке може виконувати комп'ютер на секунду;
дійсне число s (
10^6≤ s ≤10^9) - довжина оптимального туру по європейських аеропортах в метрах;дійсне число v (50 ≤ v ≤ 900) - швидкість приватного літака в метрах на секунду.
Усі дійсні числа містять не більше 10 десяткових цифр.
Вихідні дані
Виведіть в одному рядку мінімально можливий час t в секундах для розподілу ключів і значення параметра c, яке Мирослава повинна використовувати для досягнення часу t. Ваша відповідь повинна мати абсолютну або відносну помилку не більше 10^(-6).