루미 알고리즘

#1315플래티넘Bingo

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

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

Problem

Ture spelar en speciell sorts bingo som går till på följande sätt:

  • Han har en kvadratisk bricka med NxN rutor, vardera innehållande ett heltal. Samma tal kan finnas i flera rutor.
  • Spelledaren ropar ut ett godtyckligt heltal i taget. Om Ture har detta tal på sin bricka får han kryssa över det. Om han har talet i flera rutor måste han välja en enda ruta att kryssa över.
  • När Ture har kryssat en full rad med N tal, antingen horisontellt, vertikalt eller diagonalt (se figur), så har han fått “bingo” och vinner en resa till BOI (Bingo Olympiad International).

Ture förlitar sig inte på turen utan har fuskat till sig den följd av tal som kommer att ropas ut. Skriv ett program som, givet Tures bricka samt följden av tal, beräknar efter hur många utrop Ture får bingo om han spelar optimalt.

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

Figur 1: Vänster: De två diagonala raderna (prickade linjer) samt exempel på en horisontell och en vertikal rad (streckade linjer). Höger: Ett möjligt sätt att kryssa i det första exemplet.

Indata

Den första raden innehåller heltalen N och K (1 ≤ N ≤ 100, 1 ≤ K ≤ 10000), brickans sidlängd och antalet utrop.

Därefter följer N rader som vardera innehåller N heltal i intervallet 1 … 1000. Detta är Tures bingobricka.

Slutligen följer en rad med K heltal i samma intervall, de utropade talen i den ordning de ropas ut.

Utdata

Skriv ut ett heltal: det minsta antalet utrop som behövs innan Ture får en full rad (horisontellt, vertikalt eller diagonalt). Det kommer aldrig krävas mer än K utrop.

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
120K ≤ 100
240Det är aldrig optimalt att försöka få bingo längs diagonalerna.
340Inga ytterligare begränsningar.

예제

예제 1

입력
5 10
1 3 2 4 6
2 2 3 1 1
1 3 5 2 7
2 4 1 3 3
3 3 1 3 4
4 1 3 5 1 6 7 2 8 3
출력
6

예제 2

입력
8 30
15 20 20 13 18 13 14 20
17 11 13 20 9 10 8 19
19 12 9 8 16 19 9 4
20 17 3 9 1 14 14 9
12 20 19 5 16 5 19 17
3 4 17 8 5 14 18 17
9 14 16 13 13 9 13 1
13 7 8 3 19 19 5 7
2 5 1 1 20 4 18 6 20 2 19 17 15 1 6 14 17 7 12 10 10 17 18 3 3 12 13 9 18 17
출력
28

출처 표기

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