루미 알고리즘

#1501실버Cykeltävlingen

PO 2020 학교 예선코딩출제 Nils Gustafsson스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

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?

Indata

Den första raden innehåller de två heltalen N och L (2 ≤ N ≤ 10, 1 ≤ L ≤ 10^5).

De N följande raderna beskriver personerna i laget, där den i:te raden innehåller heltalen s_i och c_i (1 ≤ s_i, c_i ≤ 100).

Utdata

Programmet ska skriva ut ett decimaltal: 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.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

FallPoängvärdeGränser
120N = 2
220Alla s_i är samma, och alla c_i är samma
360Inga ytterligare begränsningar.

Exempelförklaring

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.

예제

예제 1

입력
3 10
1 3
2 3
3 1
출력
4.66666666666666607

예제 2

입력
4 5000
6 9
5 16
4 7
14 1
출력
839.416058394160473

출처 표기

출처: Programmeringsolympiaden 2020년 학교 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.