diff options
author | Nguyễn Gia Phong <mcsinyx@disroot.org> | 2020-06-06 21:33:13 +0700 |
---|---|---|
committer | Nguyễn Gia Phong <mcsinyx@disroot.org> | 2020-06-06 21:33:13 +0700 |
commit | 2f674dc80f0382f1c3178f435714960734dc9d3c (patch) | |
tree | 2abba7e4ec72bd16f58f7375126144d3fd9f4bca /12 | |
parent | b2d80610db6beda38573890ed169815e495bc663 (diff) | |
download | cp-2f674dc80f0382f1c3178f435714960734dc9d3c.tar.gz |
Reorganize stuff from secondary school
Diffstat (limited to '12')
56 files changed, 0 insertions, 2721 deletions
diff --git a/12/Q-VĩnhTường-2006/README.md b/12/Q-VĩnhTường-2006/README.md deleted file mode 100644 index c96c99e..0000000 --- a/12/Q-VĩnhTường-2006/README.md +++ /dev/null @@ -1,67 +0,0 @@ -# ĐỀ THI HSG LỚP 12 HUYỆN VĨNH TƯỜNG NĂM HỌC 2006-2007 - -Môn: Tin học -Thời gian: 150 phút (không kể thời gian giao đề). - -## Câu 1 (5 điểm) - -Nhập vào một số nhị phân có `n` chữ số (`n` < 100). Hãy in ra số dư khi chia số -đó cho 3. - -Ví dụ: - -| n | Số nhị phân | Kết quả | -| ---: | --------------: | :-----: | -| 3 | 101 | 2 | -| 8 | 10100111 | 2 | -| 12 | 100000001101 | 0 | -| 14 | 11001111101110 | 1 | -| 6 | 111111 | 0 | -| 15 | 111111111111110 | 0 | - -## Câu 2 (4 điểm) - -Nhập vào số nguyên dương `n`. Hãy in ra số nguyên tố nhỏ nhất lớn hơn `n`. - -Ví dụ: - -| n | Kết quả | -| ---: | ------: | -| 10 | 11 | -| 7 | 11 | -| 44 | 47 | -| 992 | 997 | -| 2332 | 2333 | - -## Câu 3 (8 điểm) - -Nhập vào từ số tự nhiên `n` (`n` < 1000). - -1. Phân tích `n` thành tích các thừa số nguyên tố. -2. Tìm các số tự nhiên nhỏ hơn hoặc bằng `n` mà sau khi làm phép phân tích ở - phần 1 có nhiều nhân tử nhất. - -Ví dụ: - -| n | Kết quả | -| ---: | -------------- | -| 9 | 3 3<br>8 | -| 15 | 3 5<br>8 12 | -| 21 | 3 7<br>16 | -| 70 | 2 5 7<br>64 | -| 150 | 2 3 5 5<br>128 | - -## Câu 4 (3 điểm) - -Nhập vào một mảng gồm `n` (`n` < 20) số nguyên dương. Hãy đếm xem trong mảng có -bao nhiêu số bậc thang. Biết một số được gọi là số bậc thang nếu biểu diễn thập -phân của nó có nhiều hơn một chữ số đồng thời theo chiều từ trái qua phải, chữ -số đứng sau không nhỏ hơn chữ số đứng trước. - -Ví dụ: - -| n | Dãy số | Kết quả | -| :---: | ------------------------ | :-----: | -| 7 | 1 4 7 5 8 9 3 | 0 | -| 5 | 123 102 10023 9 21 | 1 | -| 6 | 115 110 11112 31 14 1109 | 3 | diff --git a/12/Q-VĩnhTường-2006/cau1.c b/12/Q-VĩnhTường-2006/cau1.c deleted file mode 100644 index 173e7c2..0000000 --- a/12/Q-VĩnhTường-2006/cau1.c +++ /dev/null @@ -1,20 +0,0 @@ -#include <stdio.h> -#include <string.h> - -int main() -{ - char b[100], i; - short a = 0; - - scanf("%s", b); - - for (i = strlen(b) - 1; i >= 0; i -= 2) - a += b[i] - 48; - - for (i = strlen(b) - 2; i >= 0; i -= 2) - a += b[i] * 2 - 96; - - printf("%d\n", a % 3); - - return 0; -} diff --git a/12/Q-VĩnhTường-2006/cau2.c b/12/Q-VĩnhTường-2006/cau2.c deleted file mode 100644 index 4ad1c3b..0000000 --- a/12/Q-VĩnhTường-2006/cau2.c +++ /dev/null @@ -1,39 +0,0 @@ -#include <stdio.h> -#include <math.h> - -char prime(unsigned long long m) -{ - unsigned long i; - - for (i = 3; i <= sqrt(m); i += 2) - if (m % i == 0) - return 0; - - return 1; -} - -int main() -{ - unsigned long long n, i; - - scanf("%lld", &n); - - if (n == 1) { - puts("2"); - - return 0; - } - - i = (n % 2) ? n : n - 1; - - while (i <= 18446744073709551615ULL) { - i += 2; - - if (!prime(i)) - continue; - - printf("%lld\n", i); - - return 0; - } -} diff --git a/12/Q-VĩnhTường-2006/cau3.c b/12/Q-VĩnhTường-2006/cau3.c deleted file mode 100644 index 136f154..0000000 --- a/12/Q-VĩnhTường-2006/cau3.c +++ /dev/null @@ -1,40 +0,0 @@ -#include <stdio.h> -#include <math.h> - -const char PRIMES[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31}; - -int main() -{ - char i; - short n, n0; - - scanf("%hd", &n); - - if (n < 2) { - printf("\n%hd\n", n); - - return 0; - } - - n0 = n; - - for (i = 0; i < 11; i++) - while (n0 % PRIMES[i] == 0) { - n0 /= PRIMES[i]; - printf("%hd ", PRIMES[i]); - } - - if (n0 - 1) - printf("%hd\n", n0); - else - putchar(10); - - n0 = pow(2, (int) log2(n) - 1); - - if (n0 * 3 > n) - printf("%hd\n", n0 * 2); - else - printf("%hd %hd\n", n0 * 2, n0 * 3); - - return 0; -} diff --git a/12/Q-VĩnhTường-2006/cau4.c b/12/Q-VĩnhTường-2006/cau4.c deleted file mode 100644 index d971927..0000000 --- a/12/Q-VĩnhTường-2006/cau4.c +++ /dev/null @@ -1,26 +0,0 @@ -#include <stdio.h> -#include <string.h> - -int main() -{ - char n, count = 0, s[21], c, i; - unsigned long long m; - - for (n = 1; n < 20 && scanf("%lld", &m) != EOF; n++) { - if (m < 10) - continue; - - sprintf(s, "%lld", m); - c = s[0]; - - for (i = 1; i < strlen(s) && c; i++) - c = (c > s[i]) ? 0 : s[i]; - - if (c) - count++; - } - - printf("%hhd\n", count); - - return 0; -} diff --git a/12/QG-2007/README.md b/12/QG-2007/README.md deleted file mode 100644 index d32a8be..0000000 --- a/12/QG-2007/README.md +++ /dev/null @@ -1,43 +0,0 @@ -# KÌ THI CHỌN HỌC SINH GIỎI QUỐC GIA THPT NĂM 2007 - -## Dãy con không giảm dài nhất - -Cho dãy số nguyên dương a<sub>1</sub>, a<sub>2</sub>, …, a<sub>n</sub>. - -Dãy số a<sub>i</sub>, a<sub>i+1</sub>, …, a<sub>j</sub> thỏa mãn a<sub>i</sub> -≤ a<sub>i+1</sub> ≤ … ≤ a<sub>j</sub> với 1 ≤ i ≤ j ≤ n được gọi là dãy con -không giảm của dãy số đã cho và khi đó số j - i + 1 được gọi là độ dài của dãy -con này. - -### Yêu cầu - -Hãy tìm dãy con có độ dài lớn nhất trong số 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 số (u<sub>k</sub>) xác định bởi: - -* u<sub>1</sub> = 1; -* u<sub>k</sub> = u<sub>k-1</sub> + k (k ≥ 2). - -### Dữ liệu - -* Dòng đầu tiên chứa một số nguyên dương n (n ≤ 10000); -* Dòng thứ i trong n dòng tiếp theo chứa một số nguyên dương a<sub>i</sub> là - số hạng thứ i của dãy số đã cho (a<sub>i</sub> ≤ 10<sup>8</sup>, i = 1, 2, …, - n). - -### Kết quả - -Số nguyên d là độ dài của dãy con không giảm tìm được (quy ước rằng nếu không -có dãy con nào thỏa mãn điều kiện đặt ra thì d = 0). - -### Ví dụ - -| MAXISEQ.INP | MAXISEQ.OUT | -| ----------------------------------------------- | :---------: | -| 8<br>2<br>2007<br>6<br>6<br>15<br>16<br>3<br>21 | 3 | - -#### Giải thích - -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. diff --git a/12/QG-2007/maxiseq.c b/12/QG-2007/maxiseq.c deleted file mode 100644 index 94c15c8..0000000 --- a/12/QG-2007/maxiseq.c +++ /dev/null @@ -1,36 +0,0 @@ -#include <math.h> -#include <stdio.h> - -char is_in_u(long x) -{ - long y = (long) sqrt(x *= 2); - return y * (y + 1) == x; -} - -int main() -{ - FILE *f = fopen("MAXISEQ.INP", "r"); - short n, i, max = 0, start = -1; - long a, b; - - fscanf(f, "%hd\n", &n); - for (i = 0; i < n; i++) { - b = a; - fscanf(f, "%ld\n", &a); - if (!is_in_u(a) || start >= 0 && b > a) { - start = -1; - continue; - } - if (start < 0) - start = i; - if (i - start >= max) - max = i - start + 1; - } - fclose(f); - - f = fopen("MAXISEQ.OUT", "w"); - fprintf(f, "%hd\n", max); - fclose(f); - - return 0; -} diff --git a/12/QG-2008/README.md b/12/QG-2008/README.md deleted file mode 100644 index 4327b5d..0000000 --- a/12/QG-2008/README.md +++ /dev/null @@ -1,36 +0,0 @@ -# KÌ THI CHỌN HỌC SINH GIỎI QUỐC GIA THPT NĂM 2008 - -## Trò chơi với dãy số - -Hai bạn học sinh trong lúc nhàn rỗi nghĩ ra trò chơi sau đây. Mỗi bạn chọn -trước một dãy số gồm n số nguyên. Giả sử dãy số mà bạn thứ nhất chọn là: -b<sub>1</sub>, b<sub>2</sub>, …, b<sub>n</sub>; còn dãy số mà bạn thứ hai chọn -là: c<sub>1</sub>, c<sub>2</sub>, …, c<sub>n</sub>. Mỗi lượt chơi mỗi bạn đưa -ra một số hạng trong dãy số của mình. Nếu bạn thứ nhất đưa ra số hạng -b<sub>i</sub> (1 ≤ i ≤ n), còn bạn thứ hai đưa ra số hạng c<sub>j</sub> (1 ≤ j -≤ n) thì giá của lượt chơi đó sẽ là |b<sub>i</sub> + c<sub>j</sub>|. - -### Yêu cầu - -Hãy xác định giá nhỏ nhất của một lượt chơi trong số các lượt chơi có thể. - -### Dữ liệu - -* Dòng đầu tiên chứa số nguyên dương n (n ≤ 10000); -* Dòng thứ hai chứa dãy số nguyên b<sub>1</sub>, b<sub>2</sub>, …, - b<sub>n</sub> (|b<sub>i</sub>| ≤ 10<sup>9</sup>, i = 1, 2, …, n); -* Dòng thứ ba chứa dãy số nguyên c<sub>1</sub>, c<sub>2</sub>, …, - c<sub>n</sub> (|c<sub>i</sub>| ≤ 10<sup>9</sup>, i = 1, 2, …, n); -* Hai số liên tiếp trên một dòng được ghi cách nhau bởi dấu cách. - -### Kết quả - -Ghi ra giá nhỏ nhất tìm được. - -### Ví dụ - -| SEQGAME.INP | SEQGAME.OUT | -| ---------------- | :---------: | -| 2<br>1 -2<br>2 3 | 0 | - -*60% số tests ứng với 60% số điểm của bài có 1 ≤ n ≤ 1000.* diff --git a/12/QG-2008/seqgame.cpp b/12/QG-2008/seqgame.cpp deleted file mode 100644 index b1751c7..0000000 --- a/12/QG-2008/seqgame.cpp +++ /dev/null @@ -1,59 +0,0 @@ -#include <iostream> -#include <fstream> -#include <set> - -#define ABS(x) ((x < 0) ? -x : x) - -using namespace std; - -int -main() -{ - ifstream infile; - ofstream outfile; - short n; - long i, c, min = 2e9, a; - set<long> b; - std::set<long>::iterator k; - - infile.open("SEQGAME.INP"); - infile >> n; - for (i = 0; i < n; i++) - { - infile >> c; - b.insert(c); - } - - for (; n--;) - { - infile >> c; - k = b.lower_bound(-c); - if (*k == -c) - { - min = 0; - break; - } - - if (k != b.end()) - { - i = ABS(*k + c); - if (a < min) - min = i; - } - - if (k != b.begin()) - { - k--; - i = ABS(*k + c); - if (a < min) - min = i; - } - } - infile.close(); - - outfile.open("SEQGAME.OUT"); - outfile << min << endl; - outfile.close(); - - return 0; -} diff --git a/12/QG-2014/QG-2014.pdf b/12/QG-2014/QG-2014.pdf deleted file mode 100644 index f9c6864..0000000 --- a/12/QG-2014/QG-2014.pdf +++ /dev/null Binary files differdiff --git a/12/QG-2014/ballgame.lisp b/12/QG-2014/ballgame.lisp deleted file mode 100644 index 765d85c..0000000 --- a/12/QG-2014/ballgame.lisp +++ /dev/null @@ -1,49 +0,0 @@ -(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 deleted file mode 100644 index d4bc129..0000000 --- a/12/QG-2014/minroad.c +++ /dev/null @@ -1,69 +0,0 @@ -#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; -} diff --git a/12/QG-2017/README.md b/12/QG-2017/README.md deleted file mode 100644 index 9b79939..0000000 --- a/12/QG-2017/README.md +++ /dev/null @@ -1,80 +0,0 @@ -# KÌ THI CHỌN HỌC SINH GIỎI QUỐC GIA THPT NĂM 2017 - -Môn: **TIN HỌC** - -## Ngày thi thứ nhất: 05/01/2017 - -Thời gian: **180** phút - -### Tổng quan ngày thi thứ nhất - -| Tên bài | File chương trình | File dữ liệu | File kết quả | Điểm | -| ------------- | :---------------: | :----------: | :----------: | :---: | -| Virus | VIRUS.\* | VIRUS.INP | VIRUS.OUT | 7 | -| Dãy Fibonacci | FIBSEQ.\* | FIBSEQ.INP | FIBSEQ.OUT | 7 | -| Trò chơi | BGAME.\* | BGAME.INP | BGAME.OUT | 6 | - -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++. - -### Virus - -*TextFile* là một virus chuyên tấn công các file văn bản theo phương thức sau: -Sao chép một đoạn các ký tự liên tiếp trong nội dung của file văn bản vào bộ -nhớ trong, thay đổi một số ký tự trong đoạn này, sau đó chèn đoạn văn bản đã -thay đổi vào ngay sau đoạn văn bản vừa sao chép trong file văn bản. - -Vinh đang phát triển phần mềm để phát hiện một file văn bản đã bị nhiễm virus -nói trên hay chưa. Vì thế, Vinh cần giải quyết bài toán sau: Cho xâu ký tự *T* -và số nguyên không âm *k*, xâu con gồm các ký tự từ vị trí *p* đến vị trí *q* -của xâu T được gọi là đoạn có khả năng bị virus sao chép mức *k* nếu nó sai -khác với xâu con gồm các ký tự từ vị trí *q*+1 đến vị trí *q*+(*q*-*p*+1) của -xâu T ở không quá k vị trí. - -Ví dụ, xét xâu *T* = `zabaaxy` và *k* = 1. Đoạn văn bản `ab` từ ký tự thứ 2 đến -ký tự thứ 3 là đoạn văn bản độ dài 2 có khả năng bị virus sao chép mức 1 vì nó -khác với đoạn văn bản `aa` gồm các ký tự từ ký tự thứ 4 đến ký tự thứ 5 của xâu -*T* ở 1 vị trí. - -#### Yêu cầu - -Cho xâu ký tự *T* và *n* số nguyên không âm *k*<sub>1</sub>, *k*<sub>2</sub>, -…, *k<sub>n</sub>*. Với mỗi giá trị *k<sub>i</sub>*, hãy tìm độ dài đoạn dài -nhất trong xâu *T* có khả năng bị virus sao chép mức *k<sub>i</sub>* (*i* = 1, -2, …, *n*). - -#### Dữ liệu - -* Dòng đầu chứa số nguyên dương *n* (*n* ≤ 10); -* Dòng thứ hai chứa một xâu *T* gồm các chữ cái in thường lấy từ tập 26 chữ cái - tiếng Anh từ `a` đến `z`; -* Dòng thứ *i* trong số *n* dòng tiếp theo ghi số nguyên không âm - *k<sub>i</sub>* (*k<sub>i</sub>* ≤ 10, *i* = 1, 2, …, *n*). - -#### Kết quả - -*n* dòng, dòng thứ *i* ghi một số nguyên không âm là độ dài đoạn dài nhất có -khả năng bị virus sao chép mức *k<sub>i</sub>* , *i* = 1, 2, …, *n*. Ghi *0* -nếu không tìm được đoạn như vậy. - -#### Ràng buộc - -Ký hiệu *m* là độ dài của xâu *T*. - -* Có 40% số lượng test thỏa mãn điều kiện: *m* ≤ 300; -* Có thêm 30% số lượng test thỏa mãn điều kiện: *m* ≤ 3000; *k<sub>i</sub>* = 0 - với mọi *i*; -* 30% số lượng test còn lại thỏa mãn điều kiện: *m* ≤ 3000. - -#### Ví dụ - -| VIRUS.INP | VIRUS.OUT | -| ------------------------- | :-------: | -| 2<br>zabaaxy<br>0<br>1 | 1<br>2 | -| 2<br>zcaabcaaaa<br>0<br>1 | 2<br>4 | - -##### Giải thích - -Trong ví dụ thứ hai, đoạn dài nhất có khả năng bị virus sao chép mức 0 là `aa` -có độ dài 2, đoạn dài nhất có khả năng bị virus sao chép mức 1 là `caab` có độ -dài 4. diff --git a/12/QG-2017/virus.c b/12/QG-2017/virus.c deleted file mode 100644 index add408c..0000000 --- a/12/QG-2017/virus.c +++ /dev/null @@ -1,94 +0,0 @@ -#include <stdio.h> -#include <stdlib.h> -#include <string.h> - -char T[3001], **mem; - -char difflim(char lim, short len, short beg) -{ - char count = 0, *s, *z; - short i; - - if (mem[len - 1][beg] >= 0) - return mem[len - 1][beg] <= lim; - s = T + beg; - z = s + len; - for (i = 0; i < len; i++) - if ((count += s[i] != z[i]) > 10) - break; - return (mem[len - 1][beg] = count) <= lim; -} - -int main() { - FILE *f = fopen("VIRUS.INP", "r"); - char i, n, level, *levels; - short m, j, k, len, lenpos, pos[3000], res[11] = {}; - - fscanf(f, "%hhd\n%s\n", &n, T); - levels = malloc(n); - for (i = 0; i < n; i++) - fscanf(f, "%hhd\n", levels + i); - fclose(f); - m = strlen(T); - - for (i = 97; i < 123; i++) { - lenpos = 0; - for (j = 0; j < m; j++) - if (T[j] == i) - pos[lenpos++] = j; - - if (lenpos < 2) - continue; - - for (j = 0; j < lenpos - 1; j++) - for (k = lenpos - 1; k > j; k--) { - len = pos[k] - pos[j]; - if (len <= res[0]) - break; - if (m - pos[k] < len) - continue; - if (!strncmp(T + pos[j], T + pos[k], len)) { - res[0] = len; - break; - } - } - } - - mem = malloc(m * sizeof(char *) / 2); - for (len = 0; len < m / 2; len++) { - mem[len] = malloc(m - len * 2); - for (j = 0; j < m - len * 2; j++) - mem[len][j] = -1; - } - - for (level = 1; level <= 10; level++) { - for (i = j = 0; i < n; i++) - if (levels[i] == level) - j++; - if (!j) - continue; - - if (level * 2 > m) { - res[level] = m / 2; - continue; - } - - res[level] = level; - for (j = 0; j < level; j++) - if (res[j] > res[level]) - res[level] = res[j]; - - for (len = m / 2; len > res[level]; len--) - for (j = 0; j <= m - len * 2; j++) - if (difflim(level, len, j)) { - res[level] = len; - break; - } - } - - f = fopen("VIRUS.OUT", "w"); - for (i = 0; i < n; i++) - fprintf(f, "%hd\n", res[levels[i]]); - fclose(f); - return 0; -} diff --git a/12/TP-HN-2008/R1/BL1.PAS b/12/TP-HN-2008/R1/BL1.PAS deleted file mode 100644 index 6931b1b..0000000 --- a/12/TP-HN-2008/R1/BL1.PAS +++ /dev/null @@ -1,26 +0,0 @@ -uses math; - -var - f : text; - m, n, i : byte; - a, b : double; -j -begin - assign(f, 'LT.IN'); - reset(f); - read(f, n, m); - close(f); - a := 1; - for i := 1 to n do - a := a * 2; - b := 1; - for i := 1 to m do - b := b * 3; - a := a + b; - for i := 1 to trunc(log10(a)) do - a := a / 10; - assign(f, 'LT.OU'); - rewrite(f); - writeln(f, trunc(a)); - close(f) -end. diff --git a/12/TP-HN-2008/R1/BL2.PAS b/12/TP-HN-2008/R1/BL2.PAS deleted file mode 100644 index e228240..0000000 --- a/12/TP-HN-2008/R1/BL2.PAS +++ /dev/null @@ -1,57 +0,0 @@ -type - rect = record - a : longint; - b : longint - end; - arec = array of rect; - -var - f : text; - c, d, e : rect; - -function join(g, h : rect) : arec; - var n : byte = 0; - procedure j01n(p, q : longint); - begin - inc(n); - setlength(join, n); - join[n - 1].a := p; - join[n - 1].b := q - end; - begin - if g.a = h.a then j01n(g.a, g.b + h.b); - if g.a = h.b then j01n(g.a, g.b + h.a); - if g.b = h.a then j01n(g.b, g.a + h.b); - if g.b = h.b then j01n(g.b, g.a + h.a); - end; - -procedure out(m : longint); - begin - assign(f, 'GH.OU'); - rewrite(f); - writeln(f, m); - close(f); - halt - end; - -procedure libl2(x, y, z : rect); - var i, j : rect; - begin - for i in join(x, y) do - for j in join(z, i) do - if (j.a = j.b) and (j.a <> 0) then - out(j.a) - end; - -begin - assign(f, 'GH.IN'); - reset(f); - readln(f, c.a, c.b); - readln(f, d.a, d.b); - readln(f, e.a, e.b); - close(f); - libl2(c, d, e); - libl2(d, e, c); - libl2(e, c, d); - out(0) -end. diff --git a/12/TP-HN-2008/R1/BL3.PAS b/12/TP-HN-2008/R1/BL3.PAS deleted file mode 100644 index a49b4d6..0000000 --- a/12/TP-HN-2008/R1/BL3.PAS +++ /dev/null @@ -1,45 +0,0 @@ -type ar = array[0..3] of longint; - -var - f : text; - m, n, i, j : shortint; - a : array[1..101, -1..102] of longint; - tmp, max : longint; - -function next(x, y : shortint) : ar; - begin - next[0] := a[x + 1, y - 2]; - next[1] := a[x + 1, y + 2]; - next[2] := a[x + 2, y - 1]; - next[3] := a[x + 2, y + 1] - end; - -begin - for i := 1 to 101 do - for j := -1 to 102 do - a[i, j] := 0; - assign(f, 'QM.IN'); - reset(f); - readln(f, m, n); - for i := 1 to m do - for j := 1 to n do - read(f, a[i, j]); - close(f); - for i := m - 1 downto 1 do - for j := 1 to n do - begin - max := 0; - for tmp in next(i, j) do - if tmp > max then - max := tmp; - a[i, j] := a[i, j] + max; - end; - assign(f, 'QM.OU'); - rewrite(f); - max := 0; - for i := 1 to n do - if a[1, i] > max then - max := a[1, i]; - writeln(f, max); - close(f); -end. diff --git a/12/TP-HN-2008/R1/BL4.pas b/12/TP-HN-2008/R1/BL4.pas deleted file mode 100644 index c552b0d..0000000 --- a/12/TP-HN-2008/R1/BL4.pas +++ /dev/null @@ -1,62 +0,0 @@ -var - f: text; - n, i: int16; - a, b: array of int32; - - -procedure swp(var x, y: int32); - var - tmp: int32; - - begin - tmp := x; - x := y; - y := tmp - end; - - -procedure qsort(l, h: int16); - var - i, j: int16; - tmp: int32; - - begin - i := l; - j := h; - tmp := a[(l + h) div 2]; - - repeat - while a[i] < tmp do - inc(i); - while a[j] > tmp do - dec(j); - - if i <= j then - begin - swp(a[i], a[j]); - swp(b[i], b[j]); - inc(i); - dec(j) - end; - until i > j; - - if l < j then - qsort(l, j); - if i < h then - qsort(i, h) - end; - - -begin - assign(f, 'CLB.IN'); - reset(f); - readln(f, n); - setlength(a, n); - setlength(b, n); - for i := 0 to n - 1 do - readln(f, a[i], b[i]); - close(f); - qsort(0, n - 1); - for i := 0 to n - 1 do - writeln(a[i], ' ', b[i]) -end. diff --git a/12/TP-HN-2008/R1/CLB.IN b/12/TP-HN-2008/R1/CLB.IN deleted file mode 100644 index 662c775..0000000 --- a/12/TP-HN-2008/R1/CLB.IN +++ /dev/null @@ -1,4 +0,0 @@ -3 -7 9 -3 8 -10 20 diff --git a/12/TP-HN-2008/R1/CLB.OU b/12/TP-HN-2008/R1/CLB.OU deleted file mode 100644 index e69de29..0000000 --- a/12/TP-HN-2008/R1/CLB.OU +++ /dev/null diff --git a/12/TP-HN-2008/R1/R1.DOC b/12/TP-HN-2008/R1/R1.DOC deleted file mode 100644 index 5e29da2..0000000 --- a/12/TP-HN-2008/R1/R1.DOC +++ /dev/null Binary files differdiff --git a/12/TP-HN-2008/R2/README.md b/12/TP-HN-2008/R2/README.md deleted file mode 100644 index 00ccc3e..0000000 --- a/12/TP-HN-2008/R2/README.md +++ /dev/null @@ -1,115 +0,0 @@ -# KÌ THI CHỌN HỌC SINH GIỎI CẤP THÀNH PHỐ LỚP 12 NĂM HỌC 2015 - 2016 - -SỞ GIÁO DỤC VÀ ĐÀO TẠO HÀ NỘI - -Môn thi: TIN HỌC - -Ngày thi: 10/12/2008 - -Thời gian làm bài: 180 phút - -## Tổng quan bài thi - -| Bài | Tệp chương trình | Tệp dữ liệu vào | Tệp kết quả ra | Thời gian | -| :---: | :--------------: | :-------------: | :------------: | :-------: | -| 1 | TBC.PAS | TBC.INP | TBC.OUT | 2 giây | -| 2 | HC.PAS | HC.INP | HC.OUT | 2 giây | -| 3 | DG.PAS | DG.INP | DG.OUT | 2 giây | - -## Bài 1: Số trung bình cộng - -Cho dãy số nguyên a<sub>1</sub>, a<sub>2</sub>, …, a<sub>n</sub>. Số -a<sub>p</sub> (1 ≤ p ≤ n) được gọi là một số trung bình cộng trong dãy nếu tồn -tại 3 chỉ số i, j, k (1 ≤ i, j, k ≤ n) đôi một khác nhau, sao cho a<sub>p</sub> -= (a<sub>i</sub> + a<sub>j</sub> + a<sub>k</sub>) / 3. - -### Yêu cầu - -Hãy tìm số lượng các số trung bình cộng trong dãy. - -### Dữ liệu - -* Dòng đầu ghi số nguyên dương n (3 ≤ n ≤ 1000); -* Dòng thứ i trong n dòng tiếp theo ghi số nguyên a<sub>i</sub> - (|a<sub>i</sub>| < 10<sup>8</sup>). - -### Kết quả - -Một số duy nhất là đáp án của bài toán. - -### Ví dụ - -| TBC.INP | TBC.OUT | -| :------------------------: | :-----: | -| 5<br>4<br>3<br>6<br>3<br>5 | 2 | -| 3<br>1<br>2<br>5 | 0 | - -*Chú ý: 50% số test có n ≤ 300.* - -### Bài 2: Hội chợ - -Một khu hội chợ có m × n gian hàng được bố trí trong một khu hình chữ nhật kích -thước m × n. Các hàng của hình chữ nhật được đánh số từ trên xuống dưới bắt đầu -từ 1 đến m, còn các cột – đánh số từ trái sang phải, bắt đầu từ 1 đến n, ô nằm -giao của hàng i và cột j là gian hàng (i, j). Mỗi gian hàng trưng bày một sản -phẩm và đều có cửa thông với các gian hàng chung cạnh với nó. Khách tham quan -đi vào khu hội chợ từ một gian hàng bất kỳ bên trái (i bất kỳ, j = 1) và không -nhất thiết phải thăm quan tất cả các gian hàng. Khách chỉ có thể đi ra khỏi khu -hội chợ từ các gian hàng bên phải (i bất kỳ, j = n), tại mỗi gian hàng khách có -thể di chuyển qua các gian hàng có cửa thông với nó. Khi đi vào gian hàng (i, -j) thì khách tham quan phải mua vé giá là a<sub>i, j</sub>. - -### Yêu cầu - -Tính chi phí ít nhất mà khách tham quan phải trả khi tham quan khu hội chợ. - -### Dữ liệu - -* Dòng đầu tiên ghi số m, n (2 ≤ m, n ≤ 200). -* m dòng sau, mỗi dòng n số nguyên không âm, cho biết giá vé các gian hàng của - khu hội chợ. Giá vé tại gian hàng (i, j) là a<sub>i, j</sub> ≤ 30000. - -### Kết quả - -Một số duy nhất là chi phí ít nhất tìm được. - -### Ví dụ - -| HC.INP | HC.OUT | -| ------------------------------------ | :----: | -| 3 4<br>2 1 9 1<br>5 0 3 4<br>2 1 9 1 | 10 | - -*Chú ý: 50% số test có m, n ≤ 20.* - -## Bài 3: Đa giác - -Trên mặt phẳng tọa độ, xét đa giác lồi n đỉnh, các đỉnh đều có tọa độ nguyên và -có giá trị tuyệt đối không vượt quá 10<sup>5</sup>. Các đỉnh của đa giác được -liệt kê theo chiều kim đồng hồ. - -### Yêu cầu - -Cho đoạn thẳng xác định bởi hai điểm có tọa độ là (x<sub>1</sub>, -y<sub>1</sub>) và (x<sub>2</sub>, y<sub>2</sub>) trong đó x<sub>1</sub>, -y<sub>1</sub>, x<sub>2</sub>, y<sub>2</sub> là các số nguyên và có giá trị -tuyệt đối không vượt quá 10<sup>6</sup>. Hãy xác định độ dài L là phần của đoạn -thẳng nằm trong đa giác hay trên cạnh của đa giác và đưa ra số nguyên là phần -nguyên của tích L * 100. - -### Dữ liệu - -* Dòng đầu tiên chứa số nguyên n (3 ≤ n ≤ 100); -* Dòng thứ i trong n dòng sau chứa 2 số nguyên xác định tọa độ đỉnh i của đa - giác; -* Dòng cuối cùng chứa 4 số nguyên x<sub>1</sub>, y<sub>1</sub>, x<sub>2</sub>, - y<sub>2</sub>. - -### Kết quả - -Một số nguyên là phần nguyên của tích L * 100. - -### Ví dụ - -| DG.INP | DG.OUT | -| ------------------------------------------- | :----: | -| 4<br>0 1<br>1 0<br>0 -1<br>-1 0<br>-2 0 0 0 | 100 | diff --git a/12/TP-HN-2008/R2/dg.c b/12/TP-HN-2008/R2/dg.c deleted file mode 100644 index e2422df..0000000 --- a/12/TP-HN-2008/R2/dg.c +++ /dev/null @@ -1,102 +0,0 @@ -#include <math.h> -#include <stdio.h> - -#define ABS(x) (((x) < 0) ? -(x) : (x)) -#define SQR(x) ((x) * (x)) -#define DET(a, b, c, d) ((a) * (d) - (b) * (c)) -#define MIN(a, b) (((a) < (b)) ? (a) : (b)) -#define MAX(a, b) (((a) > (b)) ? (a) : (b)) - -typedef struct { - long x, y; -} poin_t; - -typedef struct { - float x, y; -} fpoin_t; - -long area2(poin_t A, poin_t B, poin_t C) -{ - return ABS(DET(C.x - A.x, A.x - B.x, C.y - A.y, A.y - B.y)); -} - -int main() -{ - FILE *f = fopen("DG.INP", "r"); - char n, i, c = 0, b; - poin_t M, N, P, Q, polygon[101]; - fpoin_t tmp, intersections[2]; - long Mout = 0, Nout, d; - double res; - - fscanf(f, "%hhd", &n); - for (i = 0; i < n; i++) - fscanf(f, "%ld %ld", &polygon[i].x, &polygon[i].y); - fscanf(f, "%ld %ld %ld %ld", &M.x, &M.y, &N.x, &N.y); - fclose(f); - f = fopen("DG.OUT", "w"); - if (M.x == N.x && M.y == N.y) { - fputs("0\n", f); - fclose(f); - return 0; - } - - for (i = 1; i < n - 1; i++) - Mout += area2(*polygon, polygon[i], polygon[i + 1]); - for (Nout = Mout, polygon[n] = *polygon, i = 0; i < n; i++) { - Mout -= area2(M, polygon[i], polygon[i + 1]); - Nout -= area2(N, polygon[i], polygon[i + 1]); - } - if (!Mout && !Nout) { - fprintf(f, "%ld\n", - (long) (sqrt(SQR(M.x - N.x) + SQR(M.y - N.y)) * 100)); - fclose(f); - return 0; - } - - for (i = 0; i < n; i++) { - P = polygon[i]; - Q = polygon[i + 1]; - d = DET(M.x - N.x, M.y - N.y, P.x - Q.x, P.y - Q.y); - if (!d) - continue; - - tmp.x = DET(DET(M.x, M.y, N.x, N.y), M.x - N.x, - DET(P.x, P.y, Q.x, Q.y), P.x - Q.x) / (double) d; - tmp.y = DET(DET(M.x, M.y, N.x, N.y), M.y - N.y, - DET(P.x, P.y, Q.x, Q.y), P.y - Q.y) / (double) d; - - if (tmp.x < MAX(MIN(M.x, N.x), MIN(P.x, Q.x)) - || tmp.x > MIN(MAX(M.x, N.x), MAX(P.x, Q.x)) - || tmp.y < MAX(MIN(M.y, N.y), MIN(P.y, Q.y)) - || tmp.y > MIN(MAX(M.y, N.y), MAX(P.y, Q.y))) - continue; - - for (b = d = 0; d < c; d++) - if (intersections[d].x == tmp.x - && intersections[d].y == tmp.y) - b = 1; - if (b) - continue; - - intersections[c].x = tmp.x; - intersections[c].y = tmp.y; - c++; - } - - if (!Mout && c) - res = SQR(M.x - intersections[0].x) - + SQR(M.y - intersections[0].y); - else if (!Nout && c) - res = SQR(N.x - intersections[0].x) - + SQR(N.y - intersections[0].y); - else if (c == 2) - res = SQR(intersections[0].x - intersections[1].x) - + SQR(intersections[0].y - intersections[1].y); - else - res = 0; - fprintf(f, "%ld\n", (long) (sqrt(res) * 100)); - fclose(f); - - return 0; -} diff --git a/12/TP-HN-2008/R2/hc.cpp b/12/TP-HN-2008/R2/hc.cpp deleted file mode 100644 index 1ea6ee3..0000000 --- a/12/TP-HN-2008/R2/hc.cpp +++ /dev/null @@ -1,73 +0,0 @@ -#include <iostream> -#include <fstream> -#include <functional> -#include <queue> -#include <vector> - -#define ENC(a, x, y) (((a) << 16) + ((x) << 8) + (y)) - -using namespace std; - -int -main() -{ - long long m, n, i, j, a[200][200]; - ifstream infile; - infile.open("HC.INP"); - infile >> m >> n; - for (i = 0; i < m; i++) - for (j = 0; j < n; j++) - infile >> a[i][j]; - infile.close(); - - priority_queue<long long, vector<long long>, greater<long long>> heap; - long long path[200][200] = {}; - for (i = 0; i < m; i++) - { - heap.push(ENC(*a[i], i, 0)); - path[i][0] = 1; - } - - long long tmp, x, y; - while (!heap.empty()) - { - tmp = heap.top(); - heap.pop(); - x = tmp >> 8 & 255; - y = tmp & 255; - tmp >>= 16; - if (y == n - 1) - break; - - if (!path[x][y + 1]) - { - heap.push(ENC(tmp + a[x][y + 1], x, y + 1)); - path[x][y + 1] = 1; - } - - if (y) - if (x && !path[x - 1][y]) - { - heap.push(ENC(tmp + a[x - 1][y], x - 1, y)); - path[x - 1][y] = 1; - } - else if (x < m - 1 && !path[x + 1][y]) - { - heap.push(ENC(tmp + a[x + 1][y], x + 1, y)); - path[x + 1][y] = 1; - } - - if (y > 1 && !path[x][y - 1]) - { - heap.push(ENC(tmp + a[x][y - 1], x, y - 1)); - path[x][y - 1] = 1; - } - } - - ofstream outfile; - outfile.open("HC.OUT"); - outfile << tmp << endl; - outfile.close(); - - return 0; -} diff --git a/12/TP-HN-2008/R2/tbc.pas b/12/TP-HN-2008/R2/tbc.pas deleted file mode 100644 index 1a26a91..0000000 --- a/12/TP-HN-2008/R2/tbc.pas +++ /dev/null @@ -1,69 +0,0 @@ -var - f : text; - i, l, m, n : integer; - a : array[1..1000] of longint; - -procedure qsort(l, h : integer); - var - i, j : integer; - x, tmp : longint; - begin - i := l; - j := h; - x := a[(i + j) div 2]; - repeat - while a[i] < x do inc(i); - while x < a[j] do dec(j); - if i <= j then - begin - tmp := a[i]; - a[i] := a[j]; - a[j] := tmp; - inc(i); - dec(j) - end - until i > j; - if l < j then qsort(l, j); - if i < h then qsort(i, h) - end; - -function biin(n0 : integer) : boolean; - var l, h, m : integer; - begin - l := 1; - h := n; - repeat - m := (l + h) div 2; - if a[m] = n0 then exit(true); - if a[m] < n0 then l := m + 1 - else h := m - 1 - until l > h; - biin := false - end; - -function libtbc(n0 : integer) : boolean; - var i, j : integer; - begin - for i := 1 to n0 - 1 do - for j := n0 + 1 to n do - if biin(a[n0] * 3 - a[i] - a[j]) then - exit(true); - libtbc := false - end; - -begin - assign(f, 'TBC.INP'); - reset(f); - readln(f, n); - for i := 1 to n do readln(f, a[i]); - close(f); - qsort(1, n); - m := 0; - for l := 2 to n - 1 do - if libtbc(l) then - inc(m); - assign(f, 'TBC.OUT'); - rewrite(f); - writeln(f, m); - close(f) -end. diff --git a/12/TP-HN-2009/R1/BTN.PAS b/12/TP-HN-2009/R1/BTN.PAS deleted file mode 100644 index dbb022d..0000000 --- a/12/TP-HN-2009/R1/BTN.PAS +++ /dev/null @@ -1,87 +0,0 @@ -type sni = record - s : ansistring; - n : integer -end; - -var - f : text; - s : ansistring; - op, cl : integer; - c : char; - -function cal(s : ansistring) : integer; - var - c : char; - tmp : integer = 0; - begin - cal := 0; - for c in s do - if c = '(' then - begin - inc(tmp); - if tmp > cal then - cal := tmp - end - else - begin - dec(tmp); - if tmp < 0 then exit(0) - end; - if tmp <> 0 then - exit(0) - end; - -function rplc( - s : ansistring; - c : char; - idx : integer -) : ansistring; - begin - exit(copy(s, 1, idx - 1) + c + copy(s, idx + 1, length(s) - idx + 1)) - end; - -function libtn( - s : ansistring; - op, cl, idx : integer -) : sni; - var - i : integer; - v0, v1 : sni; - begin - if (op = 0) and (cl = 0) then - begin - libtn.s := s; - libtn.n := cal(s); - exit - end; - i := idx; - while s[i] <> '?' do - inc(i); - if op = 0 then - exit(libtn(rplc(s, ')', i), 0, cl - 1, i + 1)); - if cl = 0 then - exit(libtn(rplc(s, '(', i), op - 1, 0, i + 1)); - v0 := libtn(rplc(s, '(', i), op - 1, cl, i + 1); - v1 := libtn(rplc(s, ')', i), op, cl - 1, i + 1); - if v0.n > v1.n then - exit(v0) - else exit(v1) - end; - -begin - assign(f, 'BTN.INP'); - reset(f); - read(f, s); - close(f); - op := length(s) div 2; - cl := length(s) div 2; - for c in s do - if c = '(' then - dec(op) - else if c = ')' then - dec(cl); - assign(f, 'BTN.OUT'); - rewrite(f); - writeln(f, libtn(s, op, cl, 1).s); - close(f) -end. diff --git a/12/TP-HN-2009/R1/HEXA.PAS b/12/TP-HN-2009/R1/HEXA.PAS deleted file mode 100644 index a2fd6ca..0000000 --- a/12/TP-HN-2009/R1/HEXA.PAS +++ /dev/null @@ -1,75 +0,0 @@ -var - f : text; - n, n0, m, i, j, tmp : longint; - s : string; - -function dec2hex(deca : longint) : string; - var - a : array[0..7] of byte; - i, j : byte; - begin - dec2hex := ''; - i := 0; - while deca > 0 do - begin - a[i] := deca mod 16; - deca := deca div 16; - inc(i) - end; - dec(i); - for j := i downto 0 do - case a[j] of - 0 : dec2hex := dec2hex + '0'; - 1 : dec2hex := dec2hex + '1'; - 2 : dec2hex := dec2hex + '2'; - 3 : dec2hex := dec2hex + '3'; - 4 : dec2hex := dec2hex + '4'; - 5 : dec2hex := dec2hex + '5'; - 6 : dec2hex := dec2hex + '6'; - 7 : dec2hex := dec2hex + '7'; - 8 : dec2hex := dec2hex + '8'; - 9 : dec2hex := dec2hex + '9'; - 10 : dec2hex := dec2hex + 'A'; - 11 : dec2hex := dec2hex + 'B'; - 12 : dec2hex := dec2hex + 'C'; - 13 : dec2hex := dec2hex + 'D'; - 14 : dec2hex := dec2hex + 'E'; - 15 : dec2hex := dec2hex + 'F' - end - end; - -begin - assign(f, 'HEXA.INP'); - reset(f); - read(f, n); - close(f); - m := n; - i := 0; - while m > 0 do - begin - inc(i); - tmp := 1; - for j := 1 to i - 1 do tmp := tmp * 16; - m := m + i * (tmp - tmp * 16) - end; - m := i; - for i := 1 to m - 1 do - begin - tmp := 1; - for j := 1 to i - 1 do tmp := tmp * 16; - n := n + i * (tmp - tmp * 16) - end; - n0 := (n + m - 1) div m; - for i := 1 to m - 1 do - begin - tmp := 1; - for j := 1 to i - 1 do tmp := tmp * 16; - n0 := n0 + tmp * 16 - tmp - end; - s := dec2hex(n0); - if n mod m > 0 then m := n mod m; - assign(f, 'HEXA.OUT'); - rewrite(f); - writeln(f, s[m]); - close(f) -end. diff --git a/12/TP-HN-2009/R1/PS.PAS b/12/TP-HN-2009/R1/PS.PAS deleted file mode 100644 index 6cf2d09..0000000 --- a/12/TP-HN-2009/R1/PS.PAS +++ /dev/null @@ -1,80 +0,0 @@ -var - f : text; - m, n : byte; - k, i, j, l, gcd0 : integer; - a, b : array[1..30] of integer; - c : array[0..1, 1..900] of integer; - -function gcd(d, e : integer) : integer; - var tmp : integer; - begin - while d > 0 do - begin - tmp := d; - d := e mod d; - e := tmp - end; - gcd := e - end; - -procedure qsort(b, e: integer); - var i, j, x, tmp: integer; - begin - i := b; - j := e; - x := (b + e) div 2; - repeat - while c[0, i] * c[1, x] < c[0, x] * c[1, i] do inc(i); - while c[0, x] * c[1, j] < c[0, j] * c[1, x] do dec(j); - if i <= j then - begin - tmp := c[0, i]; - c[0, i] := c[0, j]; - c[0, j] := tmp; - tmp := c[1, i]; - c[1, i] := c[1, j]; - c[1, j] := tmp; - inc(i); - dec(j) - end - until i > j; - if b < j then qsort(b, j); - if i < e then qsort(i, e) - end; - -begin - assign(f, 'PS.INP'); - reset(f); - read(f, m, n, k); - for i := 1 to m do read(f, a[i]); - for i := 1 to n do read(f, b[i]); - close(f); - l := 0; - for i := 1 to m do - for j := 1 to n do - begin - inc(l); - gcd0 := gcd(a[i], b[j]); - c[0, l] := a[i] div gcd0; - c[1, l] := b[j] div gcd0 - end; - qsort(1, l); - i := 1; - while i < l do - begin - inc(i); - if c[0, i] * c[1, i - 1] = c[0, i - 1] * c[1, i] then - begin - dec(l); - for j := i to l do - begin - c[0, j] := c[0, j + 1]; - c[1, j] := c[1, j + 1] - end - end - end; - assign(f, 'PS.OUT'); - rewrite(f); - writeln(f, c[0, k], ' ', c[1, k]); - close(f) -end. diff --git a/12/TP-HN-2009/R1/R1.pdf b/12/TP-HN-2009/R1/R1.pdf deleted file mode 100644 index b0834b3..0000000 --- a/12/TP-HN-2009/R1/R1.pdf +++ /dev/null Binary files differdiff --git a/12/TP-HN-2009/R2/BAI1.PAS b/12/TP-HN-2009/R2/BAI1.PAS deleted file mode 100644 index b28ae0b..0000000 --- a/12/TP-HN-2009/R2/BAI1.PAS +++ /dev/null @@ -1,90 +0,0 @@ -uses math; - -var - f : text; - n : longint; - lena, i : integer; - a : array[1..512] of longint; - -procedure insort(x : longint); - var i, j : integer; - begin - inc(lena); - a[lena] := x - 1; - for i := 1 to lena do - if a[i] < x then begin - for j := lena downto i + 1 do - a[j] := a[j - 1]; - a[i] := x; - exit - end - end; - -function notin(x : longint) : boolean; - var l, h, m : integer; - begin - l := 1; - h := lena; - repeat - m := (l + h) div 2; - if a[m] = x then exit(false); - if a[m] < x then h := m - 1 - else l := m + 1 - until l > h; - notin := true - end; - -procedure mklist(n0 : longint); - var - i, j : byte; - n10, m0 : longint; - begin - if n0 <> 0 then begin - insort(n0); - for i := 0 to trunc(log10(n0)) do - begin - n10 := 1; - for j := 1 to i do n10 := n10 * 10; - m0 := n0 div (n10 * 10) + n0 mod n10; - if notin(m0) then mklist(m0) - end - end - end; - -function prime(m : longint) : boolean; - var p, q : integer; - begin - if m < 2 then exit(false); - if m = 2 then exit(true); - if m = 3 then exit(true); - if m mod 2 = 0 then exit(false); - if m mod 3 = 0 then exit(false); - p := 5; - q := 2; - while p * p <= m do - begin - if m mod p = 0 then exit(false); - p := p + q; - q := 6 - q - end; - prime := true - end; - -begin - assign(f, 'BAI1.INP'); - reset(f); - read(f, n); - close(f); - lena := 0; - mklist(n); - assign(f, 'BAI1.OUT'); - rewrite(f); - for i := 1 to lena do - if prime(a[i]) then begin - writeln(f, a[i]); - close(f); - exit - end; - writeln(f, -1); - close(f) -end. diff --git a/12/TP-HN-2009/R2/BAI2.CPP b/12/TP-HN-2009/R2/BAI2.CPP deleted file mode 100644 index a47760f..0000000 --- a/12/TP-HN-2009/R2/BAI2.CPP +++ /dev/null @@ -1,58 +0,0 @@ -#include <iostream> -#include <fstream> -#include <functional> -#include <map> -#include <queue> -#include <vector> - -#define ENC(distance, current, coupon) (((distance) << 14) + ((current) << 1) + coupon) -#define DEC_D(data) ((data) >> 14) -#define DEC_C(data) ((data) >> 1 & 0b1111111111111) -#define DEC_B(data) ((data) & 1) - -using namespace std; - -int -main() -{ - ifstream infile; - infile.open("BAI2.INP"); - int n, m; - infile >> n >> m; - map<long long, map<long long, long long>> c; - long long k, i, j, l; - for (k = 0; k < m; k++) - { - infile >> i >> j >> l; - c[i][j] = l; - } - infile.close(); - - priority_queue<long long, vector<long long>, greater<long long>> q; - for (auto& item : c[1]) - { - q.push(ENC(item.second, item.first, 1)); - q.push(ENC(0, item.first, 0)); - } - - long long tmp; - while (!q.empty()) - { - tmp = q.top(); - q.pop(); - if (DEC_C(tmp) == n) - break; - for (auto& item : c[DEC_C(tmp)]) - q.push(ENC(DEC_D(tmp) + item.second, item.first, DEC_B(tmp))); - if (DEC_B(tmp)) - for (auto& item : c[DEC_C(tmp)]) - q.push(ENC(DEC_D(tmp), item.first, 0)); - } - - ofstream outfile; - outfile.open("BAI2.OUT"); - outfile << DEC_D(tmp) << endl; - outfile.close(); - - return 0; -} diff --git a/12/TP-HN-2009/R2/BAI3.PAS b/12/TP-HN-2009/R2/BAI3.PAS deleted file mode 100644 index 30eecdf..0000000 --- a/12/TP-HN-2009/R2/BAI3.PAS +++ /dev/null @@ -1,87 +0,0 @@ -type - ar = array of ansistring; - -var - f : text; - s0 : ansistring; - a0 : ar; - -function incre(s1, s2 : ansistring) : boolean; - var - i : smallint; - begin - if length(s1) < length(s2) then exit(true); - if length(s1) > length(s2) then exit(false); - for i := 1 to length(s1) do - begin - if ord(s1[i]) < ord(s2[i]) then exit(true); - if ord(s1[i]) > ord(s2[i]) then exit(false) - end; - exit(false) - end; - -function cal(a : ar) : smallint; - var - len, i, tmp : smallint; - begin - cal := 0; - i := 0; - len := length(a); - while (cal + i < len) and (i + 1 < len) do - begin - inc(i); - if incre(a[0], a[i]) then - begin - tmp := cal(copy(a, i, len - i)) + 1; - if tmp > cal then - cal := tmp - end - end - end; - -function putin( - aray : ar; - strng : ansistring; - len : smallint -) : ar; - begin - setlength(aray, length(aray) + 1); - aray[length(aray) - 1] := copy(strng, 1, len); - exit(aray) - end; - -function libai3( - s : ansistring; - a : ar; - n : smallint -) : smallint; - var - len, i, tmp : smallint; - begin - if s = '' then - exit(cal(a)); - libai3 := 0; - len := length(s); - i := 0; - while (i < n) and (i + libai3 < len) do - begin - inc(i); - tmp := libai3(copy(s, i + 1, len - i), putin(a, s, i), n + 1); - if tmp > libai3 then - libai3 := tmp - end - end; - -begin - assign(f, 'BAI3.INP'); - reset(f); - readln(f); - read(f, s0); - close(f); - setlength(a0, 1); - a0[0] := ''; - assign(f, 'BAI3.OUT'); - rewrite(f); - writeln(f, libai3(s0, a0, 1)); - close(f) -end. diff --git a/12/TP-HN-2009/R2/R2.pdf b/12/TP-HN-2009/R2/R2.pdf deleted file mode 100644 index 7af542a..0000000 --- a/12/TP-HN-2009/R2/R2.pdf +++ /dev/null Binary files differdiff --git a/12/TP-HN-2010/BAI1.PAS b/12/TP-HN-2010/BAI1.PAS deleted file mode 100644 index 029201d..0000000 --- a/12/TP-HN-2010/BAI1.PAS +++ /dev/null @@ -1,30 +0,0 @@ -var - f : text; - i : 1..30; - a : array[0..30] of qword; - -function gcd(a, b : qword) : qword; - var tmp : qword; - begin - while b > 0 do - begin - tmp := b; - b := a mod b; - a := tmp - end; - gcd := a - end; - -begin - assign(f, 'bai1.inp'); - reset(f); - readln(f, a[0]); - for i := 1 to a[0] do read(f, a[i]); - close(f); - for i := a[0] - 1 downto 1 do - a[i] := a[i] * a[i + 1] div gcd(a[i], a[i + 1]); - assign(f, 'bai1.out'); - rewrite(f); - writeln(f, a[1]); - close(f) -end. diff --git a/12/TP-HN-2010/BAI2.PAS b/12/TP-HN-2010/BAI2.PAS deleted file mode 100644 index d6639df..0000000 --- a/12/TP-HN-2010/BAI2.PAS +++ /dev/null @@ -1,40 +0,0 @@ -var - f : text; - s : string; - len, i, j : byte; - count : integer = 0; - -function libai2(s0 : string) : boolean; - var - bo, boo, b0 : boolean; - c : char; - begin - b0 := false; - bo := false; - boo := false; - for c in s0 do - begin - case c of - '0' .. '9' : b0 := true; - 'a' .. 'z' : bo := true; - 'A' .. 'Z' : boo := true - end; - if b0 and bo and boo then exit(true) - end; - exit(false); - end; - -begin - assign(f, 'BAI2.INP'); - reset(f); - read(f, s); - close(f); - len := length(s); - for i := 1 to len - 5 do - for j := 6 to len - i + 1 do - if libai2(copy(s, i, j)) then inc(count); - assign(f, 'BAI2.OUT'); - rewrite(f); - writeln(f, count); - close(f) -end. diff --git a/12/TP-HN-2010/BAI3 b/12/TP-HN-2010/BAI3 deleted file mode 100644 index 7b83e7b..0000000 --- a/12/TP-HN-2010/BAI3 +++ /dev/null Binary files differdiff --git a/12/TP-HN-2010/BAI3.INP b/12/TP-HN-2010/BAI3.INP deleted file mode 100644 index 3609812..0000000 --- a/12/TP-HN-2010/BAI3.INP +++ /dev/null @@ -1 +0,0 @@ -5 5 0 diff --git a/12/TP-HN-2010/BAI3.OUT b/12/TP-HN-2010/BAI3.OUT deleted file mode 100644 index e69de29..0000000 --- a/12/TP-HN-2010/BAI3.OUT +++ /dev/null diff --git a/12/TP-HN-2010/BAI3.o b/12/TP-HN-2010/BAI3.o deleted file mode 100644 index 7706cd6..0000000 --- a/12/TP-HN-2010/BAI3.o +++ /dev/null Binary files differdiff --git a/12/TP-HN-2010/BAI3.pas b/12/TP-HN-2010/BAI3.pas deleted file mode 100644 index aedf9a0..0000000 --- a/12/TP-HN-2010/BAI3.pas +++ /dev/null @@ -1,73 +0,0 @@ -type - board = array[0..31, 0..31] of boolean; - -var - f : text; - a : board; - i, j, k, l, m, n : byte; - -function king( - e : board; - x, y : byte -) : board; - var z, t : byte; - begin - for z := x - 1 to x + 1 do - for t := y - 1 to y + 1 do - e[z, t] := true; - exit(e) - end; - -function full(c : board) : boolean; - var d : boolean; - begin - for d in c do - if not(d) then - exit(false); - exit(true) - end; - -function libai3( - b : board; - x0, y0 : byte -) : byte; - type tmp = record - n, x, y : byte - end; - var - max : tmp; - t, x, y : byte; - begin - if full(b) then exit(0); - max.n := 0; - for x := x0 to m do - for y := y0 to n do - if not(b[x, y]) then - begin - t := libai3(king(b, x, y), x + 1, y + 1) + 1; - writeln(t); - if t > max.n then - begin - max.x := x; - max.y := y; - max.n := t - end - end; - exit(max.n) - end; - -begin - assign(f, 'BAI3.INP'); - reset(f); - readln(f, m, n, k); - for l := 1 to k do - begin - readln(f, i, j); - a := king(a, i, j) - end; - close(f); - assign(f, 'BAI3.OUT'); - rewrite(f); - writeln(libai3(a, 1, 1)); - close(f) -end. diff --git a/12/TP-HN-2010/README.md b/12/TP-HN-2010/README.md deleted file mode 100644 index 625312d..0000000 --- a/12/TP-HN-2010/README.md +++ /dev/null @@ -1 +0,0 @@ -![](TP-2010.png) diff --git a/12/TP-HN-2010/TP-2010.png b/12/TP-HN-2010/TP-2010.png deleted file mode 100644 index 7eacc66..0000000 --- a/12/TP-HN-2010/TP-2010.png +++ /dev/null Binary files differdiff --git a/12/TP-HN-2010/_BAI3.pas b/12/TP-HN-2010/_BAI3.pas deleted file mode 100644 index 09ec0ca..0000000 --- a/12/TP-HN-2010/_BAI3.pas +++ /dev/null @@ -1,73 +0,0 @@ -type - board = array[0..1023] of boolean; - -var - f : text; - a : board; - i, j, k, l, m, n : byte; - -function king( - e : board; - x, y : byte -) : board; - var z, t : byte; - begin - for z := x - 1 to x + 1 do - for t := y - 1 to y + 1 do - e[z, t] := true; - exit(e) - end; - -function full(c : board) : boolean; - var d : boolean; - begin - for d in c do - if not(d) then - exit(false); - exit(true) - end; - -function libai3( - b : board; - x0, y0 : byte -) : byte; - type tmp = record - n, x, y : byte - end; - var - max : tmp; - t, x, y : byte; - begin - if full(b) then exit(0); - max.n := 0; - for x := x0 to m do - for y := y0 to n do - if not(b[x, y]) then - begin - t := libai3(king(b, x, y), x + 1, y + 1) + 1; - writeln(t); - if t > max.n then - begin - max.x := x; - max.y := y; - max.n := t - end - end; - exit(max.n) - end; - -begin - assign(f, 'BAI3.INP'); - reset(f); - readln(f, m, n, k); - for l := 1 to k do - begin - readln(f, i, j); - a := king(a, i, j) - end; - close(f); - assign(f, 'BAI3.OUT'); - rewrite(f); - writeln(libai3(a, 1, 1)); - close(f) -end. diff --git a/12/TP-HN-2015/README.md b/12/TP-HN-2015/README.md deleted file mode 100644 index 2ba87d2..0000000 --- a/12/TP-HN-2015/README.md +++ /dev/null @@ -1,83 +0,0 @@ -# KÌ THI CHỌN HỌC SINH GIỎI CẤP THÀNH PHỐ LỚP 12 NĂM HỌC 2015 - 2016 - -SỞ GIÁO DỤC VÀ ĐÀO TẠO HÀ NỘI - -Môn thi: TIN HỌC - -Ngày thi: 02/10/2015 - -Thời gian làm bài: 180 phút - -## Tổng quan bài thi - -| Bài | Tệp chương trình | Tệp dữ liệu vào | Tệp kết quả ra | Thời gian | -| :---: | :--------------: | :-------------: | :------------: | :-------: | -| 1 | BAI1.PAS | BAI1.INP | BAI1.OUT | 2 giây | -| 2 | BAI2.PAS | BAI2.INP | BAI2.OUT | 2 giây | -| 3 | BAI3.PAS | BAI3.INP | BAI3.OUT | 2 giây | -| 4 | BAI4.PAS | BAI4.INP | BAI4.OUT | 2 giây | - -## Bài 1. Đếm nghiệm (6 điểm) - -Cho phuơng trình: ax + by = c (x, y là ẩn; a, b, c là số nguyên dương nhỏ hơn -10<sup>5</sup>). - -### Yêu cầu - -Hãy đếm số nghiệm nguyên dương (x, y) của phương trình đã cho thoả mãn x, y -nguyên tố cùng nhau. - -### Dữ liệu vào - -Một dòng duy nhất chứa ba số a, b, c cách nhau bởi một dấu cách. - -### Dữ liệu ra - -Số nghiệm (x, y) thoả mãn yêu cầu trên. - -### Ví dụ - -| BAI1.INP | BAI2.OUT | Giải thích | -| -------- | -------- | ------------------------- | -| 1 2 10 | 2 | (x, y) ∈ {(4, 3), (8, 1)} | - -## Bài 2. Điều hoà (5 điểm) - -Một trường THPT có n lớp học được đánh số thứ tự từ 1 đến n cần trang bị điều -hoà. Mỗi lớp một điều hoà với công suất phụ thuộc vào diện tích của từng lớp. -Lớp thứ i cần lắp điều hoà với công suất không bé hơn a<sub>i</sub> (W). Nhà -trường đã tham khảo các cửa hàng điện lạnh và lập được bảng danh mục các loại -điều hoà kèm theo công suất và giá tương ứng. - -### Yêu cầu - -Cho trước yêu cầu điều hoà với công suất tương ứng nhỏ nhất của từng lớp học -cũng như danh mục các loại điều hoà. Hãy giúp nhà trường tính số tiền nhỏ nhất -cần bỏ ra để trang bị điều hoà cho tất cả n lớp học. - -### Dữ liệu vào - -* Dòng đầu là số tự nhiên n (1 ≤ n ≤ 50000) là số lượng lớp học, -* Dòng thứ hai chứ n số nguyên a<sub>i</sub> (1 ≤ a<sub>i</sub> ≤ 1000) là công - suất nhỏ nhất của điều hoà cần trang bị cho lớp i. -* Dòng thứ 3 chứa số nguyên m (1 ≤ m ≤ 50000) là số lượng các model điều hoà - khác nhau (mỗi model có số lượng điều hoà không hạn chế). -* m dòng tiếp theo, mỗi dòng chứa 2 số nguyên b<sub>j</sub>, c<sub>j</sub> (1 ≤ - b<sub>j</sub>, c<sub>j</sub> ≤ 1000) lần lượt là công suất và giá tương ứng - của loại điều hoà model j. - -### Kết quả ra - -Tổng số tiền nhỏ nhất để mua đủ n điều hoà cho các lớp của trường. - -### Ví dụ - -| BAI2.INP | BAI2.OUT | Giải thích | -| -------- | -------- | -------------------------------------- | -| 3 | 13 | Lớp 1 mua điều hoà công suất 2, giá 3 | -| 1 2 3 | | Lớp 2 mua điều hoà công suất 2, giá 3 | -| 4 | | Lớp 3 mua điều hoà công suất 10, giá 7 | -| 1 10 | | | -| 1 5 | | | -| 10 7 | | | -| 2 3 | | | diff --git a/12/TP-HN-2015/bai1.pas b/12/TP-HN-2015/bai1.pas deleted file mode 100644 index 312f2b4..0000000 --- a/12/TP-HN-2015/bai1.pas +++ /dev/null @@ -1,38 +0,0 @@ -var - a, b, c, x, v: smallint; - f: text; - - -function gcd(m, n: smallint): smallint; - var - p: smallint; - - begin - while (n <> 0) do - begin - p := m mod n; - m := n; - n := p - end; - - exit(m) - end; - - -begin - assign(f, 'BAI1.INP'); - reset(f); - read(f, a, b, c); - close(f); - - v := 0; - for x := 1 to c div a do - if ((c - a * x) mod b = 0) and - (gcd(x, (c - a * x) div b) = 1) then - inc(v); - - assign(f, 'BAI1.OUT'); - rewrite(f); - writeln(f, v); - close(f) -end. diff --git a/12/TP-HN-2015/bai2.pas b/12/TP-HN-2015/bai2.pas deleted file mode 100644 index 858d2b1..0000000 --- a/12/TP-HN-2015/bai2.pas +++ /dev/null @@ -1,54 +0,0 @@ -var - n, m, i, b, c, j: word; - a: array of word; - f: text; - bc: array[1..1000, 1..1000] of boolean; - bestprice: array[1..1000] of word; - v: longint = 0; - - -begin - assign(f, 'BAI2.INP'); - reset(f); - - read(f, n); - setlength(a, n); - for i := 0 to n - 1 do - read(f, a[i]); - - fillchar(bc, sizeof(bc), false); - readln(f, m); - for i := 1 to m do - begin - read(f, b, c); - bc[b][c] := true - end; - - close(f); - - for i := 1 to 1000 do - bc[i][1000] := true; - - for i := 1 to 1000 do - if bc[1000][i] then - begin - bestprice[1000] := i; - break - end; - - for i := 999 downto 1 do - begin - for j := 1 to bestprice[i + 1] do - if bc[i][j] then - break; - bestprice[i] := j - end; - - for i := 0 to n - 1 do - inc(v, bestprice[a[i]]); - - assign(f, 'BAI2.OUT'); - rewrite(f); - writeln(f, v); - close(f) -end. diff --git a/12/TP-ThanhHoá-2009/BAI4.PAS b/12/TP-ThanhHoá-2009/BAI4.PAS deleted file mode 100644 index 8706032..0000000 --- a/12/TP-ThanhHoá-2009/BAI4.PAS +++ /dev/null @@ -1,29 +0,0 @@ -const - m: array[1..9] of byte = (0, 0, 1, 1, 0, 0, 4, 7, 0); - equa: array[1..9] of ansistring = ( - #10, - #10, - #10'1+2-3=0'#10, - #10'1-2-3+4=0'#10, - #10, - #10, - #10'1+2-3+4-5-6+7=0'#10'1+2-3-4+5+6-7=0'#10'1-2+3+4-5+6-7=0'#10'1-2-3-4-5+6+7=0'#10, - #10'1+2+3+4-5-6-7+8=0'#10'1+2+3-4+5-6+7-8=0'#10'1+2-3+4+5+6-7-8=0'#10'1+2-3-4-5-6+7+8=0'#10'1-2+3-4-5+6-7+8=0'#10'1-2-3+4+5-6-7+8=0'#10'1-2-3+4-5+6+7-8=0'#10, - #10 - ); - -var - n: byte; - f: text; - -begin - assign(f, 'BAI4.INP'); - reset(f); - read(f, n); - close(f); - - assign(f, 'BAI4.OUT'); - rewrite(f); - write(f, m[n], equa[n]); - close(f) -end. diff --git a/12/TP-ThanhHoá-2009/README.md b/12/TP-ThanhHoá-2009/README.md deleted file mode 100644 index f5d69a1..0000000 --- a/12/TP-ThanhHoá-2009/README.md +++ /dev/null @@ -1,173 +0,0 @@ -# Kì thi học sinh giỏi tỉnh Thanh Hoá lớp 12 năm học 2008 - 2009 - -Sở Giáo dục và Đào tạo Thanh Hoá - -Môn thi: Tin học - -Ngày thi: 28/03/2009 - -Thời gian: 180 phút - -## Tổng quan bài thi - -| Bài | Tệp chương trình | Tệp dữ liệu vào | Tệp kết quả ra | Điểm | -| :---: | :--------------: | :-------------: | :------------: | :---: | -| 1 | BAI1.PAS | BAI1.INP | BAI1.OUT | 5 | -| 2 | BAI2.PAS | BAI2.INP | BAI2.OUT | 5 | -| 3 | BAI3.PAS | BAI3.INP | BAI3.OUT | 4 | -| 4 | BAI4.PAS | BAI4.INP | BAI4.OUT | 3 | -| 5 | BAI5.PAS | BAI5.INP | BAI5.OUT | 3 | - -Giới hạn thời gian cho mỗi test là 3 giây. - -Dữ liệu vào là đúng đắn, không cần phải kiểm tra. - -## Bài 1: Số nguyên tố - -Cho dãy số gồm có N số nguyên dương a<sub>1</sub>, a<sub>2</sub>, …, -a<sub>N</sub> và một số nguyên dương K. - -### Yêu cầu - -Hãy cho biết số lượng các phần tử có giá trị nhỏ hơn K là số nguyên tố của dãy -số trên. - -### Dữ liệu - -* Dòng đầu tiên là hai số N và K. -* Dòng tiếp theo lần lượt là N số nguyên của dãy số. - -### Kết quả - -Số M là số lượng các phần tử của dãy số thoả mãn yêu cầu đề bài. - -### Giới hạn - -* 0 < N < 50000 -* 0 < K, a<sub>i</sub> < 5000 với mọi i = 1, 2, …, N - -### Ví dụ - -| BAI1.INP | BAI1.OUT | -| --------------------- | :------: | -| 7 8<br>1 2 3 8 7 6 11 | 3 | - -## Bài 2: Trung bình cộng - -Cho dãy gồm n số nguyên a<sub>1</sub>, a<sub>2</sub>, …, a<sub>n</sub> và số -nguyên K. - -### Yêu cầu - -Cho biết trong dãy số đã cho có tồn tại hay không một cặp số mà trung bình cộng -của chúng là K. - -### Dữ liệu - -* Dòng đầu tiên ghi hai số n, K. -* Dòng tiếp theo lần lượt ghi n số a<sub>1</sub>, a<sub>2</sub>, …, - a<sub>n</sub>. Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu - cách trống. - -### Kết quả - -* Số 1 nếu tồn tại một cặp số thoả mãn yêu cầu bài toán. -* Số 0 nếu không tồn tại cặp số nào thoả mãn yêu cầu bài toán. - -### Giới hạn - -* 0 < N < 50000 -* |K|, |ai| < 1000 với mọi i = 1, 2, …, n - -### Ví dụ - -| BAI2.INP | BAI2.OUT | -| -------------- | :------: | -| 4 5<br>0 2 6 4 | 1 | -| 3 3<br>1 2 3 | 0 | - -## Bài 3: Xâu đối xứng - -Xâu đối xứng là xâu đọc giống nhau nếu ta bắt đầu đọc từ trái qua phải hoặc từ -phải qua trái. Ví dụ, xâu `RADAR` là xâu đối xứng, xâu `TOMATO` không phải là -xâu đối xứng. - -### Yêu cầu - -Cho một xâu S gồm không quá 200 kí tự. Cho biết S có phải là xâu đối xứng hay -không? Nếu không, cho biết số kí tự ít nhất cần thêm vào S để S trở thành xâu -đối xứng. - -### Dữ liệu - -Gồm duy nhất 1 dòng ghi xâu S. - -### Kết quả - -Số k là số kí tự ít nhất cần thêm vào S để S trở thành xâu đối xứng. Nếu xâu S -đã cho là đối xứng thì ghi k = 0. - -### Ví dụ - -| BAI3.INP | BAI3.OUT | -| :------: | :------: | -| RADAR | 0 | -| TOMATO | 3 | - -## Bài 4: Biểu thức Zero - -Cuội viết liên tiếp các số tự nhiên từ 1 đến N thành dãy: 1 2 3 … N. Cuội đố -Bờm điền các dấu phép toán + hoặc - vào giữa 2 số tự nhiên liên tiếp sao cho -biểu thức thu được có kết quả bằng 0. - -### Yêu cầu - -Bạn hãy giúp Bờm viết chương trình liệt kê tất cả các cách điền dấu phép toán -thích hợp. - -### Dữ liệu - -Gồm 1 dòng duy nhất ghi số N (N < 10). - -### Kết quả - -* Dòng đầu tiên ghi số M là số cách điền dấu vào biểu thức. -* M dòng tiếp theo, mỗi dòng ghi một kết quả tìm được. - -### Ví dụ - -| BAI4.INP | BAI4.OUT | -| :------: | ------------ | -| 2 | 0 | -| 3 | 1<br>1+2-3=0 | - -## Bài 5: Miền 0 - -Cho một hình chữ nhật gồm M hàng, N cột, được chia thành MxN ô vuông. Mỗi ô -vuông được ghi một trong hai số nguyên 0 hoặc 1. - -Miền 0 là một miền liên tục các số 0 thuộc các ô chung cạnh với nhau. Diện tích -miền là số lượng các ô vuông cùng giá trị thuộc miền đó. - -### Yêu cầu - -Tính diện tích miền 0 lớn nhất của hình chữ nhật đã cho. - -### Dữ liệu - -* Dòng đầu tiên ghi hai số M, N. -* M dòng tiếp theo, mỗi dòng ghi N số lần lượt là giá trị các ô trong bảng số. - -### Kết quả - -Số nguyên duy nhất là diện tích miền 0 lớn nhất. - -### Giới hạn - -1 < M, N < 100. - -### Ví dụ - -| BAI5.INP | BAI5.OUT | -| ------------------------------------ | :------: | -| 3 4<br>0 0 0 1<br>1 1 0 1<br>0 0 1 0 | 4 | diff --git a/12/TP-ThanhHoá-2009/bai1.pas b/12/TP-ThanhHoá-2009/bai1.pas deleted file mode 100644 index 511d074..0000000 --- a/12/TP-ThanhHoá-2009/bai1.pas +++ /dev/null @@ -1,39 +0,0 @@ -var - prime: array[1..4999] of boolean; - n, i, k, a, j: word; - f: text; - -begin - fillchar(prime, sizeof(prime), true); - prime[1] := false; - - for i := 2 to 70 do - if prime[i] then - for j := 2 to 4999 div i do - prime[i * j] := false; - - for i := 1 to 4999 do - if prime[i] then - writeln(i); - - assign(f, 'BAI1.INP'); - reset(f); - - readln(f, n, k); - - j := 0; - for i := 1 to n do - begin - read(f, a); - if (a < k) and - prime[a] then - inc(j) - end; - - close(f); - - assign(f, 'BAI1.OUT'); - rewrite(f); - writeln(f, j); - close(f) -end. diff --git a/12/TP-ThanhHoá-2009/bai2.pas b/12/TP-ThanhHoá-2009/bai2.pas deleted file mode 100644 index 5b43c06..0000000 --- a/12/TP-ThanhHoá-2009/bai2.pas +++ /dev/null @@ -1,41 +0,0 @@ -var - n: word; - k, a: smallint; - f: text; - b: array[-999..999] of byte; - - -function libai2(): byte; - var - i: smallint; - - begin - for i := -999 to k - 1 do - if (b[i] > 0) and - (b[k * 2 - i] > 0) then - exit(1); - - if b[k] > 1 then - exit(1); - - exit(0) - end; - - -begin - assign(f, 'BAI2.INP'); - reset(f); - readln(f, n, k); - fillchar(b, sizeof(b), 0); - repeat - read(f, a); - inc(b[a]); - dec(n) - until n = 0; - close(f); - - assign(f, 'BAI2.OUT'); - rewrite(f); - writeln(f, libai2()); - close(f) -end. diff --git a/12/TP-ThanhHoá-2009/bai3.pas b/12/TP-ThanhHoá-2009/bai3.pas deleted file mode 100644 index a98141e..0000000 --- a/12/TP-ThanhHoá-2009/bai3.pas +++ /dev/null @@ -1,44 +0,0 @@ -var - f: text; - s: string; - min: byte = 255; - - -procedure palen( - s: string; - tmp: smallint -); - - begin - if tmp + length(s) >= min then - exit; - - if length(s) < 2 then - begin - min := tmp + length(s); - exit - end; - - if s[1] = s[length(s)] then - palen(copy(s, 2, length(s) - 2), tmp + 2) - else - begin - palen(copy(s, 2, length(s) - 1), tmp + 2); - palen(copy(s, 1, length(s) - 1), tmp + 2) - end - end; - - -begin - assign(f, 'BAI3.INP'); - reset(f); - read(f, s); - close(f); - - palen(s, -length(s)); - - assign(f, 'BAI3.OUT'); - rewrite(f); - writeln(f, min); - close(f) -end. diff --git a/12/TP-ThanhHoá-2009/bai4.pas b/12/TP-ThanhHoá-2009/bai4.pas deleted file mode 100644 index 04839af..0000000 --- a/12/TP-ThanhHoá-2009/bai4.pas +++ /dev/null @@ -1,72 +0,0 @@ -var - f: text; - n, i: shortint; - a: array of string; - - -function minus(num, bit: shortint): boolean; - begin - minus := num shr bit mod 2 = 1 - end; - - -function cal(n, b: shortint): boolean; - var - i, s: shortint; - - begin - s := 0; - - for i := 2 to n do - if minus(b, n - i) then - s := s - i - else - s := s + i; - - cal := s = -1 - end; - - -function equa(n, b: shortint): string; - var - i: shortint; - - begin - equa := '1'; - - for i := 2 to n do - begin - if minus(b, n - i) then - equa := equa + '-' - else - equa := equa + '+'; - - equa := equa + char(i + 48) - end; - - equa := equa + '=0' - end; - - -begin - assign(f, 'BAI4.INP'); - reset(f); - readln(f, n); - close(f); - setlength(a, 0); - - if n mod 4 mod 3 = 0 then - for i := 1 to 1 shl (n - 1) - 1 do - if cal(n, i) then - begin - setlength(a, length(a) + 1); - a[length(a) - 1] := equa(n, i) - end; - - assign(f, 'BAI4.OUT'); - rewrite(f); - writeln(f, length(a)); - for i := 0 to length(a) - 1 do - writeln(f, a[i]); - close(f) -end. diff --git a/12/TP-ThanhHoá-2009/bai4.py b/12/TP-ThanhHoá-2009/bai4.py deleted file mode 100644 index f5c5a26..0000000 --- a/12/TP-ThanhHoá-2009/bai4.py +++ /dev/null @@ -1,28 +0,0 @@ -#!/usr/bin/env python3 - - -def ops(number, length): - b = bin(number)[2:] - return '+' * (length - len(b)) + b.replace('0', '+').replace('1', '-') - - -def libai4(n): - seq, l = list(range(1, n + 1)), [] - - for i in range(2 ** (n - 1)): - s = ''.join(["{}{}".format(*j) for j in zip(ops(i, n), seq)])[1:] - if eval(s) == 0: - l.append(s + '=0\n') - - return l - - -if __name__ == '__main__': - with open('BAI4.INP') as f: - n = int(f.read()) - - with open('BAI4.OUT', 'w') as f: - l = libai4(n) - f.write('{}\n'.format(len(l))) - for s in l: - f.write(s) diff --git a/12/TP-ThanhHoá-2009/bai4pas_srcgen.py b/12/TP-ThanhHoá-2009/bai4pas_srcgen.py deleted file mode 100644 index e345caa..0000000 --- a/12/TP-ThanhHoá-2009/bai4pas_srcgen.py +++ /dev/null @@ -1,19 +0,0 @@ -#!/usr/bin/env python3 - -from bai4 import libai4 - - -with open("BAI4.PAS", "w") as f: - f.write("const\n m: array[1..9] of byte = (") - l = [libai4(i) for i in range(1, 10)] - f.write(", ".join([str(len(i)) for i in l])) - f.write(");\n equa: array[1..9] of ansistring = (\n"); - l0 = [] - for i in l: - s = " #10" + "".join(["'" + j.replace("\n", "'#10") for j in i]) - l0.append(s) - f.write(",\n".join(l0)) - f.write("\n );\n\nvar\n n: byte;\n f: text;\n\nbegin\n") - f.write(" assign(f, 'BAI4.INP');\n reset(f);\n read(f, n);\n") - f.write(" close(f);\n\n assign(f, 'BAI4.OUT');\n rewrite(f);\n") - f.write(" write(f, m[n], equa[n]);\n close(f)\nend.\n") diff --git a/12/TP-ThanhHoá-2009/bai5.pas b/12/TP-ThanhHoá-2009/bai5.pas deleted file mode 100644 index 867b9d2..0000000 --- a/12/TP-ThanhHoá-2009/bai5.pas +++ /dev/null @@ -1,112 +0,0 @@ -uses - sortnfind; - -var - f: text; - rect: array of boolean; - mem: array of intar; - m, n: byte; - tmp, i, idx0, idx1: smallint; - - -function locate(x: smallint): smallint; - var - i: smallint; - - begin - for i := 0 to length(mem) - 1 do - if binin(mem[i], x) then - exit(i) - end; - - -procedure mv( - src: intar; - var dest: intar -); - - var - lendest, lensrc, i: smallint; - - begin - lendest := length(dest); - lensrc := length(src); - setlength(dest, lendest + lensrc); - - for i := 0 to lensrc - 1 do - dest[i + lendest] := src[i]; - - setlength(src, 0); - qsort(dest) - end; - - -begin - assign(f, 'BAI5.INP'); - reset(f); - readln(f, m, n); - setlength(rect, m * n); - - for i := 0 to m * n - 1 do - begin - read(f, tmp); - - if tmp = 0 then - rect[i] := true - else - rect[i] := false - end; - close(f); - - setlength(mem, 0); - - for i := 0 to m * n - 1 do - if rect[i] then - begin - idx0 := -1; - idx1 := -1; - - if (i > 0) and rect[i - 1] then - idx0 := locate(i - 1); - - if (i >= n) and rect[i - n] then - if idx0 = -1 then - idx0 := locate(i - n) - else - begin - tmp := locate(i - n); - - if tmp < idx0 then - begin - idx1 := idx0; - idx0 := tmp - end - else if tmp > idx0 then - idx1 := tmp - end; - - if idx0 + idx1 = -2 then - begin - setlength(mem, length(mem) + 1); - setlength(mem[length(mem) - 1], 1); - mem[length(mem) - 1][0] := i; - continue - end; - - setlength(mem[idx0], length(mem[idx0]) + 1); - mem[idx0][length(mem[idx0]) - 1] := i; - - if idx1 > 0 then - mv(mem[idx1], mem[idx0]) - end; - - tmp := 0; - for i := 0 to length(mem) - 1 do - if length(mem[i]) > tmp then - tmp := length(mem[i]); - - assign(f, 'BAI5.OUT'); - rewrite(f); - writeln(f, tmp); - close(f) -end. diff --git a/12/TP-ThanhHoá-2009/sortnfind.pas b/12/TP-ThanhHoá-2009/sortnfind.pas deleted file mode 100644 index 52e8d6b..0000000 --- a/12/TP-ThanhHoá-2009/sortnfind.pas +++ /dev/null @@ -1,83 +0,0 @@ -unit sortnfind; - -interface - - type - intar = array of smallint; - - procedure qsort(var a : intar); - - function binin( - a: intar; - x: smallint - ): boolean; - -implementation - - procedure qsort(var a : intar); - - procedure sort(l, r: longint); - var - i, j, x, y: longint; - - begin - i := l; - j := r; - x := a[(l + r) div 2]; - - repeat - while a[i] < x do - inc(i); - - while x < a[j] do - dec(j); - - if i <= j then - begin - y := a[i]; - a[i] := a[j]; - a[j] := y; - inc(i); - j := j - 1 - end - until i > j; - - if l < j then - sort(l, j); - - if i < r then - sort(i, r) - end; - - begin - sort(0, length(a) - 1) - end; - - - function binin( - a: intar; - x: smallint - ): boolean; - - var - l, h, mid: word; - - begin - l := 0; - h := length(a) - 1; - - while l <= h do - begin - mid := (l + h) div 2; - if x = a[mid] then - exit(true) - else if x < a[mid] then - h := mid - 1 - else - l := mid + 1 - end; - - binin := false - end; - -end. |