스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
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.
| Grupp | Poäng | Gränser |
|---|---|---|
| 1 | 20 | K ≤ 100 |
| 2 | 40 | Det är aldrig optimalt att försöka få bingo längs diagonalerna. |
| 3 | 40 | Inga 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