Evklid TSP
Arora-Mitchell alqoritmi, Evklid səyahətçi satıcı problemi (Evklid TSP) üçün təxminən həll təqdim edən bir yanaşmadır və bu alqoritm 1998-ci ildə Sanjeev Arora və Cozef S. B. Mitchell tərəfindən müstəqil şəkildə kəşf edilmişdir. Alqoritm, TSP-nin optimal yolunu d ölçüsündə 1 + 1 / c zaman əmsalı daxilində təxmin edə bilir.
burada n - yoldakı zirvələrin sayıdır.
Miroslava kompüter təhlükəsizliyi şirkətində çalışır və Avropanın müxtəlif məlumat mərkəzlərində ümumi kriptoqrafik açarı yeniləmək vaxtı gəlib çatıb. Bunun üçün Miroslava özəl təyyarə icarəyə götürməyi və bütün böyük Avropa hava limanlarında onu gözləyən işçilərə açarı təqdim etməyi planlaşdırır. 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ü müstəvi ilə təxmin edə bildiyimiz üçün Arora-Mitchell alqoritminin dəqiq işlədiyini fərz edirik
bu kompüterdə optimal marşrutun dəqiq (1 + 1 / c) - aproksimasiya əldə etmək üçün saniyələr.
Miroslava qeyd etdi ki, c alqoritmin parametri olub, ona faydalı ola bilər, lakin düzgün dəyərini seçərkən çox diqqətli olmaq lazımdır. Əgər o, c dəyərini çox kiçik götürsə, alqoritm çox tez bitəcək və Avropada keçirdiyi vaxt çox olacaq. Digər tərəfdən, çox yüksək dəyər təyin etmək, cavabı kompüterdən gözləməyə məcbur edəcək, halbuki o, bu vaxt uçuş edə bilər.
Miroslava əvvəl başqa bir şirkətdə işləyirdi və oradan bilir ki, bütün böyük Avropa hava limanları üzrə optimal turun uzunluğu s metrdir, lakin o, şirkətdə kifayət qədər yüksək vəzifədə deyildi ki, faktiki turu bilsin. Özəl təyyarənin sürəti v metr/saniyə olduğuna görə, Miroslavaya s * (1 + 1 / c) / v saniyə lazımdır ki, alqoritm ilə yaradılmış turu tamamlasın, c parametri ilə işə salınmış. Sadəlik üçün fərz edirik ki, Miroslava hər hava limanında enib şəxsi açarın bir nüsxəsini buraxıb dərhal uçuş edə bilər.
Miroslavanın əvvəlcə alqoritmi işə salması və sonra bütün açarları paylaması nə qədər vaxt alacaq, fərz edək ki, o, optimal c parametrini seçir?
Giriş məlumatları
Riyad dörd rəqəmi ehtiva edir:
n (4 ≤ n ≤
10^6) - hava limanlarının sayı;həqiqi rəqəm p (0.001 ≤ p ≤ 5000) - kompüterin saniyədə yerinə yetirə biləcəyi milyard əməliyyatların sayı;
həqiqi rəqəm s (
10^6≤ s ≤10^9) - Avropa hava limanları üzrə optimal turun uzunluğu metr ilə;həqiqi rəqəm v (50 ≤ v ≤ 900) - özəl təyyarənin sürəti metr/saniyə ilə.
Bütün həqiqi rəqəmlər 10 onluq rəqəmdən çox deyil.
Çıxış məlumatları
Bir sətirdə açarların paylanması üçün minimal mümkün vaxt t və Miroslavanın t vaxtına çatmaq üçün istifadə etməli olduğu c parametrinin dəyərini çıxarın. Cavabınızın mütləq və ya nisbi xətası 10^(-6)-dan çox olmamalıdır.