12b.c (1466B)
1 #include <inttypes.h> 2 #include <stdio.h> 3 #include <stdlib.h> 4 #include <string.h> 5 6 #define N 200 7 #define T 5 8 #define isnum(c) (c == '-' || (c >= '0' && c <= '9')) 9 10 char *buf, line[N]; 11 int64_t s, m, n, p, a[N], mem[N][N][N]; 12 13 int64_t readl(int64_t nums[], char *buf) { 14 int64_t i; 15 for (i = 0; *buf; buf++) { 16 if (!isnum(*buf)) continue; 17 nums[i++] = atoll(buf); 18 while (isnum(*buf)) buf++; 19 } 20 return i; 21 } 22 23 int64_t f(int64_t j, int64_t i, int64_t k) { 24 if (mem[j][i][k] != -1) 25 return mem[j][i][k]; 26 if (i > n || k > a[i]) 27 return mem[j][i][k] = 0; 28 29 int64_t ret = 0; 30 if (j == m) 31 ret = i == n && k == 0; 32 if (line[j] == '#' || line[j] == '?') 33 ret += f(j+1, i, k+1); 34 if ((line[j] == '.' || line[j] == '?') && (k == 0 || k == a[i])) 35 ret += f(j+1, i+(k>0), 0); 36 return mem[j][i][k] = ret; 37 } 38 39 int main() { 40 while ((buf = fgets(line, N, stdin)) != NULL) { 41 n = readl(a, buf); 42 43 /* Multiply strings by T (1 for part 1, 5 for part 2) */ 44 for (m = 0; line[m] != ' '; m++) ; 45 for (int64_t t = 1; t < T; t++) { 46 memcpy(a + t * n, a, n * sizeof(int64_t)); 47 line[t*(m+1)-1] = '?'; 48 memcpy(line + t * (m + 1), line, (m + 1)); 49 } 50 m = T*(m+1); 51 line[m-1] = '.'; 52 line[m] = 0; 53 n *= T; 54 a[n] = 0; 55 56 /* Reset memoization table */ 57 for (int64_t j = 0; j <= m; j++) 58 for (int64_t i = 0; i <= n; i++) 59 for (int64_t k = 0; k <= m; k++) 60 mem[j][i][k] = -1; 61 62 /* Compute solution */ 63 s += f(0, 0, 0); 64 } 65 66 printf("%" PRId64 "\n", s); 67 return 0; 68 }