/* 1993 ACM Finals, Problem H, Scanner Ed Karrels, Aug. 1996 */ #include void PrintGrid(int grid[][10]) { int i, j; for (i=0; i<10; i++) { for (j=0; j<15; j++) { putchar(grid[j][i] ? '#' : '.'); } putchar('\n'); } putchar('\n'); } int Comb(int a[], int n) { int i; if (n==0) return -1; if (a[0]) { i = Comb(a+1, n-1); if (i==-1) return -1; a[0] = 0; a[i-1] = 1; return i; } else { for (i=1; i=0 && y<10) { c += grid[x][y]; x--; y++; } if (c != sensor[lvl+10]) return 0; /* upper left diagonal */ x = lvl; y = 9; c = 0; while (x>=0 && y>=0) { c += grid[x][y]; x--; y--; } if (c != sensor[lvl+49]) return 0; } else { for (i=0; i<10; i++) { /* lower left diagonal */ x = i+5; y = 9; c = 0; while (x<15 && y>=0) { c += grid[x][y]; x++; y--; } if (c != sensor[i+24]) return 0; /* upper left diagonal */ x = 14; y = 9-i; c = 0; while (x>=0 && y>=0) { c += grid[x][y]; x--; y--; } if (c != sensor[i+63]) return 0; c = 0; for (j=0; j<15; j++) { c += grid[j][i]; } if (c != sensor[i]) return 0; } } return 1; } int Try(int sensor[], int grid[15][10], int lvl) { int j; if (lvl == 15) return 1; for (j=0; j<10; j++) { grid[lvl][j] = (j < (10 - sensor[lvl+34]) ? 0 : 1); } /* printf("Trying lvl %d\n", lvl); PrintGrid(grid); */ do { if (Check(sensor, grid, lvl)) { if (Try(sensor, grid, lvl+1)) return 1; } } while (-1 != Comb(grid[lvl], 10)); return 0; } int main(void) { int grid[15][10]; int i, j; int sensor[73]; int n_images, image_no; scanf("%d", &n_images); for (image_no=0; image_no