From 2f674dc80f0382f1c3178f435714960734dc9d3c Mon Sep 17 00:00:00 2001 From: Nguyễn Gia Phong Date: Sat, 6 Jun 2020 21:33:13 +0700 Subject: Reorganize stuff from secondary school --- .../README.md" | 67 ++++++++ .../cau1.c" | 20 +++ .../cau2.c" | 39 +++++ .../cau3.c" | 40 +++++ .../cau4.c" | 26 ++++ 2ndary/12/QG-2007/README.md | 43 +++++ 2ndary/12/QG-2007/maxiseq.c | 36 +++++ 2ndary/12/QG-2008/README.md | 36 +++++ 2ndary/12/QG-2008/seqgame.cpp | 59 +++++++ 2ndary/12/QG-2014/QG-2014.pdf | Bin 0 -> 4181536 bytes 2ndary/12/QG-2014/ballgame.lisp | 49 ++++++ 2ndary/12/QG-2014/minroad.c | 69 ++++++++ 2ndary/12/QG-2017/README.md | 80 ++++++++++ 2ndary/12/QG-2017/virus.c | 94 +++++++++++ 2ndary/12/TP-HN-2008/R1/BL1.PAS | 26 ++++ 2ndary/12/TP-HN-2008/R1/BL2.PAS | 57 +++++++ 2ndary/12/TP-HN-2008/R1/BL3.PAS | 45 ++++++ 2ndary/12/TP-HN-2008/R1/BL4.pas | 62 ++++++++ 2ndary/12/TP-HN-2008/R1/CLB.IN | 4 + 2ndary/12/TP-HN-2008/R1/CLB.OU | 0 2ndary/12/TP-HN-2008/R1/R1.DOC | Bin 0 -> 79872 bytes 2ndary/12/TP-HN-2008/R2/README.md | 115 ++++++++++++++ 2ndary/12/TP-HN-2008/R2/dg.c | 102 ++++++++++++ 2ndary/12/TP-HN-2008/R2/hc.cpp | 73 +++++++++ 2ndary/12/TP-HN-2008/R2/tbc.pas | 69 ++++++++ 2ndary/12/TP-HN-2009/R1/BTN.PAS | 87 +++++++++++ 2ndary/12/TP-HN-2009/R1/HEXA.PAS | 75 +++++++++ 2ndary/12/TP-HN-2009/R1/PS.PAS | 80 ++++++++++ 2ndary/12/TP-HN-2009/R1/R1.pdf | Bin 0 -> 65142 bytes 2ndary/12/TP-HN-2009/R2/BAI1.PAS | 90 +++++++++++ 2ndary/12/TP-HN-2009/R2/BAI2.CPP | 58 +++++++ 2ndary/12/TP-HN-2009/R2/BAI3.PAS | 87 +++++++++++ 2ndary/12/TP-HN-2009/R2/R2.pdf | Bin 0 -> 103168 bytes 2ndary/12/TP-HN-2010/BAI1.PAS | 30 ++++ 2ndary/12/TP-HN-2010/BAI2.PAS | 40 +++++ 2ndary/12/TP-HN-2010/BAI3 | Bin 0 -> 132580 bytes 2ndary/12/TP-HN-2010/BAI3.INP | 1 + 2ndary/12/TP-HN-2010/BAI3.OUT | 0 2ndary/12/TP-HN-2010/BAI3.o | Bin 0 -> 4344 bytes 2ndary/12/TP-HN-2010/BAI3.pas | 73 +++++++++ 2ndary/12/TP-HN-2010/README.md | 1 + 2ndary/12/TP-HN-2010/TP-2010.png | Bin 0 -> 1251665 bytes 2ndary/12/TP-HN-2010/_BAI3.pas | 73 +++++++++ 2ndary/12/TP-HN-2015/README.md | 83 ++++++++++ 2ndary/12/TP-HN-2015/bai1.pas | 38 +++++ 2ndary/12/TP-HN-2015/bai2.pas | 54 +++++++ "2ndary/12/TP-ThanhHo\303\241-2009/BAI4.PAS" | 29 ++++ "2ndary/12/TP-ThanhHo\303\241-2009/README.md" | 173 +++++++++++++++++++++ "2ndary/12/TP-ThanhHo\303\241-2009/bai1.pas" | 39 +++++ "2ndary/12/TP-ThanhHo\303\241-2009/bai2.pas" | 41 +++++ "2ndary/12/TP-ThanhHo\303\241-2009/bai3.pas" | 44 ++++++ "2ndary/12/TP-ThanhHo\303\241-2009/bai4.pas" | 72 +++++++++ "2ndary/12/TP-ThanhHo\303\241-2009/bai4.py" | 28 ++++ .../12/TP-ThanhHo\303\241-2009/bai4pas_srcgen.py" | 19 +++ "2ndary/12/TP-ThanhHo\303\241-2009/bai5.pas" | 112 +++++++++++++ "2ndary/12/TP-ThanhHo\303\241-2009/sortnfind.pas" | 83 ++++++++++ 56 files changed, 2721 insertions(+) create mode 100644 "2ndary/12/Q-V\304\251nhT\306\260\341\273\235ng-2006/README.md" create mode 100644 "2ndary/12/Q-V\304\251nhT\306\260\341\273\235ng-2006/cau1.c" create mode 100644 "2ndary/12/Q-V\304\251nhT\306\260\341\273\235ng-2006/cau2.c" create mode 100644 "2ndary/12/Q-V\304\251nhT\306\260\341\273\235ng-2006/cau3.c" create mode 100644 "2ndary/12/Q-V\304\251nhT\306\260\341\273\235ng-2006/cau4.c" create mode 100644 2ndary/12/QG-2007/README.md create mode 100644 2ndary/12/QG-2007/maxiseq.c create mode 100644 2ndary/12/QG-2008/README.md create mode 100644 2ndary/12/QG-2008/seqgame.cpp create mode 100644 2ndary/12/QG-2014/QG-2014.pdf create mode 100644 2ndary/12/QG-2014/ballgame.lisp create mode 100644 2ndary/12/QG-2014/minroad.c create mode 100644 2ndary/12/QG-2017/README.md create mode 100644 2ndary/12/QG-2017/virus.c create mode 100644 2ndary/12/TP-HN-2008/R1/BL1.PAS create mode 100644 2ndary/12/TP-HN-2008/R1/BL2.PAS create mode 100644 2ndary/12/TP-HN-2008/R1/BL3.PAS create mode 100644 2ndary/12/TP-HN-2008/R1/BL4.pas create mode 100644 2ndary/12/TP-HN-2008/R1/CLB.IN create mode 100644 2ndary/12/TP-HN-2008/R1/CLB.OU create mode 100644 2ndary/12/TP-HN-2008/R1/R1.DOC create mode 100644 2ndary/12/TP-HN-2008/R2/README.md create mode 100644 2ndary/12/TP-HN-2008/R2/dg.c create mode 100644 2ndary/12/TP-HN-2008/R2/hc.cpp create mode 100644 2ndary/12/TP-HN-2008/R2/tbc.pas create mode 100644 2ndary/12/TP-HN-2009/R1/BTN.PAS create mode 100644 2ndary/12/TP-HN-2009/R1/HEXA.PAS create mode 100644 2ndary/12/TP-HN-2009/R1/PS.PAS create mode 100644 2ndary/12/TP-HN-2009/R1/R1.pdf create mode 100644 2ndary/12/TP-HN-2009/R2/BAI1.PAS create mode 100644 2ndary/12/TP-HN-2009/R2/BAI2.CPP create mode 100644 2ndary/12/TP-HN-2009/R2/BAI3.PAS create mode 100644 2ndary/12/TP-HN-2009/R2/R2.pdf create mode 100644 2ndary/12/TP-HN-2010/BAI1.PAS create mode 100644 2ndary/12/TP-HN-2010/BAI2.PAS create mode 100644 2ndary/12/TP-HN-2010/BAI3 create mode 100644 2ndary/12/TP-HN-2010/BAI3.INP create mode 100644 2ndary/12/TP-HN-2010/BAI3.OUT create mode 100644 2ndary/12/TP-HN-2010/BAI3.o create mode 100644 2ndary/12/TP-HN-2010/BAI3.pas create mode 100644 2ndary/12/TP-HN-2010/README.md create mode 100644 2ndary/12/TP-HN-2010/TP-2010.png create mode 100644 2ndary/12/TP-HN-2010/_BAI3.pas create mode 100644 2ndary/12/TP-HN-2015/README.md create mode 100644 2ndary/12/TP-HN-2015/bai1.pas create mode 100644 2ndary/12/TP-HN-2015/bai2.pas create mode 100644 "2ndary/12/TP-ThanhHo\303\241-2009/BAI4.PAS" create mode 100644 "2ndary/12/TP-ThanhHo\303\241-2009/README.md" create mode 100644 "2ndary/12/TP-ThanhHo\303\241-2009/bai1.pas" create mode 100644 "2ndary/12/TP-ThanhHo\303\241-2009/bai2.pas" create mode 100644 "2ndary/12/TP-ThanhHo\303\241-2009/bai3.pas" create mode 100644 "2ndary/12/TP-ThanhHo\303\241-2009/bai4.pas" create mode 100644 "2ndary/12/TP-ThanhHo\303\241-2009/bai4.py" create mode 100644 "2ndary/12/TP-ThanhHo\303\241-2009/bai4pas_srcgen.py" create mode 100644 "2ndary/12/TP-ThanhHo\303\241-2009/bai5.pas" create mode 100644 "2ndary/12/TP-ThanhHo\303\241-2009/sortnfind.pas" (limited to '2ndary/12') diff --git "a/2ndary/12/Q-V\304\251nhT\306\260\341\273\235ng-2006/README.md" "b/2ndary/12/Q-V\304\251nhT\306\260\341\273\235ng-2006/README.md" new file mode 100644 index 0000000..c96c99e --- /dev/null +++ "b/2ndary/12/Q-V\304\251nhT\306\260\341\273\235ng-2006/README.md" @@ -0,0 +1,67 @@ +# ĐỀ 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
8 | +| 15 | 3 5
8 12 | +| 21 | 3 7
16 | +| 70 | 2 5 7
64 | +| 150 | 2 3 5 5
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/2ndary/12/Q-V\304\251nhT\306\260\341\273\235ng-2006/cau1.c" "b/2ndary/12/Q-V\304\251nhT\306\260\341\273\235ng-2006/cau1.c" new file mode 100644 index 0000000..173e7c2 --- /dev/null +++ "b/2ndary/12/Q-V\304\251nhT\306\260\341\273\235ng-2006/cau1.c" @@ -0,0 +1,20 @@ +#include +#include + +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/2ndary/12/Q-V\304\251nhT\306\260\341\273\235ng-2006/cau2.c" "b/2ndary/12/Q-V\304\251nhT\306\260\341\273\235ng-2006/cau2.c" new file mode 100644 index 0000000..4ad1c3b --- /dev/null +++ "b/2ndary/12/Q-V\304\251nhT\306\260\341\273\235ng-2006/cau2.c" @@ -0,0 +1,39 @@ +#include +#include + +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/2ndary/12/Q-V\304\251nhT\306\260\341\273\235ng-2006/cau3.c" "b/2ndary/12/Q-V\304\251nhT\306\260\341\273\235ng-2006/cau3.c" new file mode 100644 index 0000000..136f154 --- /dev/null +++ "b/2ndary/12/Q-V\304\251nhT\306\260\341\273\235ng-2006/cau3.c" @@ -0,0 +1,40 @@ +#include +#include + +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/2ndary/12/Q-V\304\251nhT\306\260\341\273\235ng-2006/cau4.c" "b/2ndary/12/Q-V\304\251nhT\306\260\341\273\235ng-2006/cau4.c" new file mode 100644 index 0000000..d971927 --- /dev/null +++ "b/2ndary/12/Q-V\304\251nhT\306\260\341\273\235ng-2006/cau4.c" @@ -0,0 +1,26 @@ +#include +#include + +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/2ndary/12/QG-2007/README.md b/2ndary/12/QG-2007/README.md new file mode 100644 index 0000000..d32a8be --- /dev/null +++ b/2ndary/12/QG-2007/README.md @@ -0,0 +1,43 @@ +# 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 a1, a2, …, an. + +Dãy số ai, ai+1, …, aj thỏa mãn ai +≤ ai+1 ≤ … ≤ aj 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ố (uk) xác định bởi: + +* u1 = 1; +* uk = uk-1 + 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 ai là + số hạng thứ i của dãy số đã cho (ai ≤ 108, 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
2
2007
6
6
15
16
3
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 +(uk) là: 6, 6, 15 và 3, 21 (vì u2 = 3, u3 = 6, +u5 = 15, u6 = 21). Dãy cần tìm là 6, 6, 15 có độ dài là +3. diff --git a/2ndary/12/QG-2007/maxiseq.c b/2ndary/12/QG-2007/maxiseq.c new file mode 100644 index 0000000..94c15c8 --- /dev/null +++ b/2ndary/12/QG-2007/maxiseq.c @@ -0,0 +1,36 @@ +#include +#include + +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/2ndary/12/QG-2008/README.md b/2ndary/12/QG-2008/README.md new file mode 100644 index 0000000..4327b5d --- /dev/null +++ b/2ndary/12/QG-2008/README.md @@ -0,0 +1,36 @@ +# 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à: +b1, b2, …, bn; còn dãy số mà bạn thứ hai chọn +là: c1, c2, …, cn. 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 +bi (1 ≤ i ≤ n), còn bạn thứ hai đưa ra số hạng cj (1 ≤ j +≤ n) thì giá của lượt chơi đó sẽ là |bi + cj|. + +### 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 b1, b2, …, + bn (|bi| ≤ 109, i = 1, 2, …, n); +* Dòng thứ ba chứa dãy số nguyên c1, c2, …, + cn (|ci| ≤ 109, 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
1 -2
2 3 | 0 | + +*60% số tests ứng với 60% số điểm của bài có 1 ≤ n ≤ 1000.* diff --git a/2ndary/12/QG-2008/seqgame.cpp b/2ndary/12/QG-2008/seqgame.cpp new file mode 100644 index 0000000..b1751c7 --- /dev/null +++ b/2ndary/12/QG-2008/seqgame.cpp @@ -0,0 +1,59 @@ +#include +#include +#include + +#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 b; + std::set::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/2ndary/12/QG-2014/QG-2014.pdf b/2ndary/12/QG-2014/QG-2014.pdf new file mode 100644 index 0000000..f9c6864 Binary files /dev/null and b/2ndary/12/QG-2014/QG-2014.pdf differ diff --git a/2ndary/12/QG-2014/ballgame.lisp b/2ndary/12/QG-2014/ballgame.lisp new file mode 100644 index 0000000..765d85c --- /dev/null +++ b/2ndary/12/QG-2014/ballgame.lisp @@ -0,0 +1,49 @@ +(defun normalize-line (line) + (if (or (and (= (first line) 0) (< (second line) 0)) + (< (first line) 0)) + (mapcar #'- line) + line)) + +(defun make-line (x1 x2 y1 y2) + (let* ((a (- y2 y1)) + (b (- x1 x2)) + (c (+ (* a x1) (* b y1))) + (g (gcd a b c))) + (normalize-line (mapcar (lambda (x) (/ x g)) (list a b c))))) + +(defun extract-result (first-pair second-pair) + (let ((triple (union first-pair second-pair))) + (if (= (length triple) 3) + (format nil "~a~a~a" (first triple) (second triple) (third triple)) + (format nil "~{~a ~}~a" first-pair (first second-pair))))) + +(with-open-file (instream "BALLGAME.INP") + (let ((n (read instream))) + (labels ((read-blues (m result) + (if (<= m n) + (let* ((x (read instream)) (y (read instream))) + (read-blues (1+ m) (cons (list m x y) result))) + result))) + (let ((blues (read-blues 1 '())) + (lines (make-hash-table :test 'equal))) + (labels ((process-reds (m) + (if (<= m n) + (let* ((x (read instream)) + (y (read instream)) + (result + (dolist (blue blues nil) + (let* ((line (make-line x (second blue) + y (third blue))) + (this-pair (list (first blue) (+ m n))) + (that-pair (gethash line lines))) + (if (null that-pair) + (setf (gethash line lines) this-pair) + (return (extract-result this-pair + that-pair))))))) + (cond (result) + (t (process-reds (1+ m))))) + "-1"))) + (with-open-file (outstream "BALLGAME.OUT" :direction :output + :if-exists :supersede) + (princ (process-reds 1) outstream) + (fresh-line outstream))))))) diff --git a/2ndary/12/QG-2014/minroad.c b/2ndary/12/QG-2014/minroad.c new file mode 100644 index 0000000..d4bc129 --- /dev/null +++ b/2ndary/12/QG-2014/minroad.c @@ -0,0 +1,69 @@ +#include +#include + +struct trees { + long d, a, b; +}; + +int cmp(const void *x, const void *y) +{ + long d = ((struct trees *) x)->d - ((struct trees *) y)->d; + if (d < 0) + return -1; + else if (d > 0) + return 1; + else + return 0; +} + +int main() +{ + FILE *f = fopen("MINROAD.INP", "r"); + long n, a, b; + fscanf(f, "%ld %ld %ld\n", &n, &a, &b); + + struct trees *t = (struct trees *) malloc(n * sizeof(struct trees)); + long k; + for (long i = 0; i < n; i++) { + fscanf(f, "%ld %ld\n", &t[i].d, &k); + if (k == 1) { + t[i].a = 1; + t[i].b = 0; + } else { + t[i].a = 0; + t[i].b = 1; + } + } + fclose(f); + + qsort(t, n, sizeof(struct trees), cmp); + for (long i = 1; i < n; i++) { + t[i].a += t[i - 1].a; + t[i].b += t[i - 1].b; + } + + struct trees *enough = t; + for (k = n; k > 0 && (enough->a < a || enough->b < b); k--) + enough++; + + long d0 = -1, d1, maxa, maxb; + for (; k--; enough++) { + maxa = enough->a - a; + maxb = enough->b - b; + while (t->a <= maxa && t->b <= maxb) { + t++; + n--; + } + + d1 = d0; + d0 = enough->d - t->d; + if (d1 != -1 && d1 < d0) + d0 = d1; + } + + f = fopen("MINROAD.OUT", "w"); + fprintf(f, "%ld\n", d0); + fclose(f); + + return 0; +} diff --git a/2ndary/12/QG-2017/README.md b/2ndary/12/QG-2017/README.md new file mode 100644 index 0000000..9b79939 --- /dev/null +++ b/2ndary/12/QG-2017/README.md @@ -0,0 +1,80 @@ +# 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*1, *k*2, +…, *kn*. Với mỗi giá trị *ki*, 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 *ki* (*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 + *ki* (*ki* ≤ 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 *ki* , *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; *ki* = 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
zabaaxy
0
1 | 1
2 | +| 2
zcaabcaaaa
0
1 | 2
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/2ndary/12/QG-2017/virus.c b/2ndary/12/QG-2017/virus.c new file mode 100644 index 0000000..add408c --- /dev/null +++ b/2ndary/12/QG-2017/virus.c @@ -0,0 +1,94 @@ +#include +#include +#include + +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/2ndary/12/TP-HN-2008/R1/BL1.PAS b/2ndary/12/TP-HN-2008/R1/BL1.PAS new file mode 100644 index 0000000..6931b1b --- /dev/null +++ b/2ndary/12/TP-HN-2008/R1/BL1.PAS @@ -0,0 +1,26 @@ +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/2ndary/12/TP-HN-2008/R1/BL2.PAS b/2ndary/12/TP-HN-2008/R1/BL2.PAS new file mode 100644 index 0000000..e228240 --- /dev/null +++ b/2ndary/12/TP-HN-2008/R1/BL2.PAS @@ -0,0 +1,57 @@ +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/2ndary/12/TP-HN-2008/R1/BL3.PAS b/2ndary/12/TP-HN-2008/R1/BL3.PAS new file mode 100644 index 0000000..a49b4d6 --- /dev/null +++ b/2ndary/12/TP-HN-2008/R1/BL3.PAS @@ -0,0 +1,45 @@ +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/2ndary/12/TP-HN-2008/R1/BL4.pas b/2ndary/12/TP-HN-2008/R1/BL4.pas new file mode 100644 index 0000000..c552b0d --- /dev/null +++ b/2ndary/12/TP-HN-2008/R1/BL4.pas @@ -0,0 +1,62 @@ +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/2ndary/12/TP-HN-2008/R1/CLB.IN b/2ndary/12/TP-HN-2008/R1/CLB.IN new file mode 100644 index 0000000..662c775 --- /dev/null +++ b/2ndary/12/TP-HN-2008/R1/CLB.IN @@ -0,0 +1,4 @@ +3 +7 9 +3 8 +10 20 diff --git a/2ndary/12/TP-HN-2008/R1/CLB.OU b/2ndary/12/TP-HN-2008/R1/CLB.OU new file mode 100644 index 0000000..e69de29 diff --git a/2ndary/12/TP-HN-2008/R1/R1.DOC b/2ndary/12/TP-HN-2008/R1/R1.DOC new file mode 100644 index 0000000..5e29da2 Binary files /dev/null and b/2ndary/12/TP-HN-2008/R1/R1.DOC differ diff --git a/2ndary/12/TP-HN-2008/R2/README.md b/2ndary/12/TP-HN-2008/R2/README.md new file mode 100644 index 0000000..00ccc3e --- /dev/null +++ b/2ndary/12/TP-HN-2008/R2/README.md @@ -0,0 +1,115 @@ +# 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 a1, a2, …, an. Số +ap (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 ap += (ai + aj + ak) / 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 ai + (|ai| < 108). + +### 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
4
3
6
3
5 | 2 | +| 3
1
2
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à ai, j. + +### 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à ai, j ≤ 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
2 1 9 1
5 0 3 4
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á 105. 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à (x1, +y1) và (x2, y2) trong đó x1, +y1, x2, y2 là các số nguyên và có giá trị +tuyệt đối không vượt quá 106. 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 x1, y1, x2, + y2. + +### 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
0 1
1 0
0 -1
-1 0
-2 0 0 0 | 100 | diff --git a/2ndary/12/TP-HN-2008/R2/dg.c b/2ndary/12/TP-HN-2008/R2/dg.c new file mode 100644 index 0000000..e2422df --- /dev/null +++ b/2ndary/12/TP-HN-2008/R2/dg.c @@ -0,0 +1,102 @@ +#include +#include + +#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/2ndary/12/TP-HN-2008/R2/hc.cpp b/2ndary/12/TP-HN-2008/R2/hc.cpp new file mode 100644 index 0000000..1ea6ee3 --- /dev/null +++ b/2ndary/12/TP-HN-2008/R2/hc.cpp @@ -0,0 +1,73 @@ +#include +#include +#include +#include +#include + +#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, greater> 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/2ndary/12/TP-HN-2008/R2/tbc.pas b/2ndary/12/TP-HN-2008/R2/tbc.pas new file mode 100644 index 0000000..1a26a91 --- /dev/null +++ b/2ndary/12/TP-HN-2008/R2/tbc.pas @@ -0,0 +1,69 @@ +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/2ndary/12/TP-HN-2009/R1/BTN.PAS b/2ndary/12/TP-HN-2009/R1/BTN.PAS new file mode 100644 index 0000000..dbb022d --- /dev/null +++ b/2ndary/12/TP-HN-2009/R1/BTN.PAS @@ -0,0 +1,87 @@ +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/2ndary/12/TP-HN-2009/R1/HEXA.PAS b/2ndary/12/TP-HN-2009/R1/HEXA.PAS new file mode 100644 index 0000000..a2fd6ca --- /dev/null +++ b/2ndary/12/TP-HN-2009/R1/HEXA.PAS @@ -0,0 +1,75 @@ +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/2ndary/12/TP-HN-2009/R1/PS.PAS b/2ndary/12/TP-HN-2009/R1/PS.PAS new file mode 100644 index 0000000..6cf2d09 --- /dev/null +++ b/2ndary/12/TP-HN-2009/R1/PS.PAS @@ -0,0 +1,80 @@ +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/2ndary/12/TP-HN-2009/R1/R1.pdf b/2ndary/12/TP-HN-2009/R1/R1.pdf new file mode 100644 index 0000000..b0834b3 Binary files /dev/null and b/2ndary/12/TP-HN-2009/R1/R1.pdf differ diff --git a/2ndary/12/TP-HN-2009/R2/BAI1.PAS b/2ndary/12/TP-HN-2009/R2/BAI1.PAS new file mode 100644 index 0000000..b28ae0b --- /dev/null +++ b/2ndary/12/TP-HN-2009/R2/BAI1.PAS @@ -0,0 +1,90 @@ +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/2ndary/12/TP-HN-2009/R2/BAI2.CPP b/2ndary/12/TP-HN-2009/R2/BAI2.CPP new file mode 100644 index 0000000..a47760f --- /dev/null +++ b/2ndary/12/TP-HN-2009/R2/BAI2.CPP @@ -0,0 +1,58 @@ +#include +#include +#include +#include +#include +#include + +#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> 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, greater> 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/2ndary/12/TP-HN-2009/R2/BAI3.PAS b/2ndary/12/TP-HN-2009/R2/BAI3.PAS new file mode 100644 index 0000000..30eecdf --- /dev/null +++ b/2ndary/12/TP-HN-2009/R2/BAI3.PAS @@ -0,0 +1,87 @@ +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/2ndary/12/TP-HN-2009/R2/R2.pdf b/2ndary/12/TP-HN-2009/R2/R2.pdf new file mode 100644 index 0000000..7af542a Binary files /dev/null and b/2ndary/12/TP-HN-2009/R2/R2.pdf differ diff --git a/2ndary/12/TP-HN-2010/BAI1.PAS b/2ndary/12/TP-HN-2010/BAI1.PAS new file mode 100644 index 0000000..029201d --- /dev/null +++ b/2ndary/12/TP-HN-2010/BAI1.PAS @@ -0,0 +1,30 @@ +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/2ndary/12/TP-HN-2010/BAI2.PAS b/2ndary/12/TP-HN-2010/BAI2.PAS new file mode 100644 index 0000000..d6639df --- /dev/null +++ b/2ndary/12/TP-HN-2010/BAI2.PAS @@ -0,0 +1,40 @@ +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/2ndary/12/TP-HN-2010/BAI3 b/2ndary/12/TP-HN-2010/BAI3 new file mode 100644 index 0000000..7b83e7b Binary files /dev/null and b/2ndary/12/TP-HN-2010/BAI3 differ diff --git a/2ndary/12/TP-HN-2010/BAI3.INP b/2ndary/12/TP-HN-2010/BAI3.INP new file mode 100644 index 0000000..3609812 --- /dev/null +++ b/2ndary/12/TP-HN-2010/BAI3.INP @@ -0,0 +1 @@ +5 5 0 diff --git a/2ndary/12/TP-HN-2010/BAI3.OUT b/2ndary/12/TP-HN-2010/BAI3.OUT new file mode 100644 index 0000000..e69de29 diff --git a/2ndary/12/TP-HN-2010/BAI3.o b/2ndary/12/TP-HN-2010/BAI3.o new file mode 100644 index 0000000..7706cd6 Binary files /dev/null and b/2ndary/12/TP-HN-2010/BAI3.o differ diff --git a/2ndary/12/TP-HN-2010/BAI3.pas b/2ndary/12/TP-HN-2010/BAI3.pas new file mode 100644 index 0000000..aedf9a0 --- /dev/null +++ b/2ndary/12/TP-HN-2010/BAI3.pas @@ -0,0 +1,73 @@ +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/2ndary/12/TP-HN-2010/README.md b/2ndary/12/TP-HN-2010/README.md new file mode 100644 index 0000000..625312d --- /dev/null +++ b/2ndary/12/TP-HN-2010/README.md @@ -0,0 +1 @@ +![](TP-2010.png) diff --git a/2ndary/12/TP-HN-2010/TP-2010.png b/2ndary/12/TP-HN-2010/TP-2010.png new file mode 100644 index 0000000..7eacc66 Binary files /dev/null and b/2ndary/12/TP-HN-2010/TP-2010.png differ diff --git a/2ndary/12/TP-HN-2010/_BAI3.pas b/2ndary/12/TP-HN-2010/_BAI3.pas new file mode 100644 index 0000000..09ec0ca --- /dev/null +++ b/2ndary/12/TP-HN-2010/_BAI3.pas @@ -0,0 +1,73 @@ +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/2ndary/12/TP-HN-2015/README.md b/2ndary/12/TP-HN-2015/README.md new file mode 100644 index 0000000..2ba87d2 --- /dev/null +++ b/2ndary/12/TP-HN-2015/README.md @@ -0,0 +1,83 @@ +# 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 +105). + +### 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 ai (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 ai (1 ≤ ai ≤ 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 bj, cj (1 ≤ + bj, cj ≤ 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/2ndary/12/TP-HN-2015/bai1.pas b/2ndary/12/TP-HN-2015/bai1.pas new file mode 100644 index 0000000..312f2b4 --- /dev/null +++ b/2ndary/12/TP-HN-2015/bai1.pas @@ -0,0 +1,38 @@ +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/2ndary/12/TP-HN-2015/bai2.pas b/2ndary/12/TP-HN-2015/bai2.pas new file mode 100644 index 0000000..858d2b1 --- /dev/null +++ b/2ndary/12/TP-HN-2015/bai2.pas @@ -0,0 +1,54 @@ +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/2ndary/12/TP-ThanhHo\303\241-2009/BAI4.PAS" "b/2ndary/12/TP-ThanhHo\303\241-2009/BAI4.PAS" new file mode 100644 index 0000000..8706032 --- /dev/null +++ "b/2ndary/12/TP-ThanhHo\303\241-2009/BAI4.PAS" @@ -0,0 +1,29 @@ +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/2ndary/12/TP-ThanhHo\303\241-2009/README.md" "b/2ndary/12/TP-ThanhHo\303\241-2009/README.md" new file mode 100644 index 0000000..f5d69a1 --- /dev/null +++ "b/2ndary/12/TP-ThanhHo\303\241-2009/README.md" @@ -0,0 +1,173 @@ +# 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 a1, a2, …, +aN 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, ai < 5000 với mọi i = 1, 2, …, N + +### Ví dụ + +| BAI1.INP | BAI1.OUT | +| --------------------- | :------: | +| 7 8
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 a1, a2, …, an 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ố a1, a2, …, + an. 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
0 2 6 4 | 1 | +| 3 3
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
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
0 0 0 1
1 1 0 1
0 0 1 0 | 4 | diff --git "a/2ndary/12/TP-ThanhHo\303\241-2009/bai1.pas" "b/2ndary/12/TP-ThanhHo\303\241-2009/bai1.pas" new file mode 100644 index 0000000..511d074 --- /dev/null +++ "b/2ndary/12/TP-ThanhHo\303\241-2009/bai1.pas" @@ -0,0 +1,39 @@ +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/2ndary/12/TP-ThanhHo\303\241-2009/bai2.pas" "b/2ndary/12/TP-ThanhHo\303\241-2009/bai2.pas" new file mode 100644 index 0000000..5b43c06 --- /dev/null +++ "b/2ndary/12/TP-ThanhHo\303\241-2009/bai2.pas" @@ -0,0 +1,41 @@ +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/2ndary/12/TP-ThanhHo\303\241-2009/bai3.pas" "b/2ndary/12/TP-ThanhHo\303\241-2009/bai3.pas" new file mode 100644 index 0000000..a98141e --- /dev/null +++ "b/2ndary/12/TP-ThanhHo\303\241-2009/bai3.pas" @@ -0,0 +1,44 @@ +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/2ndary/12/TP-ThanhHo\303\241-2009/bai4.pas" "b/2ndary/12/TP-ThanhHo\303\241-2009/bai4.pas" new file mode 100644 index 0000000..04839af --- /dev/null +++ "b/2ndary/12/TP-ThanhHo\303\241-2009/bai4.pas" @@ -0,0 +1,72 @@ +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/2ndary/12/TP-ThanhHo\303\241-2009/bai4.py" "b/2ndary/12/TP-ThanhHo\303\241-2009/bai4.py" new file mode 100644 index 0000000..f5c5a26 --- /dev/null +++ "b/2ndary/12/TP-ThanhHo\303\241-2009/bai4.py" @@ -0,0 +1,28 @@ +#!/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/2ndary/12/TP-ThanhHo\303\241-2009/bai4pas_srcgen.py" "b/2ndary/12/TP-ThanhHo\303\241-2009/bai4pas_srcgen.py" new file mode 100644 index 0000000..e345caa --- /dev/null +++ "b/2ndary/12/TP-ThanhHo\303\241-2009/bai4pas_srcgen.py" @@ -0,0 +1,19 @@ +#!/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/2ndary/12/TP-ThanhHo\303\241-2009/bai5.pas" "b/2ndary/12/TP-ThanhHo\303\241-2009/bai5.pas" new file mode 100644 index 0000000..867b9d2 --- /dev/null +++ "b/2ndary/12/TP-ThanhHo\303\241-2009/bai5.pas" @@ -0,0 +1,112 @@ +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/2ndary/12/TP-ThanhHo\303\241-2009/sortnfind.pas" "b/2ndary/12/TP-ThanhHo\303\241-2009/sortnfind.pas" new file mode 100644 index 0000000..52e8d6b --- /dev/null +++ "b/2ndary/12/TP-ThanhHo\303\241-2009/sortnfind.pas" @@ -0,0 +1,83 @@ +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. -- cgit 1.4.1