From 3a3843673d8401f224901ad170aaf2ab8c3b1f46 Mon Sep 17 00:00:00 2001 From: Nguyễn Gia Phong Date: Fri, 20 Jul 2018 15:04:12 +0700 Subject: Revise a few competive exersises --- .gitmodules | 6 ++++ 12/QG-2007/README.md | 2 +- 12/QG-2014/ballgame.lisp | 49 ++++++++++++++++++++++++++++++++ 12/QG-2014/minroad.c | 69 ++++++++++++++++++++++++++++++++++++++++++++++ THT/C/TP-2018/README.md | 2 +- others/coastline/README.md | 6 ++-- paip/book | 1 + 7 files changed, 130 insertions(+), 5 deletions(-) create mode 100644 .gitmodules create mode 100644 12/QG-2014/ballgame.lisp create mode 100644 12/QG-2014/minroad.c create mode 160000 paip/book 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 (uk) là: 6, 6, 15 và 3, 21 (vì u2 = 3, u3 = 6, u5 = 15, u6 = 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 +#include + +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
1 2
2 3
3 4
1 4
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
112233456 | 645231312 | -| 2
12 | -1 | +| 9
112233456 | 645231312 | +| 2
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 index 0000000..40bcebd --- /dev/null +++ b/paip/book @@ -0,0 +1 @@ +Subproject commit 40bcebdaeccf7ce5c4fa13ef20ffe0cd10a66dff -- cgit 1.4.1