diff options
Diffstat (limited to 'tht/C/TP-2018')
| -rw-r--r-- | tht/C/TP-2018/README.md | 170 | ||||
| -rw-r--r-- | tht/C/TP-2018/func.scm | 35 | ||||
| -rw-r--r-- | tht/C/TP-2018/guess.scm | 8 | ||||
| -rw-r--r-- | tht/C/TP-2018/mab.cpp | 77 | ||||
| -rw-r--r-- | tht/C/TP-2018/mab.scm | 110 |
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)))))) |