Revise a few competive exersises

7 files changed, 129 insertions, 5 deletions

diff --git a/.gitmodules b/.gitmodules
new file mode 100644
index 0000000..019e9dc
--- /dev/null
+++ b/.gitmodules
@@ -0,0 +1,6 @@
+[submodule "paip"]
+	path = paip/book
+	url = https://github.com/norvig/paip-lisp.git
+[submodule "paip/book"]
+	path = paip/book
+	url = https://github.com/norvig/paip-lisp
diff --git a/12/QG-2007/README.md b/12/QG-2007/README.md
index a58798f..d32a8be 100644
--- a/12/QG-2007/README.md
+++ b/12/QG-2007/README.md
@@ -40,4 +40,4 @@ có dãy con nào thỏa mãn điều kiện đặt ra thì d = 0).
 Các dãy con không giảm của dãy số đã cho mà các phần tử của nó đều thuộc dãy
 (u<sub>k</sub>) là: 6, 6, 15 và 3, 21 (vì u<sub>2</sub> = 3, u<sub>3</sub> = 6,
 u<sub>5</sub> = 15, u<sub>6</sub> = 21). Dãy cần tìm là 6, 6, 15 có độ dài là
-3. 
+3.
diff --git a/12/QG-2014/ballgame.lisp b/12/QG-2014/ballgame.lisp
new file mode 100644
index 0000000..765d85c
--- /dev/null
+++ b/12/QG-2014/ballgame.lisp
@@ -0,0 +1,49 @@
+(defun normalize-line (line)
+  (if (or (and (= (first line) 0) (< (second line) 0))
+          (< (first line) 0))
+      (mapcar #'- line)
+      line))
+
+(defun make-line (x1 x2 y1 y2)
+  (let* ((a (- y2 y1))
+         (b (- x1 x2))
+         (c (+ (* a x1) (* b y1)))
+         (g (gcd a b c)))
+    (normalize-line (mapcar (lambda (x) (/ x g)) (list a b c)))))
+
+(defun extract-result (first-pair second-pair)
+  (let ((triple (union first-pair second-pair)))
+    (if (= (length triple) 3)
+        (format nil "~a~a~a" (first triple) (second triple) (third triple))
+        (format nil "~{~a ~}~a" first-pair (first second-pair)))))
+
+(with-open-file (instream "BALLGAME.INP")
+  (let ((n (read instream)))
+    (labels ((read-blues (m result)
+               (if (<= m n)
+                   (let* ((x (read instream)) (y (read instream)))
+                     (read-blues (1+ m) (cons (list m x y) result)))
+                   result)))
+      (let ((blues (read-blues 1 '()))
+            (lines (make-hash-table :test 'equal)))
+        (labels ((process-reds (m)
+                   (if (<= m n)
+                       (let* ((x (read instream))
+                              (y (read instream))
+                              (result
+                               (dolist (blue blues nil)
+                                 (let* ((line (make-line x (second blue)
+                                                         y (third blue)))
+                                        (this-pair (list (first blue) (+ m n)))
+                                        (that-pair (gethash line lines)))
+                                   (if (null that-pair)
+                                       (setf (gethash line lines) this-pair)
+                                       (return (extract-result this-pair
+                                                               that-pair)))))))
+                         (cond (result)
+                               (t (process-reds (1+ m)))))
+                       "-1")))
+          (with-open-file (outstream "BALLGAME.OUT" :direction :output
+                                     :if-exists :supersede)
+            (princ (process-reds 1) outstream)
+            (fresh-line outstream)))))))
diff --git a/12/QG-2014/minroad.c b/12/QG-2014/minroad.c
new file mode 100644
index 0000000..d4bc129
--- /dev/null
+++ b/12/QG-2014/minroad.c
@@ -0,0 +1,69 @@
+#include <stdlib.h>
+#include <stdio.h>
+
+struct trees {
+	long d, a, b;
+};
+
+int cmp(const void *x, const void *y)
+{
+	long d = ((struct trees *) x)->d - ((struct trees *) y)->d;
+	if (d < 0)
+		return -1;
+	else if (d > 0)
+		return 1;
+	else
+		return 0;
+}
+
+int main()
+{
+	FILE *f = fopen("MINROAD.INP", "r");
+	long n, a, b;
+	fscanf(f, "%ld %ld %ld\n", &n, &a, &b);
+
+	struct trees *t = (struct trees *) malloc(n * sizeof(struct trees));
+	long k;
+	for (long i = 0; i < n; i++) {
+		fscanf(f, "%ld %ld\n", &t[i].d, &k);
+		if (k == 1) {
+			t[i].a = 1;
+			t[i].b = 0;
+		} else {
+			t[i].a = 0;
+			t[i].b = 1;
+		}
+	}
+	fclose(f);
+
+	qsort(t, n, sizeof(struct trees), cmp);
+	for (long i = 1; i < n; i++) {
+		t[i].a += t[i - 1].a;
+		t[i].b += t[i - 1].b;
+	}
+
+	struct trees *enough = t;
+	for (k = n; k > 0 && (enough->a < a || enough->b < b); k--)
+		enough++;
+
+	long d0 = -1, d1, maxa, maxb;
+	for (; k--; enough++) {
+		maxa = enough->a - a;
+		maxb = enough->b - b;
+		while (t->a <= maxa && t->b <= maxb) {
+			t++;
+			n--;
+		}
+
+		d1 = d0;
+		d0 = enough->d - t->d;
+		if (d1 != -1 && d1 < d0)
+			d0 = d1;
+	}
+
+	f = fopen("MINROAD.OUT", "w");
+	fprintf(f, "%ld\n", d0);
+	fclose(f);
+
+	return 0;
+}
diff --git a/THT/C/TP-2018/README.md b/THT/C/TP-2018/README.md
index 66b7b41..f13f31d 100644
--- a/THT/C/TP-2018/README.md
+++ b/THT/C/TP-2018/README.md
@@ -166,5 +166,5 @@ dạng sau:
 ### Ví dụ
 
 |                 LAMPS.INP                  | LAMPS.OUT |
-|                                            | :-------: |
+| ------------------------------------------ | :-------: |
 | 4 1<br>1 2<br>2 3<br>3 4<br>1 4<br>0 1 0 0 |    1 4    |
diff --git a/others/coastline/README.md b/others/coastline/README.md
index 5582125..b58a06f 100644
--- a/others/coastline/README.md
+++ b/others/coastline/README.md
@@ -27,8 +27,8 @@ In ra số lớn nhất Ming có thể tạo ra, hoặc -1 nếu không thể s�
 
 |  Sample Input  | Sample Output |
 | -------------- | ------------- |
-| 9<br>112233456 | 645231312     |
-| 2<br>12        | -1            |
+| 9<br>112233456 |   645231312   |
+| 2<br>12        |   -1          |
 
 ## GRID
 
@@ -69,7 +69,7 @@ Ví dụ: a = 11, b = 48, k = 7.
 
 Ta có: trong chuỗi các số nguyên {11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21,
 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35 36; 37, 38, 39, 40, 41,
-42, 43, 44, 45, 46, 47, 48} sẽ có các bộ với 7 số sau (11, 12, 13, 14,15, 16,
+42, 43, 44, 45, 46, 47, 48} sẽ có các bộ với 7 số sau (11, 12, 13, 14, 15, 16,
 17), (12, 13, 14, 15, 16, 17, 18), (13, 14, 15, 16, 17, 18, 19), ..., (42, 43,
 44, 45, 46, 47, 48).
 
diff --git a/paip/book b/paip/book
new file mode 160000
+Subproject 40bcebdaeccf7ce5c4fa13ef20ffe0cd10a66df