Tävlingsprogrammering/Uppgifter/Bingo
Bingo
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.
Indata
Första raden innehåller brickans dimension N, där 1≤N≤100, och antalet utrop K, där 1≤K≤10000. Därefter följer N rader vardera innehållande 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
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.
Exempel 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
ska ge svaret
6
Exempel 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
ska ge svaret
28
Lösning
[redigera]Här gäller det att inte börja testa alla möjligheter att kryssa över talen på brickan, eftersom antalet möjligheter kan växa exponentiellt. Istället fokuserar vi på en rad i taget (vågrätt, lodrätt eller diagonalt) och räknar ut efter hur många utrop just den raden blir full om man alltid prioriterar att kryssa i denna rad. Detta kan göras genom att man först sparar hur många förekomster av varje tal som finns i raden, och sedan bara minskar detta antal varje gång ett tal ropas ut. Slutligen väljer man förstås att prioritera den rad som kräver det minsta antalet utrop.
Lösning i C:
#include <stdio.h>
int MIN(int p, int q) {return p<q?p:q;}
int N, b[100][100], K, utrop[10000];
int run(int x, int y, int dx, int dy) { //Hur många utrop krävs för bingo i raden (x,y)+i(dx,dy), i=0..N-1
int c[1001],i,k,left;
for(i=0;i<=1000;i++) c[i]=0; //Sätt talräknarna till 0
for(i=0;i<N;i++) c[b[y+i*dy][x+i*dx]]++; //Räkna antalet förekomster i den aktuella raden
left=N; //Antal okryssade rutor i raden
for(k=0;k<K;k++) { //Loopa över utropen
if(c[utrop[k]]>0) { //Om detta tal finns i raden (okryssat)
c[utrop[k]]--; left--; //Minska räknarna
if(left==0) return k+1; //BINGO!!!
}
}
return K+1; //Ingen bingo på denna rad
}
int main() {
int i,j,m;
scanf("%d %d",&N,&K);
for(i=0;i<N;i++) for(j=0;j<N;j++) scanf("%d", &b[i][j]);
for(i=0;i<K;i++) scanf("%d", &utrop[i]);
m=K+1; //Innehåller snabbaste bingon hittills, kommer alltid hitta en med m<=K
for(i=0;i<N;i++) m=MIN(m, run(0,i,1,0)); //Testa vågräta rader
for(i=0;i<N;i++) m=MIN(m, run(i,0,0,1)); //Testa lodräta rader
m=MIN(m, run(0,0,1,1)); //Testa ena diagonalen
m=MIN(m, run(0,N-1,1,-1)); //Testa andra diagonalen
printf("%d\n", m);
return 0;
}
Lösning i Haskell (av Anton Fors Hurdén):
import Data.List
import Control.Monad
play :: Int -> [Int] -> [Int] -> Int
play n [] _ = n
play n _ [] = n
play n (number:numbers) row = play (n + 1) numbers $ delete number row
diagonals board = zipWith (!!) (reverse board) [0..] : [zipWith (!!) board [0..]]
main = do
[n, k] <- getLine >>= return . (map read) . words
board <- replicateM n $ getLine >>= return . (map read) . words
numbers <- getLine >>= return . (map read) . words
print $ minimum $ map (play 0 numbers) $ board ++ transpose board ++ diagonals board