루미 알고리즘

#1440골드Rulltrappa

PO 2018 결선코딩출제 Paulina Hensman, Johan Sannemo스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

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

Problem

Paulina Osqulda (Osqulda är en studentikos benämning på teknologer som studerar vid Kungliga Tekniska högskolan i Stockholm, se https://sv.wikipedia.org/wiki/Osquar_och_Osqulda.) pluggar på KTH i Stockholm, och åker varje morgon till skolan via tunnelbanan. När hon kommer fram till sin tunnelbanestation måste hon åka upp längs en rulltrappa för att komma ut.

I rulltrappan bildas det ofta två olika köer. På den högra sidan av trappan ställer sig folk som vill stå still i rulltrappan, medan man ställer sig på den vänstra sidan om man föredrar att gå i rulltrappan (för att komma upp snabbare).

Paulina har märkt att det oftast bildas en jättelång kö till den vänstra sidan av rulltrappan, eftersom alla är så stressade till jobbet och vill kunna gå snabbt upp för rulltrappan. På sista tiden har hon funderat på om det kanske rentav skulle gå snabbare att istället välja den högra kön, eftersom kön där ofta är kortare.

Rulltrappan är totalt M trappsteg lång. Om man står i rulltrappan färdas man S trappsteg per sekund uppåt i rulltrappan. Om man istället går i rulltrappan färdas man G trappsteg per sekund uppåt.

Totalt kan A personer per sekund börja gå i rulltrappan ur den vänstra kön, medan B personer per sekund kan ställa sig på rulltrappan ur den högra kön. Detta betyder att i början av förloppet går en person på rulltrappan. Innan en ny person går på rulltrappan måste denna vänta 1/A (respektive 1/B sekunder) för att kunna gå på rulltrappan.

Den vänstra kön är för närvarande L personer lång, och den högra är R personer lång.

Hjälp Paulina avgöra vilken kö hon ska ställa sig i, för att så snabbt som möjligt nå rulltrappans topp.

Indata

Den första raden innehåller tre heltal M, S, G (30 ≤ M ≤ 200, 1 ≤ S ≤ G ≤ M), antalet steg i rulltrapporna och antalet steg per sekund man färdas om man står still, respektive går i rulltrappan.

Nästa rad innehåller två decimaltal A och B (0.1 ≤ A, B ≤ 1), antalet personer per sekund som går på den vänstra respektive högra rulltrappan.

Den sista raden innehåller två heltal L och R (0 ≤ L, R ≤ 100), antalet personer i den vänstra respektiva högra rulltrappan just nu.

Utdata

Skriv ut latmask om det snabbaste alternativet är att välja den högra kön och stå i rulltrappan, eller friskus om det snabbaste alternativet är att välja den vänstra kön och gå i rulltrappan.

Det är garanterat att tiden det tar för Paulina att åka upp för rulltrappan skiljer sig med minst 1 sekund mellan de två köerna, så du behöver aldrig bry dig om fallet när båda alternativen är lika snabba.

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.

GruppPoängvärdeGränser
140L = R = 0
240S = G
320Inga ytterligare begränsningar.

Förklaring av exempel 1

I exempel 1 är båda köer tomma, så Paulina kan omedelbart börja gå upp längs rulltrappan. Om hon står stilla i rulltrappan färdas hon med 1 trappsteg per sekund, så det tar 50/1 = 50 sekunder. Om hon istället går upp i rulltrappan färdas hon med 2 trappsteg per sekund, så det tar 50/2 = 25 sekunder, vilket är det snabbare alternativet.

Förklaring av exempel 2

I exempel 2 går det inte snabbare för Paulina att gå upp för rulltrappan än om hon står stilla (ty hon har stukat foten). Däremot har båda sidorna en kö.

I den högra sidan av kön står det 3 personer, och det tar 3/0.5 = 6 sekunder innan dessa personer har gått på rulltrappan. I den vänstra sidan står det istället 4 personer, och det tar 7/1 = 7 sekunder innan dessa personer har gått på rulltrappan.

Således är det snabbare alternativet att välja den högra kön och stå stilla i rulltrappan.

Förklaring av exempel 3

Om Paulina väljer den vänstra kön och går upp för rulltrappan kommer hon upp efter 129 sekunder. Om hon istället väljer att ta den högra kön och därmed stå i rulltrappan tar det 130 sekunder.

예제

예제 1

입력
50 1 2
1 1
0 0
출력
friskus

예제 2

입력
50 1 1
1 0.5
7 3
출력
latmask

예제 3

입력
100 2 4
0.5 0.3
52 24
출력
friskus

출처 표기

출처: Programmeringsolympiaden 2018년 결선 · 원문 페이지 · 이용 조건 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). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.