루미 알고리즘

#1321다이아Kötid

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

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

Problem

Du har fått jobb på ett välkänt nöjesfält. Det finns många intressanta problem där som behöver lösas, men ditt första uppdrag är att förbättra informationen till de som köar för berg- och dalbanan. Det bästa de har nu är en skylt som säger “20 minuters kö härifrån”, oavsett hur lång kön är.

Den enda berg- och dalbanevagnen har plats för K stycken personer och tar 1 minut för att köra ett varv. Av- och påstigning tar ingen tid. Besökare kommer till kön i grupper som inte kan tänka sig att delas upp mellan flera vagnar. Det händer därför ibland att en vagn inte fylls helt då nästföljande grupp är för stor. När detta sker så gör attraktionsvärdarna sitt bästa med att fylla vagnen genom att låta någon grupp som står senare i kön gå före. Om det till exempel finns x stycken lediga platser i nuvarande vagn så letar de upp nästa grupp i kön som har storlek mindre än eller lika med x och fyller vagnen med den. Denna process upprepas sedan tills dess att ingen mer grupp får plats i vagnen. Ditt uppdrag är att för varje grupp i kön räkna ut hur länge de kommer att behöva köa.

Indata

Den första raden innehåller två heltal N och K (1 ≤ N ≤ 10^6, 1 ≤ K ≤ 10^8), antal grupper i kön och antal personer per vagn. På nästa rad följer N stycken heltal g_i, (1 ≤ g_i ≤ K), storleken på grupperna i kön. Den första gruppen i indata är den som står först i kön.

Utdata

Skriv ut en rad med N stycken heltal separerade av mellanslag, kötiden för varje grupp.

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 ≤ 1000, 1 ≤ K ≤ N
240N ≤ 10^5
340Inga ytterligare begränsningar.

Förklaring av exempelfall 1

Låt oss anta att det står tre grupper i kö, och varje vagn rymmer precis tre personer, och att kön i början har utseende [2,2,1]. Först blir det första gruppens tur att kliva i vagnen. Nu har vagnen en plats kvar, och den sista gruppen i kön (bestående av en person) får gå före den andra gruppen, som måste vänta på nästa tur. Svaret blir då att första och sista gruppen har 0 kötid, och den andra gruppen har 1 enhet kötid. Vi skriver alltså ut 0 1 0.

예제

예제 1

입력
3 3
2 2 1
출력
0 1 0 

예제 2

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

출처 표기

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