diff options
Diffstat (limited to '2ndary/12/QG-2017')
| -rw-r--r-- | 2ndary/12/QG-2017/README.md | 80 | ||||
| -rw-r--r-- | 2ndary/12/QG-2017/virus.c | 94 |
2 files changed, 174 insertions, 0 deletions
diff --git a/2ndary/12/QG-2017/README.md b/2ndary/12/QG-2017/README.md new file mode 100644 index 0000000..9b79939 --- /dev/null +++ b/2ndary/12/QG-2017/README.md @@ -0,0 +1,80 @@ +# KÌ THI CHỌN HỌC SINH GIỎI QUỐC GIA THPT NĂM 2017 + +Môn: **TIN HỌC** + +## Ngày thi thứ nhất: 05/01/2017 + +Thời gian: **180** phút + +### Tổng quan ngày thi thứ nhất + +| Tên bài | File chương trình | File dữ liệu | File kết quả | Điểm | +| ------------- | :---------------: | :----------: | :----------: | :---: | +| Virus | VIRUS.\* | VIRUS.INP | VIRUS.OUT | 7 | +| Dãy Fibonacci | FIBSEQ.\* | FIBSEQ.INP | FIBSEQ.OUT | 7 | +| Trò chơi | BGAME.\* | BGAME.INP | BGAME.OUT | 6 | + +Dấu `*` được thay thế bởi `PAS` hoặc `CPP` của ngôn ngữ lập trình được sử dụng +tương ứng là Pascal hoặc C++. + +### Virus + +*TextFile* là một virus chuyên tấn công các file văn bản theo phương thức sau: +Sao chép một đoạn các ký tự liên tiếp trong nội dung của file văn bản vào bộ +nhớ trong, thay đổi một số ký tự trong đoạn này, sau đó chèn đoạn văn bản đã +thay đổi vào ngay sau đoạn văn bản vừa sao chép trong file văn bản. + +Vinh đang phát triển phần mềm để phát hiện một file văn bản đã bị nhiễm virus +nói trên hay chưa. Vì thế, Vinh cần giải quyết bài toán sau: Cho xâu ký tự *T* +và số nguyên không âm *k*, xâu con gồm các ký tự từ vị trí *p* đến vị trí *q* +của xâu T được gọi là đoạn có khả năng bị virus sao chép mức *k* nếu nó sai +khác với xâu con gồm các ký tự từ vị trí *q*+1 đến vị trí *q*+(*q*-*p*+1) của +xâu T ở không quá k vị trí. + +Ví dụ, xét xâu *T* = `zabaaxy` và *k* = 1. Đoạn văn bản `ab` từ ký tự thứ 2 đến +ký tự thứ 3 là đoạn văn bản độ dài 2 có khả năng bị virus sao chép mức 1 vì nó +khác với đoạn văn bản `aa` gồm các ký tự từ ký tự thứ 4 đến ký tự thứ 5 của xâu +*T* ở 1 vị trí. + +#### Yêu cầu + +Cho xâu ký tự *T* và *n* số nguyên không âm *k*<sub>1</sub>, *k*<sub>2</sub>, +…, *k<sub>n</sub>*. Với mỗi giá trị *k<sub>i</sub>*, hãy tìm độ dài đoạn dài +nhất trong xâu *T* có khả năng bị virus sao chép mức *k<sub>i</sub>* (*i* = 1, +2, …, *n*). + +#### Dữ liệu + +* Dòng đầu chứa số nguyên dương *n* (*n* ≤ 10); +* Dòng thứ hai chứa một xâu *T* gồm các chữ cái in thường lấy từ tập 26 chữ cái + tiếng Anh từ `a` đến `z`; +* Dòng thứ *i* trong số *n* dòng tiếp theo ghi số nguyên không âm + *k<sub>i</sub>* (*k<sub>i</sub>* ≤ 10, *i* = 1, 2, …, *n*). + +#### Kết quả + +*n* dòng, dòng thứ *i* ghi một số nguyên không âm là độ dài đoạn dài nhất có +khả năng bị virus sao chép mức *k<sub>i</sub>* , *i* = 1, 2, …, *n*. Ghi *0* +nếu không tìm được đoạn như vậy. + +#### Ràng buộc + +Ký hiệu *m* là độ dài của xâu *T*. + +* Có 40% số lượng test thỏa mãn điều kiện: *m* ≤ 300; +* Có thêm 30% số lượng test thỏa mãn điều kiện: *m* ≤ 3000; *k<sub>i</sub>* = 0 + với mọi *i*; +* 30% số lượng test còn lại thỏa mãn điều kiện: *m* ≤ 3000. + +#### Ví dụ + +| VIRUS.INP | VIRUS.OUT | +| ------------------------- | :-------: | +| 2<br>zabaaxy<br>0<br>1 | 1<br>2 | +| 2<br>zcaabcaaaa<br>0<br>1 | 2<br>4 | + +##### Giải thích + +Trong ví dụ thứ hai, đoạn dài nhất có khả năng bị virus sao chép mức 0 là `aa` +có độ dài 2, đoạn dài nhất có khả năng bị virus sao chép mức 1 là `caab` có độ +dài 4. diff --git a/2ndary/12/QG-2017/virus.c b/2ndary/12/QG-2017/virus.c new file mode 100644 index 0000000..add408c --- /dev/null +++ b/2ndary/12/QG-2017/virus.c @@ -0,0 +1,94 @@ +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +char T[3001], **mem; + +char difflim(char lim, short len, short beg) +{ + 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 ((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, *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); + m = strlen(T); + + for (i = 97; i < 123; i++) { + lenpos = 0; + for (j = 0; j < m; j++) + if (T[j] == i) + pos[lenpos++] = j; + + if (lenpos < 2) + continue; + + for (j = 0; j < lenpos - 1; j++) + for (k = lenpos - 1; k > j; k--) { + len = pos[k] - pos[j]; + if (len <= res[0]) + break; + if (m - pos[k] < len) + continue; + if (!strncmp(T + pos[j], T + pos[k], len)) { + res[0] = len; + break; + } + } + } + + 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 (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; + } + + 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; +} |