시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 1 | 1 | 1 | 100.000% |
Du och dina kompisar har bildat ett lag som ska delta i en löpartävling. Tävlingen har lite speciella regler. Man får nämligen använda en cykel, men bara en per lag. Medlemmarna i laget kan alltså turas om att använda cykeln, och kan när som helst hoppa av den så att de som kommer bakom kan använda den istället. Det är inte tillåtet för cykeln att färdas bakåt.
Tiden för ett lag räknas när den sista medlemmen går i mål. I ert lag är ni $N$ personer. Person nummer $i$ springer med en konstant hastighet $s_i$ meter/sekund, och cyklar med en konstant hastighet $c_i$ meter/sekund. Loppet är $L$ meter långt. Hur snabbt kan ni ta er i mål, om ni använder cykeln optimalt?
På första raden står de två heltalen $N$ och $L$ ($2 \leq N \leq 10$, $1 \leq L \leq 10^5$). På de $N$ följande raderna står två heltal vardera: $s_i$ och $c_i$ ($1 \leq s_i, c_i \leq 100$).
Programmet ska skriva ut ett flyttal: den minimala tiden som laget kan ta sig i mål (i sekunder). Svaret anses korrekt om det skiljer sig från det rätta svaret med högst $10^{-2}$.
3 10 1 3 2 3 3 1
4.666666667
4 5000 6 9 5 16 4 7 14 1
839.416058394
I det första exemplet är en lösning att låta den första personen cykla de första $8$ meterna, och sen springa resten. Person nummer $2$ kan då springa de första $8$ meterna och sen cykla sista biten. Person nummer $3$ springer hela vägen. Notera att person nummer $3$ har högre springhastighet än cykelhastighet.
I det andra exemplet består laget av en elitlöpare, en elitcyklist, en PO-arrangör, och en struts. Lösningen bygger på att låta PO-arrangören cykla en stor del av tiden.
Olympiad > Swedish Olympiad in Informatics > 2020 > Qualification 6번