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