Add hsg/12/QG-2017/virus.c

3 files changed, 158 insertions, 0 deletions

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*<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
new file mode 100644
index 0000000..d4a56ba
--- /dev/null
+++ b/12/QG-2017/virus.c
@@ -0,0 +1,71 @@
+#include <stdio.h>
+#include <string.h>
+
+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')