루미 알고리즘

#1324다이아Orkesteroptimering

PO 2013 훈련 캠프코딩스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

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

Problem

Problemlösar-orkestern är en samling programmerarmusiker i full gång med att planera sin kommande turné. Den viktigaste uppgiften är att maximera oväsendet de kan åstadkomma i varje låt, detta för att uppnå optimal publikuppskattning.

Orkestern består av N musiker och har bett dig att optimera en låt som består av M takter. Varje musiker har endast övat på de takter han/hon funnit intressanta och är inte kapabel att spela resten av takterna. Varje gång som en musiker spelar en takt så görs detta med oväsendet V=1/(X+1) oväsen-enheter, där X är antalet takter som musikern spelat tidigare i låten. En musiker spelar alltså svagare och svagare ju fler takter han/hon spelar, vilket självklart beror på den ansträngning det tar att lyfta sitt instrument.

Oväsendet i en takt räknas ut genom att ta det maximala V för de musiker som spelar då (endast den som spelar starkast hörs), eller 0 om ingen spelar i takten. För att räkna ut det totala oväsendet i låten så adderar man sedan helt enkelt ihop oväsendet för alla takter. Din uppgift är att räkna ut hur mycket oväsen som kan åstadkommas i låten, givet att orkestern spelar optimalt.

Notera att alla musiker spelar lika bra, det enda som har betydelse för mängden oväsen en musiker kan åstadkomma är antalet takter han/hon har spelat tidigare.

Indata

Den första raden består av två heltal, N och M (1 ≤ N ≤ 1000, 20 < M ≤ 1000).

Därefter följer N, var och en beskrivande en musiker. Dessa rader börjar med ett heltal T_i, antal takter som musiker i övat in, och följs av T_i stycken heltal som beskriver vilka takter musikern övat på. Varje takt representeras med ett tal mellan 1 och M. Det är även garanterat att summan av alla T_i är mindre än 20000.

Utdata

Skriv ut ett flyttal, det maximala oväsendet som kan åstadkommas i låten. Ett absolut fel mindre än 10^-5 betraktas som korrekt.

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ängGränser
120N, M ≤ 20
280Inga ytterligare begränsningar.

Förklaring av exempelfall 1

Anta att vi har två personer och fem takter. Person 1 kan spela alla takter, och person 2 kan bara spela de två första (se exempelindata 1). Då låter vi den andra personen spela de två takter den behärskar, och den andra personen får spela resten. Summan av alla oväsenden blir då (i taktordning) 1 + 1/2 + 1 + 1/2 + 1/3 = 10/3.

예제

예제 1

입력
2 5
5 1 2 3 4 5
2 1 2
출력
3.333333333333333

예제 2

입력
3 3
2 1 3
2 1 2
2 1 2
출력
3.000000000000000

출처 표기

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