diff options
Diffstat (limited to '12/QG-2017')
| -rw-r--r-- | 12/QG-2017/README.md | 80 | ||||
| -rw-r--r-- | 12/QG-2017/virus.c | 94 |
2 files changed, 0 insertions, 174 deletions
diff --git a/12/QG-2017/README.md b/12/QG-2017/README.md deleted file mode 100644 index 9b79939..0000000 --- a/12/QG-2017/README.md +++ /dev/null @@ -1,80 +0,0 @@ -# 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/12/QG-2017/virus.c b/12/QG-2017/virus.c deleted file mode 100644 index add408c..0000000 --- a/12/QG-2017/virus.c +++ /dev/null @@ -1,94 +0,0 @@ -#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; -} |