From 3a3843673d8401f224901ad170aaf2ab8c3b1f46 Mon Sep 17 00:00:00 2001
From: Nguyễn Gia Phong <vn.mcsinyx@gmail.com>
Date: Fri, 20 Jul 2018 15:04:12 +0700
Subject: Revise a few competive exersises

---
 12/QG-2007/README.md     |  2 +-
 12/QG-2014/ballgame.lisp | 49 ++++++++++++++++++++++++++++++++++
 12/QG-2014/minroad.c     | 69 ++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 119 insertions(+), 1 deletion(-)
 create mode 100644 12/QG-2014/ballgame.lisp
 create mode 100644 12/QG-2014/minroad.c

(limited to '12')

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;
+}
-- 
cgit 1.4.1