루미 알고리즘

#1472플래티넘Brevoptimering

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

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

Problem

Progolympkommittén, bestående av N personer, ska skicka ut kuvert med affischer för kvalet till alla skolor. För att göra processen snabbare har de delat upp uppgifterna som behöver göras. Uppgifterna är bland annat att skriva adresser, sätta på frimärken, lägga i affischerna och stänga kuverten. När en person är klar med ett kuvert skickas det vidare till någon annan person. Det går inte lika snabbt som de hade hoppats på, och därför undrar de vilka som skulle kunna jobba snabbare.

Varje person p har en egen maximal produktionshastighet M_p kuvert per sekund. Om vi låter I_p vara antalet kuvert som skickas till person p per sekund och låter U_p vara antalet kuvert den blir klar med per sekund så är U_p = min(I_p, M_p). En person blir alltså inte klar med fler än M_p brev per sekund, även om hen får fler att arbeta med. Varje person har dessutom att antal personer den skickar de kuvert hen blir klar med. Den behöver inte skicka lika mycket kuvert till varje person, utan varje person får en viss procent av kuverten p skickar. De personer som ingen skickar kuvert till och som därmed är i början av produktionslinjen har I_p = ∞, och därmed U_p = M_p (de har en oändlig hög med kuvert att ta av). Vissa personer skickar inte vidare några kuvert alls, utan lägger dem bara i hög bredvid sig när de är klara.

För vilka personer gäller att U_p = M_p, det vill säga att de jobbar på sin maximala produktionshastighet?

Indata

Den första raden innehåller ett heltal N (1 ≤ N ≤ 10^5), antalet personer. De nästa N raderna beskriver personerna. Rad i innehåller först heltalet M_i, den maximala produktionshastigheten för person i (1 ≤ M_i ≤ 10^5). Därefter kommer ett heltal k, och sedan k par av heltal j w, som betyder att person i skickar w procent av sina kuvert till person j (1 ≤ w ≤ 100, 1 ≤ j ≤ N, i ≠ j). Inget j kan förekomma mer än en gång på en given rad, och summan av w:na på raden kommer att vara 100, såvida inte k = 0.

Låt S beteckna summan av alla k. Då gäller 0 ≤ S ≤ 10^5.

Produktionskedjan är designad på ett sådant sätt att ingen person kan få tillbaka ett brev de redan arbetat med.

Utdata

Skriv ut en rad med alla i som uppfyller U_p = M_p, i stigande ordning.

Det garanteras att om U_p = M_p så kommer detta stämma med marginal, mer specifikt I_p - M_p > 10^-4. Om tvärt om U_p ≠ M_p så kommer det finnas marginal åt andra hållet: M_p - I_p > 10^-4.

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
112Varje person skickar brev till högst en person (d.v.s k ≤ 1) och tar emot brev från max en person
217Varje person tar emot brev från exakt en annan person, förutom person 1 som inte tar emot från någon
321Om person i skickar till person j så är i < j
425N, S ≤ 10
525Inga ytterligare begränsningar.

Förklaring av exempelfall

Här följer tre grafer som representerar de tre exempelfallen. Varje person representeras av en nod. På varje kant är mängden kuvert som skickas utskrivet i enheten kps, kuvert per sekund.

Notera att i testfallsgrupp 1 skulle enbart exempelfall 1 kunna förekomma, i testfallsgrupp 2 enbart exempelfall 2, och i testfallsgrupp 3 enbart exempelfall 3. I testfallsgrupp 4 och 5 skulle alla tre exempelfall kunna förekomma.

(그림은 원문 저장소에서 볼 수 있습니다)

Figur 1: Sample 1

(그림은 원문 저장소에서 볼 수 있습니다)

Figur 2: Sample 2

(그림은 원문 저장소에서 볼 수 있습니다)

Figur 3: Sample 3

예제

예제 1

입력
8
7 0
10 1 6 100
8 1 4 100
9 1 1 100
11 0
12 1 5 100
10 1 3 100
5 0
출력
1 2 3 7 8

예제 2

입력
10
16 3 2 50 4 25 6 25
9 2 9 75 5 25
2 1 8 100
5 0
1 0
2 2 3 90 7 10
1 0
1 0
5 1 10 100
6 0
출력
1 5 6 8 9

예제 3

입력
6
10 3 2 25 3 25 4 50
1000 1 5 100
1000 1 5 100
1000 1 6 100
1 1 6 100
1000 0
출력
1 5

출처 표기

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