Evklid TSP

Məşhur Arora-Mitchell yaxınlaşdırma alqoritmi Evklid Səyyah Satıcı Problemi (Evklid TSP) üçün Sanjeev Arora və Joseph S. B. Mitchell tərəfindən 1998-ci ildə müstəqil olaraq kəşf edilmişdir. Bu alqoritm optimal TSP turunun $d$ ölçülü fəzada 1 + \frac{1}{c} yaxınlığı ilə aşağıdakı iş vaxtında hesablana bilər:

burada $n$ — turdakı nöqtələrin (zirvələrin) sayıdır.

Miroslava kompüter təhlükəsizliyi şirkətində çalışır və Avropada bir çox məlumat mərkəzində paylaşılmış kriptoqrafik açarı yeniləməyin vaxtı çatıb. Bu məqsədlə Miroslava özəl təyyarə icarəyə götürüb bütün böyük Avropa hava limanlarında gözləyən əməkdaşlara açarı paylayacaq. O, mümkün qədər tez qayıtmaq istəyir.

Miroslavanın şirkətində saniyədə $p$ milyard əməliyyat yerinə yetirə bilən bir kompüter var. Avropanı ikiölçülü bir müstəvi kimi təsəvvür etsək, Arora-Mitchell alqoritmi bu kompüterdə tam olaraq

saniyə işləyir və optimal turun (1 + \frac{1}{c}) yaxın qiymətləndirilməsini verir.

Miroslava diqqət edib ki, $c$ alqoritmin parametridir və ona kömək edə bilər, lakin düzgün seçimdə ehtiyatlı olmaq lazımdır. Əgər $c$ çox kiçik seçilərsə, alqoritm tez bitəcək, amma tur çox uzun çəkəcək. Əksinə, $c$ çox böyük olarsa, kompüterin cavabını gözləmək vaxt itkisidir.

Miroslava daha əvvəl başqa bir şirkətdə çalışıb və oradan bilir ki, bütün böyük Avropa hava limanlarını əhatə edən ən yaxşı turun uzunluğu $s$ metrdir, amma dəqiq yürüşü bilmir. Təyyarənin sürəti $v$ metr/saniyədirsə, Miroslavaya (s \cdot (1 + \frac{1}{c})) / v saniyə lazımdır ki, seçilmiş $c$ parametri ilə alınan turu başa vursun. Sadəlik üçün fərz edirik ki, Miroslava hər hava limanında enib, açarı qoyub dərhal uçur.

Miroslava əvvəlcə alqoritmi işə salıb sonra açarları paylamaq üçün optimal $c$ parametrini seçsə, ən qısa ümumi müddət nə olar?

Giriş

Girişin bir sətrində dörd ədəd verilir:

• bir tam ədəd $n$ (4 \le n \le 10^6) — hava limanlarının sayı;

• bir həqiqi ədəd $p$ (0.001 \le p \le 5000) — saniyədə kompüterin yerinə yetirə biləcəyi milyard əməliyyatların sayı;

• bir həqiqi ədəd $s$ (10^6 \le s \le 10^9) — optimal turun uzunluğu (metr);

• bir həqiqi ədəd $v$ (50 \le v \le 900) — təyyarənin sürəti (metr/saniyə).

Bütün həqiqi ədədlər ən çox $10$ onluq rəqəmdə veriləcək.

Çıxış

Bir sətirdə açarların paylanması üçün alınan ən qısa mümkün vaxtı $t$ və bu müddət üçün seçiləcək $c$ parametrini çap edin. Cavabınızın mütləq və ya nisbətən səhvi 10^{-6}-dan çox olmamalıdır.