/* Blocks (IOI 2000) Copyright (C) 2002 Flavio Chierichetti This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA Il programma legge 'types.in' da file, si aspetta 'block.in' su standard input e scrive 'block.out' su standard output. The idea behind: Innanzitutto qualche parola sui blocchi in ingresso. Ogni blocco può essere ruotato prima di essere inserito nella costruzione; in questa soluzione le rotazioni vengono fatte prima dell'inserimento, e ogni rotazione diversa dalle altre è considerata blocco a sé stante. Ogni blocco può essere inscritto in un parallelepipedo. Ogni parallelepipedo ha 6 facce e può quindi essere 'appoggiato' su di un piano in 6 modi differenti. Inoltre per ogni faccia appoggiata il parallelepipedo può essere ruotato attorno ad una perpendicolare al piano d'appoggio in 4 modi diversi (possiamo ruotare di 90 gradi alla volta). Quindi ogni blocco ha al più 24 (6 * 4) diverse rotazioni; blocchi con assi di simmetria hanno ovviamente meno rotazioni. La dimensione del vettore di blocchi è uguale a NBaseBlk (numero di blocchi base) moltiplicato per 24; il vettore è sovradimensionato poiché per i blocchi descritti in types.in esistono complessivamente 105 diverse rotazioni (ma questo è un dato "sperimentale"). La parte algoritimica interessante è, però, quella della ricerca del minimo numero di blocchi con i quali si può costruire il solido di ingresso: la soluzione qui adottata è un branch-and-bound. La regola di taglio è la seguente: il numero minimo di blocchi necessari per coprire tutto il solido in un qualsiasi momento è uguale al numero di blocchi unitari non ancora coperti diviso il massimo volume di un blocco (risultato arrotondato per eccesso) sommato al numero di blocchi usati fino a quel momento. Se quindi questo numero è maggiore o uguale al numero di blocchi della migliore soluzione fino a quel momento trovata, è inutile andare avanti. */ #include #include /* Transform serve per ruotare di 90 gradi una coordinata attorno ad un asse: Old: (x, y, z) NewX: (x, Transform(z), y) NewY: (Transform(z), y, x) NewZ: (Transform(y), x, z) */ #define Transform(a) ( ( - ( 2 * (a) + 1 ) - 1 ) / 2 ) enum { NBaseBlk = 12 , MaxVSol = 50 , MaxBlk = 4 , MaxDSol = 7 }; typedef struct { int x, y, z; } coord; typedef struct { /* N: Label del blocco V: Volume (numero di blocchi unitari) del blocco B: Vettore delle coordinate dei blocchi unitari del blocco */ int N, V; coord B[MaxBlk]; } block; /* Vettore dei blocchi esistenti */ block Block[NBaseBlk * 24]; /* Numero di elementi di Block */ int NBlock; /* Volume del solido */ int V; /* Rappresentazione tridimensionale del solido */ int Space[MaxDSol + 2 * MaxBlk][MaxDSol + 2 * MaxBlk][MaxDSol + 2 * MaxBlk]; /* Try: Blocchi inseriti nella ricorsione Depth: Livello di ricorsione Best: Blocchi inseriti nella migliore soluzione finora trovata NBest: Numero di elementi di Best */ int Try[MaxVSol], Depth, Best[MaxVSol], NBest; /* Acquisizione dei blocchi */ void getBlocks(); void Rotate(block Blk); void Normalize(block *Blk); /* Acquisizione solido */ void getSolid(); /* Comparazione tra tipi di dato */ int CompareCoord(const void *a, const void *b); int CompareBlk(const void *a, const void *b); /* Funzione ricorsiva del branch-and-bound */ void Search(); int main(int argc, char *argv[]) { int i; getBlocks(); getSolid(); /* Parti dalla soluzione peggiore (tutti blocchi da 1) */ NBest = V; for ( i = 0 ; i < NBest ; i++ ) Best[i] = NBlock - 1; Search(); /* Restituisci block.out */ printf("%d\n", NBest); for ( i = 1 ; i <= NBest ; i++ ) printf("%d%c", Block[Best[i - 1]].N, (i < NBest) ? ' ' : '\n'); return 0; } /* getBlocks() prende da 'types.in' i 12 blocchi e li passa alla funzione Rotate che li ruoterà e inserirà in Block. Alla fine i blocchi vengono ordinati in ordine decrescente per velocizzare la ricorsione. */ void getBlocks() { FILE *f; block Base; int i, j; f = fopen("types.in", "r"); for ( i = 0 ; i < NBaseBlk ; i++ ) { fscanf(f, " %d %d", &Base.N, &Base.V); for ( j = 0 ; j < Base.V ; j++ ) fscanf(f, " %d %d %d", &Base.B[j].x, &Base.B[j].y, &Base.B[j].z); Rotate(Base); } fclose(f); qsort(Block, NBlock, sizeof(block), CompareBlk); } /* Rotate() prende un blocco e lo ruota 64 volte (4 per l'asse x * 4 per y * 4 per z). Ad ogni rotazione il blocco viene normalizzato e, se non è già presente nel vettore Block, viene inserito. */ void Rotate(block Blk) { coord i; int n, m; int swap; for ( i.x = 0 ; i.x < 4 ; i.x++ ) { for ( i.y = 0 ; i.y < 4 ; i.y++ ) { for ( i.z = 0 ; i.z < 4 ; i.z++ ) { Normalize(&Blk); for ( n = 0 ; n < NBlock ; n++ ) if ( Blk.V == Block[n].V ) { for ( m = 0 ; m < Blk.V ; m++ ) if ( CompareCoord(&Blk.B[m], &Block[n].B[m]) ) break; if ( m == Blk.V ) break; } if ( n == NBlock ) { Block[NBlock].V = Blk.V; for ( n = 0 ; n < Blk.V ; n++ ) Block[NBlock].B[n] = Blk.B[n]; Block[NBlock].N = Blk.N; NBlock++; } /* Rotazione su z */ for ( n = 0 ; n < Blk.V ; n++ ) { swap = Blk.B[n].x; Blk.B[n].x = Transform(Blk.B[n].y); Blk.B[n].y = swap; } } /* Rotazione su y */ for ( n = 0 ; n < Blk.V ; n++ ) { swap = Blk.B[n].x; Blk.B[n].x = Transform(Blk.B[n].z); Blk.B[n].z = swap; } } /* Rotazione su x */ for ( n = 0 ; n < Blk.V ; n++ ) { swap = Blk.B[n].y; Blk.B[n].y = Transform(Blk.B[n].z); Blk.B[n].z = swap; } } } /* Normalize() prende un blocco, ordina i blocchi unitari al suo interno (secondo la funzione CompareCoord) e trasla il blocco in maniera che il primo blocco unitario sia in posizione (0, 0, 0). */ void Normalize(block *Blk) { int i; coord c; qsort(Blk->B, Blk->V, sizeof(coord), CompareCoord); c = Blk->B[0]; for ( i = 0 ; i < Blk->V ; i++ ) { Blk->B[i].x -= c.x; Blk->B[i].y -= c.y; Blk->B[i].z -= c.z; } } /* getSolid() prende le coordinate dei blocchi unitari del solido da standard input e ci riempe l'array tridimensionale Space. */ void getSolid() { int i; coord c; scanf(" %d", &V); for ( i = 0 ; i < V ; i++ ) { scanf(" %d %d %d", &c.x, &c.y, &c.z); Space[c.x + MaxBlk - 1][c.y + MaxBlk - 1][c.z + MaxBlk - 1] = 1; } } int CompareCoord(const void *a, const void *b) { coord A, B; A = *((coord*) a); B = *((coord*) b); if ( A.x == B.x ) if ( A.y == B.y ) return A.z - B.z; else return A.y - B.y; else return A.x - B.x; } int CompareBlk(const void *a, const void *b) { return ((block*)b)->V - ((block*)a)->V; } /* Search() è la funzione ricorsiva che cerca la miglior soluzione */ void Search() { coord i; int found, n, m; /* Se abbiamo coperto tutti i blocchi unitari, abbiamo una nuova soluzione migliore */ if ( !V ) { NBest = Depth; for ( n = 0 ; n < NBest ; n++ ) Best[n] = Try[n]; return; } if ( Depth + (V + MaxBlk - 1) / MaxBlk >= NBest ) return; /* Cerca il primo blocco unitario non coperto */ found = 0; for ( i.x = MaxBlk ; !found ; i.x++ ) for ( i.y = MaxBlk ; !found ; i.y++ ) for ( i.z = MaxBlk ; !found ; i.z++ ) if ( Space[i.x][i.y][i.z] ) found = 1; i.x--; i.y--; i.z--; /* Prova ad attaccare al blocco unitario ognuno dei blocchi */ for ( n = 0 ; n < NBlock ; n++ ) { for ( m = 0 ; m < Block[n].V ; m++ ) if ( Space[i.x + Block[n].B[m].x][i.y + Block[n].B[m].y][i.z + Block[n].B[m].z] ) Space[i.x + Block[n].B[m].x][i.y + Block[n].B[m].y][i.z + Block[n].B[m].z] = 0; else break; if ( m < Block[n].V ) { for ( m-- ; m >= 0 ; m-- ) Space[i.x + Block[n].B[m].x][i.y + Block[n].B[m].y][i.z + Block[n].B[m].z] = 1; continue; } Try[Depth] = n; V -= m; Depth++; Search(); V += m; Depth--; for ( m-- ; m >= 0 ; m-- ) Space[i.x + Block[n].B[m].x][i.y + Block[n].B[m].y][i.z + Block[n].B[m].z] = 1; } }