루미 알고리즘

#1438플래티넘Cirkelskivevärlden

PO 2018 결선코딩출제 Johan Sannemo스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

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

Problem

Det är morgon på Cirkelskivevärlden, och solen håller på att gå upp. Soluppgången på Cirkelskivevärlden är inte som soluppgångar på de flesta världar. Detta är kanske inte så konstigt, då Cirkelskivevärlden inte är som de flesta världar (den är nämligen en cirkelskiva, till skillnad från de mer konventionella sfäriska världarna). Cirkelskivevärlden är nämligen fylld med magi, och som alla vet undviker gärna solljuset att färdas genom starka magiska fält.

Som en av Cirkelskivevärldens mest kraftfulla magiker som bor på motsatt sida av Cirkelskivevärlden än där soluppgången först träffar cirkelskiveytan är detta ett faktum som du tycker är ytterst trevligt. Du älskar nämligen sovmorgonar, och om du fick välja skulle solen helst stanna på sin sida av världen någon timme längre på morgonarna. Speciellt nu när du precis köpt ytterst solljuskänsliga hyacinther. Turen i oturen ligger dock i att du som magiker kan påverka solljusets framfart över Cirkelskivevärlden genom att förstärka vissa av de magiska fält som finns i världen.

Världen kan modelleras som ett n × n rutnät, där alla rutor som ingår i en cirkelskiva kring rutnätets mitt existerar på världen (exakt vilka rutor som existerar ges av indata). I rutan på koordinat (r, c) finns ett magiskt fält med styrkan m_{r, c}. För att öka fältstyrkan med 1 behöver du använda dig av p_{r, c} trollformler på rutan. Du kan inte öka fältstyrkan med mindre än 1, men du kan öka den med 1 upprepade gånger.

När solen går upp börjar den att försöka lysa upp position (0, (n - 1)/2) – högst upp i rutnätet – och sprider sig sedan på följande vis (se även figuren nedan). Antag att solen försöker lysa upp en viss ruta (r, c). Det tar då m_{r, c} sekunder innan solen lyser på rutan. Så fort solen lyser på rutan börjar den försöka lysa på de (upp till fyra) rutor som rutan delar en kant med.

Du bor på rutan (n-1, (n-1)/2) (längst ner i rutnätet). Totalt kan du k stycken trollformler, som du vill använda dig av för att öka fältstyrkan på olika rutor i världen. Din uppgift är att använda trollformlerna på ett sätt som maximerar antalet sekunder innan solen lyser upp rutan du bor på.

Indata

Observera: testdatan på detta problem är öppen. Du kan ladda ner den i menyn till höger (1.in, 2.in, 3.in, 4.in, 5.in).

Den första raden innehåller ett heltal 0 ≤ t ≤ 5, ordningstalet för detta testfall. Fallet t = 0 representar exempelfallet, och ska ignoreras (du kan skriva ut vad du vill då).

Den andra raden innehåller två heltal n och k, där n är udda.

De följande n raderna innehåller talen m_{r, c}. Den i:te raden innehåller talen m_{i, c} för alla 0 ≤ c < n.

De följande n raderna innehåller talen p_{r, c}. Den i:te raden innehåller talen p_{i, c} för alla 0 ≤ c < n.

Om en ruta inte är med på cirkelskivan är både m_{r, c} och p_{r, c} lika med -1, annars är de alltid positiva.

Utdata

Skriv ut n rader med n tal vardera. Den i:te raden ska innehålla antalet trollformler du använder på rutorna (i, c) för 0 ≤ c < n. Antalet trollformler du använder på ruta (i, c) måste vara en multipel av p_{i, c}.

Poängsättning

Din lösning kommer att få poäng på varje av de fem testfallen.

Varje testfall poängsätts på följande vis. Antag att tiden det tar för solen att nå dig är T sekunder om inga trollformler används, att den maximala tiden någon deltagare lyckas åstadkomma är T_max och att din tid är T_du.

Din poäng på testfallet är då

20 · (T_du - T)/(T_max - T).

Under tävlingen kommer T_max vara satt till 2 · T.

Förklaring till exemplet

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

Siffrorna anger den magiska fältstyrkan före trollningen (vänstra figuren) och efter trollningen (övriga figurer). Färgmarkeringen visar vilka rutor som är upplysta efter 0, 4 respektive 6 sekunder. Den nedersta rutan, där du bor, blir upplyst efter 10 sekunder. Det finns många andra sätt att trolla som ger samma fördröjning.

예제

예제 1

입력
0
5 5
-1 -1 1 -1 -1
-1 1 1 1 -1
1 1 1 1 1
-1 1 1 1 -1
-1 -1 1 -1 -1
-1 -1 1 -1 -1
-1 1 1 1 -1
1 1 1 1 1
-1 1 1 1 -1
-1 -1 1 -1 -1
출력
0 0 1 0 0
0 0 1 0 0
0 0 1 0 0
0 0 1 0 0
0 0 1 0 0

출처 표기

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