diff options
| -rw-r--r-- | 12/QG-2017/virus.c | 71 | ||||
| -rwxr-xr-x | 12/QG-2017/virus_randinp.py | 9 |
2 files changed, 47 insertions, 33 deletions
diff --git a/12/QG-2017/virus.c b/12/QG-2017/virus.c index d4a56ba..add408c 100644 --- a/12/QG-2017/virus.c +++ b/12/QG-2017/virus.c @@ -1,22 +1,31 @@ #include <stdio.h> +#include <stdlib.h> #include <string.h> -char difflim(char lim, char *s, short len) +char T[3001], **mem; + +char difflim(char lim, short len, short beg) { - char i, count = 0; + char count = 0, *s, *z; + short i; + if (mem[len - 1][beg] >= 0) + return mem[len - 1][beg] <= lim; + s = T + beg; + z = s + len; for (i = 0; i < len; i++) - if (s[i] != s[len + i] && ++count > lim) - return 0; - return 1; + if ((count += s[i] != z[i]) > 10) + break; + return (mem[len - 1][beg] = count) <= lim; } int main() { FILE *f = fopen("VIRUS.INP", "r"); - char i, n, level, T[3001], levels[10]; + char i, n, level, *levels; short m, j, k, len, lenpos, pos[3000], res[11] = {}; fscanf(f, "%hhd\n%s\n", &n, T); + levels = malloc(n); for (i = 0; i < n; i++) fscanf(f, "%hhd\n", levels + i); fclose(f); @@ -45,27 +54,41 @@ int main() { } } - f = fopen("VIRUS.OUT", "w"); - for (i = 0; i < n; i++) { - level = levels[i]; - if (level && !res[level]) { - if (level * 2 > m) - res[level] = m / 2; - else - res[level] = level; - for (j = 0; j < level; j++) - if (res[j] > res[level]) - res[level] = res[j]; + mem = malloc(m * sizeof(char *) / 2); + for (len = 0; len < m / 2; len++) { + mem[len] = malloc(m - len * 2); + for (j = 0; j < m - len * 2; j++) + mem[len][j] = -1; + } - for (len = m / 2; len > res[level]; len--) - for (j = 0; j <= m - len * 2; j++) - if (difflim(level, T + j, len)) { - res[level] = len; - break; - } + for (level = 1; level <= 10; level++) { + for (i = j = 0; i < n; i++) + if (levels[i] == level) + j++; + if (!j) + continue; + + if (level * 2 > m) { + res[level] = m / 2; + continue; } - fprintf(f, "%hd\n", res[level]); + + res[level] = level; + for (j = 0; j < level; j++) + if (res[j] > res[level]) + res[level] = res[j]; + + for (len = m / 2; len > res[level]; len--) + for (j = 0; j <= m - len * 2; j++) + if (difflim(level, len, j)) { + res[level] = len; + break; + } } + + f = fopen("VIRUS.OUT", "w"); + for (i = 0; i < n; i++) + fprintf(f, "%hd\n", res[levels[i]]); fclose(f); return 0; } diff --git a/12/QG-2017/virus_randinp.py b/12/QG-2017/virus_randinp.py deleted file mode 100755 index 566e452..0000000 --- a/12/QG-2017/virus_randinp.py +++ /dev/null @@ -1,9 +0,0 @@ -#!/usr/bin/env python3 -import random -import string - -with open('VIRUS.INP', 'w') as f: - f.write('10\n') - for _ in range(3000): - f.write(random.choice(string.ascii_lowercase)) - f.write('\n0\n1\n2\n3\n5\n6\n7\n8\n9\n10\n') |