루미 알고리즘

#1427골드IOI-uttagning

PO 2017 온라인 예선코딩출제 Johan Sannemo스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

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

Problem

Programmeringsolympiadens arrangörsgrupp vill ut och leka i snön. Tyvärr har man som arrangör otaliga plikter, som kommer före lekandet. Man måste göra uppgifter, övervaka tävlingar, åka som ledare, och beräkna vilka deltagare som är uttagna till landslaget utifrån årets resultat.

Det slog dock arrangörerna att den sista biten kan ju någon annan ordna. T.ex. du.

Reglerna för uttagning till landslaget går till som följer. Totalt finns det fyra tävlingar som ligger till grund för uttagning; finaltävlingen samt tre s.k. KATT-tävlingar (KATT1, KATT2 och KATT3).

Efter alla tävlingar räknas resultaten samman, och de fyra tävlanden med bäst poäng blir uttagna till International Olympiad in Informatics, IOI. Utöver IOI ska även ett lag väljas till Baltic Olympiad in Informatics, BOI. Detta lag består dels av IOI-laget, samt de två bästa tävlanden som inte går i trean och inte kvalificerade sig till IOI.

När resultaten räknas samman väljs de två bästa resultaten från de tre KATT-tävlingarna ut, samt resultatet från finalen, och summeras.

Inom en tävling räknas resultatet ut genom att normalisera poängen en tävlande fick. Först beräknar man den bästa poängen bland alla deltagare MAX, samt medianpoängen bland alla deltagare MED. Om en deltagare fick x ≤ MED poäng blir deltagarens resultat 50 · x/MED. Om en deltagare fick MED ≤ x ≤ MAX poäng blir deltagarnas resultat 50 + 50 · (x - MED)/(MAX - MED). Detta innebär att resultatet ökar linjärt från 0 till 50 när poängen ökar från 0 till MED, och från 50 till 100 när poängen ökar från MED till MAX.

För varje deltagare i tävlingen kommer du får deltagarens resultat i de fyra tävlingarna, samt deltagarens årskurs. Avgör vilka som blir uttagna till IOI och BOI.

Indata

Den första raden innehåller ett heltal 6 ≤ N ≤ 40, antalet deltagare.

De N nästa raderna beskriver en deltagare och dess resultat. En rad börjar med deltagarens namn, som består av upp till 20 små bokstäver från a till z, utan mellanslag. Därefter följer ett tal som är antingen 7, 8, 9, 1, 2, 3 och beskriver deltagarens årskurs. Årskurserna 7, 8, 9 representerar här högstadieelever. Slutligen kommer fyra heltal 0 ≤ F, K1, K2, K3 ≤ 700 - poängen från finalen, KATT1, KATT2 och KATT3 respektive.

I en tävling kommer medianen och maxpoängen alltid vara skiljda från varandra. Det kommer alltid finnas precis ett möjligt lag enligt reglerna ovan.

Utdata

På den första raden ska du skriva ut namnen på de fyra deltagare som blev uttagna till IOI.

Nästa rad ska innehålla två namn - de ytterligare deltagare som kvalificerade sig till BOI.

På varje rad ska namnen du skriver ut vara sorterade i bokstavsordning.

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ärdeBegränsningar
123Medianpoängen i en tävling är alltid 50, och maxpoängen 100.
213Alla elever är förstaårselever
331Resultaten i de tre KATT-tävlingarna var alltid samma.
433Inga begränsningar

예제

예제 1

입력
33
lisavallfors 3 505 362 145 0
adamhasselwander 3 200 0 0 0
martinjakobsson 3 247 101 69 272
arvidlunnemark 1 461 40 160 343
nicolehedblom 2 450 328 0 139
fredrikekholm 8 216 168 229 265
davidwarn 2 653 400 400 387
fredrikhernqvist 3 608 400 400 100
bjornmagnusson 1 320 181 175 227
karllundstig 3 657 306 360 265
johanbostrom 3 0 40 0 178
ivarmatstoms 1 216 0 0 0
simonhalvdansson 3 100 0 0 0
mattiasgrenfeldt 1 445 159 215 35
joakimblikstad 3 644 400 400 331
gustavlindqvist 3 149 0 0 0
erikprantare 2 361 101 0 0
johannesagestam 3 207 61 0 142
carlagrell 2 500 0 130 35
jonatannilsson 2 415 100 75 100
hannesbredberg 3 229 85 0 35
carlenlund 2 116 40 0 0
kristofferahgren 3 450 281 105 235
markoproloscic 2 337 0 0 0
eriksundqvist 3 200 0 0 0
lucasunnerfelt 2 528 0 200 0
johanvikstrom 3 339 128 76 79
victorsellstedt 3 283 0 0 0
bjornthoren 3 345 0 100 0
hermankarlsson 2 557 362 360 303
jacoberiksson 2 236 106 30 135
hugoeberhard 9 386 115 105 276
erikrimskog 3 200 0 0 0
출력
davidwarn fredrikhernqvist joakimblikstad karllundstig
arvidlunnemark hermankarlsson

예제 2

입력
7
annbrittcaroline 3 100 100 100 100
gandalf 1 0 75 75 75
byteasar 3 75 0 75 75
jultomten 2 50 50 50 50
pelle 3 25 25 25 0
alice 8 25 0 25 25
bob 9 0 0 0 0
출력
annbrittcaroline byteasar gandalf jultomten
alice bob

출처 표기

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