From 18419b2b07ffbc1f390c7309ca78cfc7820411eb Mon Sep 17 00:00:00 2001 From: Nguyễn Gia Phong Date: Wed, 23 May 2018 21:46:57 +0700 Subject: Thêm đề bảng C Tin học trẻ Hà Nội XXIII MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- THT/C/TP-2018/README.md | 170 ++++++++++++++++++++++++++++++++++++++++++++++++ THT/C/TP-2018/func.scm | 35 ++++++++++ THT/C/TP-2018/guess.scm | 8 +++ THT/C/TP-2018/mab.cpp | 77 ++++++++++++++++++++++ THT/C/TP-2018/mab.scm | 110 +++++++++++++++++++++++++++++++ 5 files changed, 400 insertions(+) create mode 100644 THT/C/TP-2018/README.md create mode 100644 THT/C/TP-2018/func.scm create mode 100644 THT/C/TP-2018/guess.scm create mode 100644 THT/C/TP-2018/mab.cpp create mode 100644 THT/C/TP-2018/mab.scm diff --git a/THT/C/TP-2018/README.md b/THT/C/TP-2018/README.md new file mode 100644 index 0000000..66b7b41 --- /dev/null +++ b/THT/C/TP-2018/README.md @@ -0,0 +1,170 @@ +# Đề 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 109). + +### 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**ij*. + +Phần tử *a**ij* đượ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**s*, +*y**s*, đếm số lượng phần tử cực trị mức (*x**s*, +*y**s*). + +### 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á + 109. +* Dòng thứ *s* trong *k* dòng tiếp theo chứa hai số nguyên *x**s*, + *y**s* (0 ≤ *x**s* ≤ *n*, 0 ≤ *y**s* ≤ *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**s*, *y**s*) trong bảng số *A*. + +### Ví dụ + +| MAB.INP | MAB.OUT | Giải thích | +| ------------------------------------------------- | :-----: | ------------------------------------------------------ | +| 3 3 2
15 3 9
55 4 6
76 1 2
0 0
1 0 | 1
2 | *a*22
*a*22, *a*13 | + +### 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*) = + +* p/q nếu *k* = 1 +* 1/*f*(*k* - 1, *r*, *p*, *q*) 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 +*a*/*b* = *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* ≤ 106, + *M* ≤ 106; +* Các test khác ứng với 10% số điểm có *k* ≤ 109, + *M* ≤ 106; +* Các test còn lại ứng với 20% số điểm có *k* ≤ 1015, + *M* ≤ 1015. + +## Đè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*1, *v*2, …, + *v**k*, *v*1 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**k*, *v**k* 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**s*1, + *c**s*2, …, *c**sn*, trong đó *c**sr* 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*1, *l*2, …, *l**m*, + trong đó *l**h* 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
1 2
2 3
3 4
1 4
0 1 0 0 | 1 4 | diff --git a/THT/C/TP-2018/func.scm b/THT/C/TP-2018/func.scm new file mode 100644 index 0000000..a7d0af5 --- /dev/null +++ b/THT/C/TP-2018/func.scm @@ -0,0 +1,35 @@ +(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 new file mode 100644 index 0000000..2274605 --- /dev/null +++ b/THT/C/TP-2018/guess.scm @@ -0,0 +1,8 @@ +(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 new file mode 100644 index 0000000..7b8dbb8 --- /dev/null +++ b/THT/C/TP-2018/mab.cpp @@ -0,0 +1,77 @@ +#include +#include +#include +#include +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> a; + a.resize(m); + vector> r; + r.resize(m); + vector> 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> 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> 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 new file mode 100644 index 0000000..e90f242 --- /dev/null +++ b/THT/C/TP-2018/mab.scm @@ -0,0 +1,110 @@ +(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)))))) -- cgit 1.4.1