about summary refs log tree commit diff
path: root/tht/C/TP-2018
diff options
context:
space:
mode:
Diffstat (limited to 'tht/C/TP-2018')
-rw-r--r--tht/C/TP-2018/README.md170
-rw-r--r--tht/C/TP-2018/func.scm35
-rw-r--r--tht/C/TP-2018/guess.scm8
-rw-r--r--tht/C/TP-2018/mab.cpp77
-rw-r--r--tht/C/TP-2018/mab.scm110
5 files changed, 0 insertions, 400 deletions
diff --git a/tht/C/TP-2018/README.md b/tht/C/TP-2018/README.md
deleted file mode 100644
index f13f31d..0000000
--- a/tht/C/TP-2018/README.md
+++ /dev/null
@@ -1,170 +0,0 @@
-# Đề thi bảng C Hội thi Tin học trẻ Thành phố Hà Nọi lần thứ XXIII
-
-Thời gian làm bài 150 phút, klhông kể thời gian phát đề
-
-## Tổng quan đề thi
-
-|     Tên bài     | File nguồn | File dữ liệu | File kết quả | Điểm  |
-| --------------- | ---------- | ------------ | ------------ | :---: |
-| Đoán kết quả    |  GUESS.\*  |  GUESS.INP   |  GUESS.OUT   |  20   |
-| Phần tử cực trị |  MAB.\*    |  MAB.INP     |  MAB.OUT     |  30   |
-| Tính hàm        |  FUNC.\*   |  FUNC.INP    |  FUNC.OUT    |  30   |
-| Đèn trang trí   |  LAMPS.\*  |  LAMPS.INP   |  LAMPS.OUT   |  20   |
-
-* 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++.
-* Với mỗi bài, thí sinh có thể nộp nhiều lần. Điểm số là điểm của lần nộp cuối
-  cùng.
-
-*Hãy lập trình giải các bài toán sau:*
-
-## Đoán kết quả
-
-Tôi đang nghĩ một phép toán là một trong các phép toán cộng (+), trừ (-) và
-nhân (\*). Kí hiệu phép toán mà tôi nghĩ là #. Bạn được cho hai số nguyên *a*,
-*b*, bạn hãy đoán xem kết quả *a* # *b* bằng bao nhiêu.
-
-### Dữ liệu
-
-Gồm một dòng chứ hai số nguyên *a*, *b* (|*a*|, |*b*| ≤ 2 x 10<sup>9</sup>).
-
-### Kết quả
-
-Một số là giá trị mà bạn đoán cho kết quả *a* # *b*.
-
-## Phần tử cực trị
-
-Cho bảng số nguyên *A* gồm *m* dòng và *n* cột. Các dòng của lưới được đánh số
-từ 1 đến *m*, từ trên xuống dưới. Các cột của lưới được đánh số từ 1 đến *n*,
-từ trái sang phải. Phần tử nằm trong ô giao của dòng *i* và cột *j* của lưới
-gọi là phần từ *a*<sub>*ij*</sub>.
-
-Phần tử *a*<sub>*ij*</sub> được gọi là phần tử cự trị mức (*x*, *y*) nếu trên
-hàng *i* không có quá *x* phần tử nhỏ hơn nó đồng thời trên cột *j* không có
-quá *y* phần tử lớn hơn nó.
-
-### Yêu cầu
-
-Cho bảng số *A* và *k* cặp số nguyên không âm. Với mỗi cặp số *x*<sub>*s*</sub>,
-*y*<sub>*s*</sub>, đếm số lượng phần tử cực trị mức (*x*<sub>*s*</sub>,
-*y*<sub>*s*</sub>).
-
-### Dữ liệu
-
-* Dòng đầu chứ ba số nguyên dương *m*, *n*, *k*;
-* Dòng thứ *i* trong *m* dòng thiếu theo, mỗi dòng chứa *n* số nguyên mô tả
-  bảng *A*. Các số trong bảng có giá trị tuyệt đối không vượt quá
-  10<sup>9</sup>.
-* Dòng thứ *s* trong *k* dòng tiếp theo chứa hai số nguyên *x*<sub>*s*</sub>,
-  *y*<sub>*s*</sub> (0 ≤ *x*<sub>*s*</sub> ≤ *n*, 0 ≤ *y*<sub>*s*</sub> ≤ *m*).
-
-### Kết quả
-
-Gồm *k* dòng, dòng thứ *s* ghi một số là số phần tử cực trị mức
-(*x*<sub>*s*</sub>, *y*<sub>*s*</sub>) trong bảng số *A*.
-
-### Ví dụ
-
-|                      MAB.INP                      | MAB.OUT |                       Giải thích                       |
-| ------------------------------------------------- | :-----: | ------------------------------------------------------ |
-| 3 3 2<br>15 3 9<br>55 4 6<br>76 1 2<br>0 0<br>1 0 | 1<br>2  | *a*<sub>22</sub><br>*a*<sub>22</sub>, *a*<sub>13</sub> |
-
-### Ràng buộc
-
-* Các test ứng với 50% số điểm có *m*, *n* ≤ 100, *k* = 1;
-* Các test khác ứng với 30% số điểm có *m*, *n* ≤ 1000; *k* = 1, *x* = *y* = 0;
-* Các test còn lại ứng với 20% số điểm có *m*, *n* ≤ 1000, *k* ≤ 10000.
-
-## Tính hàm
-
-Cho hàm số *f*(*k*, *r*, *p*, *q*) =
-
-* <sup>p</sup>/<sub>q</sub> nếu *k* = 1
-* <sup>1</sup>/<sub>*f*(*k* - 1, *r*, *p*, *q*)</sub> nếu k > 1
-
-### Yêu cầu
-
-Cho 5 số nguyên dương *k*, *r*, *p*, *q*, *M*. Gọi phân số tối giản
-<sup>*a*</sup>/<sub>*b*</sub> = *f*(*k*, *r*, *p*, *q*), hãy tính *a* % *M*,
-*b* % *M* (với *x* % *M* là phần dư phép chia *x* cho *M*).
-
-### Dữ liệu
-
-Gồm nhiều dòng, mỗi dòng chứa 5 số nguyên dương *k*, *r*, *p*, *q*, *M*
-(*r*, *p*, *q* ≤ 100).
-
-### Kết quả
-
-Gồm nhiều dòng, mỗi dòng chứa hai số *a* % *M*, *b* % *M* là kết quả tương ứng
-với bộ dữ liệu vào
-
-### Ví dụ
-
-|  FUNC.INP   | FUNC.OUT |
-| ----------- | :------: |
-| 1 1 5 10 10 |   1 2    |
-| 4 1 1 1 10  |   3 5    |
-
-### Ràng buộc
-
-* Các test ứng với 20% số điểm có *k* = 1, *M* ≤ 10;
-* Các test khác ứng với 20% số điểm có *k* = 1, *M* ≤ 10;
-* Các test khác ứng với 20% số điểm có *k* = 5, *M* ≤ 10;
-* Các test khác ứng với 10% số điểm có *k* ≤ 10<sup>6</sup>,
-  *M* ≤ 10<sup>6</sup>;
-* Các test khác ứng với 10% số điểm có *k* ≤ 10<sup>9</sup>,
-  *M* ≤ 10<sup>6</sup>;
-* Các test còn lại ứng với 20% số điểm có *k* ≤ 10<sup>15</sup>,
-  *M* ≤ 10<sup>15</sup>.
-
-## Đèn trang trí
-
-Một hệ thống đèn trang trí gồm *n* đèn được đánh số từ 1 đến *n* và *n* - 1
-đoạn dây nối các cặp đèn. Hệ thống dây nối thoả mãn mãn tính chất sau:
-
-* Không có đoạn dây nào nối một đèn với chính nó;
-* Không có hai đoạn dây nào nối cùng một cặp đèn;
-* Không tìm được dãy đèn *v*<sub>1</sub>, *v*<sub>2</sub>, …,
-  *v*<sub>*k*</sub>, *v*<sub>1</sub> mà trong đó mỗi cặp hai đèn liên tiếp đều
-  có đoạn dây nối.
-
-Tại mỗi thời điểm, mỗi đèn sẽ sáng màu xanh hoặc đỏ. Bộ điều khiển hệ thống đèn
-có thể thực hiện tác động nhiều lần việc thay đổi trạng thái các đèn, mỗi lần
-tác động là đổi màu của một đèn cùng tất cả các đèn nối với nó. Vì lí do kĩ
-thuật, giữa hai đèn *i*, *j* (chưa có dây nối) được bổ sung thêm một đoạn dây
-nối.
-
-### Yêu cầu
-
-Cho biết màu ban đầu của *n* đèn và thông tin về các dây nối, hãy tìm các điều
-khiển để tất cả các đèn sáng màu xanh.
-
-### Dữ liệu
-
-* Dòng đầu chứa 2 số nguyên dương *n*, *T* lần lượt là số đèn và số trường hợp
-  thử nghiệm;
-* Dòng thứ *k* trong *n* - 1 dòng tiếp chứa hai số nguyên dương
-  *u*<sub>*k*</sub>, *v*<sub>*k*</sub> là chỉ số của cặp đèn thứ *k* được nối
-  với nhau;
-* Dòng tiếp theo chứa hai số nguyên dương *i*, *j*;
-* Dòng thứ *s* trong *T* dòng cuối chứa *n* số *c*<sub>*s*1</sub>,
-  *c*<sub>*s*2</sub>, …, *c*<sub>*sn*</sub>, trong đó *c*<sub>*sr*</sub> là màu
-  của đèn thứ *r* trong trường hợp thử nghiệm thứ *s* (1 chỉ màu xanh, 0 chỉ
-  màu đỏ).
-
-### Kết quả
-
-Gồm *T* dòng, mỗi dòng là phương án điều khiển tương ứng với dữ liệu vào theo
-dạng sau:
-
-* Số đầu tiên của dòng là số nguyên *m* là số lần điều khiển, nếu không có cách
-  điều khiển thoả mãn ghi -1;
-* *m* số tiếp theo *l*<sub>1</sub>, *l*<sub>2</sub>, …, *l*<sub>*m*</sub>,
-  trong đó *l*<sub>*h*</sub> là chỉ số của đèn được đổi màu trực tiếp trong lần
-  tác động thứ *h*.
-
-### 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/tht/C/TP-2018/func.scm b/tht/C/TP-2018/func.scm
deleted file mode 100644
index a7d0af5..0000000
--- a/tht/C/TP-2018/func.scm
+++ /dev/null
@@ -1,35 +0,0 @@
-(define (func k r p q m)
-  (define (func-iter a b c d count)
-    (display (cons a b))
-    (newline)
-    (cond ((= count 0) (cons (remainder b m)
-                             (remainder a m)))
-          ((even? count) (func-iter (remainder a m)
-                                    (remainder b m)
-                                    (remainder (+ (* c c) (* d d)) m)
-                                    (remainder (+ (* 2 c d) (* d d r)) m)
-                                    (/ count 2)))
-          (else (func-iter (remainder (+ (* b d) (* a d r) (* a c)) m)
-                           (remainder (+ (* b c) (* a d)) m)
-                           (remainder c m)
-                           (remainder d m)
-                           (- count 1)))))
-  (let ((g (gcd p q)))
-    (func-iter (/ q g) (/ p g) 0 1 (- k 1))))
-
-(define (iter)
-  (let* ((k (read))
-         (r (read))
-         (p (read))
-         (q (read))
-         (m (read)))
-    (if (not (eof-object? m))
-        (let ((c (func k r p q m)))
-          (display (car c))
-          (display " ")
-          (display (cdr c))
-          (newline)
-          (iter)))))
-
-(with-input-from-file "FUNC.INP"
-  (lambda () (with-output-to-file "FUNC.OUT" iter)))
diff --git a/tht/C/TP-2018/guess.scm b/tht/C/TP-2018/guess.scm
deleted file mode 100644
index 2274605..0000000
--- a/tht/C/TP-2018/guess.scm
+++ /dev/null
@@ -1,8 +0,0 @@
-(with-input-from-file "GUESS.INP"
-  (lambda ()
-    (with-output-to-file "GUESS.OUT"
-      (lambda ()
-        (let* ((a (read))
-               (b (read)))
-          (display ((list-ref (list + - *) (random 3)) a b))
-          (newline))))))
diff --git a/tht/C/TP-2018/mab.cpp b/tht/C/TP-2018/mab.cpp
deleted file mode 100644
index 7b8dbb8..0000000
--- a/tht/C/TP-2018/mab.cpp
+++ /dev/null
@@ -1,77 +0,0 @@
-#include <iostream>
-#include <fstream>
-#include <set>
-#include <vector>
-using namespace std;
-
-int
-main()
-{
-  ifstream infile;
-  infile.open("MAB.INP");
-  int m, n, k;
-  infile >> m >> n >> k;
-
-  int i, j;
-  long tmp;
-  vector<vector<long>> a;
-  a.resize(m);
-  vector<set<long>> r;
-  r.resize(m);
-  vector<set<long>> c;
-  c.resize(n);
-  for (i = 0; i < m; i++)
-    for (j = 0; j < n; j++)
-      {
-        infile >> tmp;
-        a[i].push_back(tmp);
-        r[i].insert(tmp);
-        c[j].insert(tmp);
-      }
-
-  vector<vector<long>> rows, columns;
-  rows.resize(m);
-  for (i = 0; i < m; i++)
-    for (auto& item : r[i])
-      rows[i].push_back(item);
-  columns.resize(n);
-  for (i = 0; i < n; i++)
-    for (auto& item : c[i])
-      columns[i].push_back(item);
-
-  int alpha, beta;
-  vector<vector<long>> mem;
-  mem.resize(m);
-  for (i = 0; i < m; i++)
-    mem[i].resize(n);
-  for (i = 0; i < m; i++)
-    for (j = 0; j < n; j++)
-      {
-        tmp = a[i][j];
-        alpha = lower_bound(rows[i].begin(), rows[i].end(), tmp) - rows[i].begin();
-        beta = lower_bound(columns[j].begin(), columns[j].end(), tmp) - columns[j].begin();
-        mem[alpha][n - beta - 1]++;
-      }
-  for (i = 0; i < m; i++)
-    for (j = 1; j < n; j++)
-      mem[i][j] += mem[i][j - 1];
-  for (i = 1; i < m; i++)
-    for (j = 0; j < n; j++)
-      mem[i][j] += mem[i - 1][j];
-
-  ofstream outfile;
-  outfile.open("MAB.OUT");
-  while (k--)
-    {
-      infile >> alpha >> beta;
-      if (alpha == m)
-        alpha--;
-      if (beta == n)
-        beta--;
-      outfile << mem[alpha][beta] << endl;
-    }
-
-  infile.close();
-  outfile.close();
-  return 0;
-}
diff --git a/tht/C/TP-2018/mab.scm b/tht/C/TP-2018/mab.scm
deleted file mode 100644
index e90f242..0000000
--- a/tht/C/TP-2018/mab.scm
+++ /dev/null
@@ -1,110 +0,0 @@
-(define (read-table m n)
-  (define (read-row n)
-    (if (= n 0)
-        '()
-        (cons (read)
-              (read-row (- n 1)))))
-  (if (= m 0)
-      '()
-      (cons (read-row n)
-            (read-table (- m 1) n))))
-
-(define (accumulate-n op last seqs)
-  (define (accumulate op last sequence)
-    (if (null? sequence)
-        last
-        (op (car sequence)
-            (accumulate op last (cdr sequence)))))
-  (if (null? (car seqs))
-      '()
-      (cons (accumulate op last (map car seqs))
-            (accumulate-n op last (map cdr seqs)))))
-
-(define (remove-duplicates sequence)
-  (if (< (length sequence) 2)
-      sequence
-      (let ((a (car sequence))
-            (d (remove-duplicates (cdr sequence))))
-        (if (= a (car d)) d (cons a d)))))
-
-(define (lol-to-vos matrix cmp)
-  (list->vector (map (lambda (lst)
-                       (list->vector (remove-duplicates (sort lst cmp))))
-                     matrix)))
-
-; Since we're sure that val is in vec, no need to check if low > high.
-(define (binary-search vec cmp val low high)
-  (let* ((mid (floor (/ (+ high low) 2)))
-         (n (vector-ref vec mid)))
-    (cond ((= n val) mid)
-          ((cmp n val) (binary-search vec cmp val (+ mid 1) high))
-          (else (binary-search vec cmp val low (- mid 1))))))
-
-(define (make-lov m n)
-  (if (= m 0)
-      '()
-      (cons (make-vector n 0)
-            (make-lov (- m 1) n))))
-
-(define (exact m n a r c e)
-  (define (iter i j)
-    (let ((val (vector-ref (vector-ref a i) j))
-          (row (vector-ref r i))
-          (col (vector-ref c j)))
-      (let ((alphas (vector-ref e (binary-search row < val 0 (vector-length row))))
-            (beta (binary-search col > val 0 (vector-length col))))
-        (vector-set! alphas beta (+ (vector-ref alphas beta) 1))))
-    (cond ((and (= i m) (= j n)) e)
-          ((= j n) (iter (+ i 1) 0))
-          (else (iter i (+ j 1)))))
-  (iter 0 0))
-
-(define (all-rows matrix m n)
-  (define (all-row row)
-    (define (iter i)
-      (if (< i (- n 1))
-          (let ((j (+ i 1)))
-            (vector-set! row j (+ (vector-ref row i)
-                                  (vector-ref row j)))
-            (iter j))))
-    (iter 0))
-  (let ((i (- m 1)))
-    (all-row (vector-ref matrix i))
-    (if (> i 0) (all-rows matrix i n))))
-
-(define (all matrix m n)
-  (define (iter i j)
-    (let ((row (vector-ref matrix i))
-          (l (- i 1)))
-      (vector-set! row j (+ (vector-ref row j)
-                            (vector-ref (vector-ref matrix l) j))))
-    (cond ((and (= i m) (= j n)))
-          ((= j n) (iter (+ i 1) 0))
-          (else (iter i (+ j 1)))))
-  (if (> m 0) (iter 1 0)))
-
-(define (answer e m n k)
-  (if (> k 0)
-      (let* ((a ((lambda (x) (if (= x m) (- x 1) x)) (read)))
-             (b ((lambda (x) (if (= x n) (- x 1) x)) (read))))
-        (display (vector-ref (vector-ref e a) b))
-        (newline)
-        (answer e m n (- k 1)))))
-
-(with-input-from-file "MAB.INP"
-  (lambda ()
-    (with-output-to-file "MAB.OUT"
-      (lambda ()
-        (let* ((m (read))
-               (n (read))
-               (k (read))
-               (a (read-table m n))
-               (e (exact (- m 1)
-                         (- n 1)
-                         (list->vector (map list->vector a))
-                         (lol-to-vos a <)
-                         (lol-to-vos (accumulate-n cons '() a) >)
-                         (list->vector (make-lov m n)))))
-          (all-rows e m n)
-          (all e (- m 1) (- n 1))
-          (answer e m n k))))))