Tävlingsprogrammering/Uppgifter/Bingo

Från Wikibooks
Hoppa till navigering Hoppa till sök


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).
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.

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