From 91b5248c8b951d82f3c9a2deb6ac928cce553497 Mon Sep 17 00:00:00 2001 From: Raphael McSinyx Date: Tue, 27 Jun 2017 12:10:09 +0700 Subject: Add hsg/12/QG-2017/virus.c --- 12/QG-2017/README.md | 78 +++++++++++++++++++++++++++++++++++++++++++++ 12/QG-2017/virus.c | 71 +++++++++++++++++++++++++++++++++++++++++ 12/QG-2017/virus_randinp.py | 9 ++++++ 3 files changed, 158 insertions(+) create mode 100644 12/QG-2017/README.md create mode 100644 12/QG-2017/virus.c create mode 100755 12/QG-2017/virus_randinp.py (limited to '12/QG-2017') diff --git a/12/QG-2017/README.md b/12/QG-2017/README.md new file mode 100644 index 0000000..9d64c57 --- /dev/null +++ b/12/QG-2017/README.md @@ -0,0 +1,78 @@ +# 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 + +### 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*1, *k*2, +…, *kn*. Với mỗi giá trị ki, 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 *ki* (*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 + *ki* (*ki* ≤ 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 *ki* , *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; *ki* = 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
zabaaxy
0
1 | 1
2 | +| 2
zcaabcaaaa
0
1 | 2
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 new file mode 100644 index 0000000..d4a56ba --- /dev/null +++ b/12/QG-2017/virus.c @@ -0,0 +1,71 @@ +#include +#include + +char difflim(char lim, char *s, short len) +{ + char i, count = 0; + + for (i = 0; i < len; i++) + if (s[i] != s[len + i] && ++count > lim) + return 0; + return 1; +} + +int main() { + FILE *f = fopen("VIRUS.INP", "r"); + char i, n, level, T[3001], levels[10]; + short m, j, k, len, lenpos, pos[3000], res[11] = {}; + + fscanf(f, "%hhd\n%s\n", &n, T); + 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; + } + } + } + + 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]; + + 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; + } + } + fprintf(f, "%hd\n", res[level]); + } + fclose(f); + return 0; +} diff --git a/12/QG-2017/virus_randinp.py b/12/QG-2017/virus_randinp.py new file mode 100755 index 0000000..566e452 --- /dev/null +++ b/12/QG-2017/virus_randinp.py @@ -0,0 +1,9 @@ +#!/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') -- cgit 1.4.1