루미 알고리즘

#1432플래티넘Snömur

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

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

Problem

Efter förnedringen i snöbollskriget tänker Sverige bygga en snömur, och tvinga Finland att betala för den. Muren ska ha en viss bredd W, och vara så hög som möjligt (it's going to be yuuuge!).

Som byggmaterial finns det ett antal snöblock som alla har höjden 1, men kan ha olika bredder. När muren konstrueras måste varje block uppfylla följande en regel: på raden under blocket, på de två positioner blocket har sina ändpunkter, måste det ligga ett block precis till höger och vänster om punkten, undantaget början och slutet på en rad, där det istället måste finnas en ändpunkt på varje rad.

Det får dessutom inte finnas hålrum på samma position på två direkt efterföljande rader i muren (den tomma raden precis ovanför muren räknas inte).

Följande bild illustrerar några otillåtna (vänster) och tillåtna (höger) murar:

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

Figur 1: Ett antal otillåtna (vänster) och tillåtna (höger) murar.

Givet bredden W och de möjliga blocken, konstruera en så hög mur som möjligt.

Indata

Observera: testdatan på detta problem är öppen. Du kan ladda ner den i attachments eller här (https://progolymp.se/uploads/snomur.zip).

Den första raden innehåller tre heltal heltal T, N och W - testfallets nummer, antalet block och bredden på muren. Nästa rad innehåller N heltal, bredden på varje block.

Utdata

På den första raden ska du skriva ut höjden på din mur, H.

Du ska sedan skriva ut H rader, en för varje rad i din mur. Rad i ska först ha ett tal B, antalet block på den raden i din mur. Detta ska följas av B par av heltal P_{i,j}, L_{i,j} positionen och längden för det j:te blocket på raden.

Inskickning

När du skickar in din lösning räcker det med ett program som läser in testfallets nummer T och skriver ut lösningen för det testfallet.

Om du inte vill skriva ett sådant program själv kan du använda en sida vi konstruerade: http://progolymp.se/uploads/snokaosgen.html där du kan klistra in alla dina lösningar och få ett Python 3-program som du kan skicka in.

Poängsättning

Ditt program kommer att testas på testfall, och poängsättas baserat på hur det står sig relativt domarnas lösning.

Antag att på ett testfall så får ditt program höjden X, och dommar lösningen får höjden Y. Då får du 10 × X/Y poäng på testfallet, avrundat till två decimaler.

Din poäng för en inskickning är summan av poängen för testfallen, och din totala poäng är poängen för den bästa inskickningen. Det går alltså inte att kombinera testfall mellan olika inskickningar, utan du måste skicka in ett enda program som maximerar din poäng på alla testfall samtidigt.

Din lösning kan maximalt få 100 poäng, även om den är bättre än den domarna skrivit.

출처 표기

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