루미 알고리즘

#1328골드Lagtävling

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

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

Problem

Vissa anser att PO borde ha en lagtävling där den bästa skolan utses baserat på de individuella resultaten. Då uppkommer naturligtvis frågan hur denna vinnande skola ska utses. Om vi har N deltagare i PO och vi antar att uppgifterna är så utslagsgivande att inga deltagare får samma resultat, så kan resultatet beskrivas som en sträng med N bokstäver, där varje bokstav representerar en skola och är ordnade så att den första bokstaven anger vinnarens skola, nästa bokstav anger den andraplacerades skola o.s.v. (vi antar i denna uppgift att högst 26 skolor deltar, så bokstäverna A-Z räcker).

Ett möjligt sätt att utse vinnande skola vore då att lägga ihop placeringssiffrorna för de K bästa eleverna från varje skola och välja den med minst placeringssiffra (skolor med mindre än K elever räknas givetvis inte). Problemet med detta system illustreras bäst med ett exempel: Antag att resultatet är AABCBBCCDDDA och att K=3. Då vinner B med placeringssumman 3+5+6=14 medan A får 1+2+12=15. Men om vi istället jämför A direkt med varje annat lag, utan att ta med deltagarna från övriga lag när vi beräknar placeringssiffrorna. Då vinner A varje sådan duell med 1+2+6=9 mot 3+4+5=12. Observera att alla A:s deltagare kan påverka placeringarna för lag B, inte bara de K första.

Ett lag som vinner alla sådana hypotetiska dueller mot övriga lag brukar kallas för en Condorcet-vinnare, och det faktum att vår första metod inte alltid utser Condorcet-vinnaren, även om en sådan finns, kan beskrivas som att metoden inte uppfyller Condorcet-kriteriet. Föga förvånande används dessa termer oftare om politiska valsystem än programmeringstävlingsresultat.

Skriv ett program som, givet en resultatlista och talet K, avgör om det finns en Condorcet-vinnare bland skolorna.

Indata

Först en rad med två heltal N och K, det totala antalet deltagare och antalet som ska räknas med för varje skola (1 ≤ N ≤ 1000 och 1 ≤ K ≤ 100). Därefter en rad med N bokstäver, valda bland A–Z. Observera att en skola med mindre än K deltagare automatiskt förlorar sina dueller.

Utdata

Programmet ska skriva ut en rad med bokstaven representerande den skola som är Condorcet-vinnare, eller strängen “Ingen” om det inte finns någon Condorcet-vinnare.

예제

예제 1

입력
12 3
FKGHGFHHGFFG
출력
G

예제 2

입력
15 2
PAUHABPUOEXVBOH
출력
Ingen

출처 표기

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