Oyun relikviyaları
Kibersport, video oyunları vasitəsilə keçirilən rəqabətli idman növüdür. Dota 2, kibersportda ən məşhur rəqabətli video oyunlardan biridir. Yaxınlarda isə yeni bir video oyun olan Dota 3 çıxıb. Dota 3-də oyunçular öz qəhrəmanları üçün relikviyalar ala bilərlər. Relikviyalar, oyunda qəhrəmanın hərəkətlərini və statistikasını izləyən sayğaclardır.
Gloriya Dota 3 oynamağı sevir və sevimli qəhrəmanı üçün mövcud olan bütün n relikviyanı almaq istəyir.
Relikviyalar oyun içi valyuta olan parçalarla alınır. Hər bir relikviyanın öz qiyməti var - i-ci relikviya üçün c[i] parça. Oyunçu relikviyanı aşağıdakı üsullardan biri ilə ala bilər:
i-ci relikviyanı almaq üçün
c[i]parça ödəmək;x parça ödəyərək mövcud n relikviyadan birini təsadüfi olaraq əldə etmək. Relikviyanı əldə etmə ehtimalı bütün n relikviyalar üçün eynidir. Əgər təkrarlanan relikviya əldə edilərsə, relikviya təkrar emal edilir və oyunçuya x / 2 parça geri qaytarılır.
Gloriya bütün n relikviyanı almaq istəyir. Ona bütün relikviyaları almaq üçün gözlənilən minimum parça sayını azaltmağa kömək edin.
Giriş Məlumatları
Birinci sətir iki tam ədəd n və x (1 ≤ n ≤ 100, 1 ≤ x ≤ 10000) - relikviyaların sayı və təsadüfi relikviya əldə etmənin qiymətini ehtiva edir.
İkinci sətir n tam ədəd c[1], c[2], ..., c[n] (x ≤ c[i] ≤ 10000, Σ c[i] ≤ 10000) - n relikviyanın qiymətlərini ehtiva edir.
Çıxış Məlumatları
Bir real ədəd çıxarın - Gloriyanın bütün relikviyaları almaq üçün xərcləməli olduğu gözlənilən minimum parça sayı. Absolyut və ya nisbi səhv 10^(-9)-dan çox olmamalıdır.
İzah
Birinci nümunədə optimal strategiya 20 parça ödəyərək iki relikviyadan birini təsadüfi olaraq əldə etməkdir. Sonra iki ssenari mövcuddur.
Birinci ssenari Gloriya birinci relikviyanı əldə edərsə baş verəcək. Sonra o, ikinci relikviyanı əldə edənə qədər təsadüfi relikviyalar əldə etməyə davam edəcək. Bu ssenaridə xərclənməli olan gözlənilən parça sayı 20 + 30 = 50 olacaq.
İkinci ssenaridə Gloriya əvvəlcə ikinci relikviyanı əldə edir. Sonra birinci relikviyanı 25 parça ödəyərək almaq daha yaxşıdır, buna görə də bu ssenaridə xərclənməli olan gözlənilən parça sayı 20 + 25 = 45 olacaq. Beləliklə, xərclənməli olan gözlənilən parça sayı (50 + 45) / 2 = 47.5 olacaq.