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 --- 2ndary/10/CSP-KT2/README.md | 164 +++++++++++++++++++++++++++++++++++++++++++ 2ndary/10/CSP-KT2/dcount.c | 27 +++++++ 2ndary/10/CSP-KT2/hamming.c | 27 +++++++ 2ndary/10/CSP-KT2/negpairs.c | 24 +++++++ 2ndary/10/CSP-KT2/sumarv.c | 19 +++++ 2ndary/10/CSP-KT2/zpairs.c | 28 ++++++++ 6 files changed, 289 insertions(+) create mode 100644 2ndary/10/CSP-KT2/README.md create mode 100644 2ndary/10/CSP-KT2/dcount.c create mode 100644 2ndary/10/CSP-KT2/hamming.c create mode 100644 2ndary/10/CSP-KT2/negpairs.c create mode 100644 2ndary/10/CSP-KT2/sumarv.c create mode 100644 2ndary/10/CSP-KT2/zpairs.c (limited to '2ndary/10/CSP-KT2') diff --git a/2ndary/10/CSP-KT2/README.md b/2ndary/10/CSP-KT2/README.md new file mode 100644 index 0000000..33f03f7 --- /dev/null +++ b/2ndary/10/CSP-KT2/README.md @@ -0,0 +1,164 @@ +# ĐỀ KIỂM TRA LỚP 10 TIN + +Trường ĐHSP Hà Nội - Trường THPT Chuyên + +Môn thi: Tin học - Ngày 01/10/2015 + +Thời gian làm bài: 180 phút + +## TỔNG QUAN VỀ ĐỀ THI + +| Bài | Tên file bài làm | Giới hạn mỗi test | Điểm | +| :---: | ---------------- | :---------------: | :--: | +| 1 | `NEGPAIRS.*` | 0.5 giây | 100 | +| 2 | `DCOUNT.*` | 0.5 giây | 100 | +| 3 | `SUMAVR.*` | 0.5 giây | 100 | +| 4 | `ZPAIRS.*` | 0.5 giây | 100 | +| 5 | `HAMMING.*` | 0.5 giây | 100 | + +Phần mở rộng `*` là PAS hay CPP tùy theo ngôn ngữ và môi trường lập trình (Free +Pascal hay CodeBlock). + +## Bài 1. CẶP SỐ ĐỐI NHAU (NEGPAIRS.*) + +Cho dãy số nguyên A = (a1, a2, ..., an). Hãy +cho biết có bao nhiêu cặp chỉ số (i, j) trong đó i ≠ j thỏa mãn ai = +−aj + +**Dữ liệu:** Vào từ thiết bị nhập chuẩn: + +* Dòng 1 chứa số nguyên dương n ≤ 106 +* Dòng 2 chứa n số nguyên a1, a2, ..., an cách + nhau bởi dấu cách (∀i: |ai| ≤ 100) + +**Kết quả:** Ghi ra thiết bị xuất chuẩn một số nguyên duy nhất là số cặp i ≠ j +thỏa mãn ai = −aj. + +**Ví dụ:** + +| Sample Input | Sample Output | +| ------------------------- | :-----------: | +| 9
-3 -2 -1 0 9 0 1 2 3 | 4 | +| 6
0 0 0 0 | 6 | + +## Bài 2. THỐNG KÊ (DCOUNT.*) + +Cho dãy số nguyên không âm A = (a1, a2, ..., +an) gồm n phần tử. + +**Yêu cầu:** Hãy đếm số lượng các giá trị khác nhau có trong dãy A và đưa ra số +lần xuất hiện của phần tử xuất hiện nhiều nhất? + +**Dữ liệu:** Vào từ thiết bị nhập chuẩn + +* Dòng đầu ghi số n (n ≤ 106) +* Dòng tiếp theo gồm n số là các phần tử của dãy A, (0 ≤ ai ≤ + 106) + +**Kết quả:** Ghi ra thiết bị xuất chuẩn gồm 2 số k và t: k là số lượng các giá +trị khác nhau và t là số lần xuất hiện của phần tử xuất hiện nhiều nhất trong +dãy đã cho. + +**Ví dụ:** + +| Sample Input | Sample Output | +| ----------------------- | ------------- | +| 8
11 2 13 4 50 2 2 3 | 6 3 | + +*Giải thích: có 6 giá trị khác nhau trong dãy là 2, 3, 4, 11, 13 và 50, số 2 +xuất hiện nhiều nhất là 3 lần.* + +## Bài 3. TRUNG BÌNH CỘNG (SUMAVR.*) + +Cho dãy số nguyên B = (b1, b2, ..., bn), hãy +tìm dãy số nguyên A = (a1, a2, ..., an) sao +cho ∀i: 1 ≤ i ≤ n trung bình cộng của i phần tử đầu tiên trong dãy A đúng bằng +bi: + +a1 + a2 + ... + an = bi x i, ∀i = +1, 2, ..., n + +**Dữ liệu:** Vào từ thiết bị nhập chuẩn: + +* Dòng 1 chứa số nguyên dương n ≤ 105 +* Dòng 2 chứa n số nguyên b1, b2, ..., bn cách + nhau bởi dấu cách (∀i: |bi| ≤ 109) + +**Kết quả:** Ghi ra thiết bị xuất chuẩn n số a1, a2, ..., +an theo đúng thứ tự cách nhau bởi dấu cách. + +**Ví dụ:** + +| Sample Input | Sample Output | +| -------------- | ------------- | +| 5
1 2 2 3 4 | 1 3 2 6 8 | + +## Bài 4. GHÉP CẶP (ZPAIRS.*) + +Cho hai dãy số A = (a1, a2, ..., an) và dãy số +B = (b1, b2, ..., bn) đã được sắp theo thứ tự +không giảm. + +Một phép ghép cặp là phép lấy một phần tử ai của dãy A và một phần +tử bj của dãy B thành một cặp (ai, bj). Chi +phí của cặp này được tính bằng |ai − bj|. + +**Yêu cầu:** Tính xem có thể ghép tối đa được bao nhiêu cặp sao cho tổng chi +phí của các cặp = 0. Biết rằng, mỗi phần tử trong A cũng như trong B chỉ được +ghép vào một cặp duy nhất. + +**Dữ liệu:** Vào từ thiết bị nhập chuẩn: + +* Dòng 1: 2 số n, m lần lượt là số phần tử của dãy A, B (n, m ≤ 105). +* Dòng 2: gồm n số nguyên sắp theo thứ tự không giảm là dãy A = (a1, + a2, ..., an), |ai| ≤ 109. +* Dòng 3: gồm m số nguyên sắp theo thứ tự không giảm là dãy B = + ,(b1, b2, ..., bn) |bi| ≤ + 109. + +**Kết quả:** Ghi ra thiết bị xuất chuẩn gồm duy nhất một số k là số cặp ghép +lớn nhất tìm được thỏa mãn yêu cầu đề bài. + +**Ví dụ:** + +| Sample Input | Sample Output | +| --------------------------- | ------------- | +| 4 5
1 2 2 3
2 3 5 5 5 | 2 | + +## Bài 5. DÃY SỐ HAMMING (HAMMING.*) + +Dãy số nguyên dương tăng dần trong đó, phần tử đầu tiên là a1 = 1, +các phần tử tiếp theo có ước nguyên tố của mỗi số không quá 5 được gọi là dãy +hamming. Như vậy, 10 = 2 x 5 sẽ là một số trong hãy Hamming, còn 26 = 2 x 13 +không thuộc dãy hamming. + +Phần đầu của dãy Hamming là: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ... + +**Yêu cầu:** Cho một dãy gồm n số nguyên a1, a2, ..., +an (ai ≤ 109). Với mỗi số ai hãy +kiểm tra xem nó có thuộc dãy số Hamming? + +**Dữ liệu:** Vào từ thiết bị nhập chuẩn: +* Dòng đầu là số n (n ≤ 105) +* n dòng tiếp theo, mỗi dòng ghi một số nguyên của dãy a1, + a2, ..., an (ai ≤ 109). + +**Kết quả:** Ghi ra thiết bị xuất chuẩn gồm n dòng mỗi dòng gồm YES hoặc NO +tương ứng với mỗi số ai có/không thuộc dãy Hamming. + +**Ví dụ:** + +| Sample Input | Sample Output | +| ------------ | ------------- | +| 11 | YES | +| 1 | YES | +| 2 | YES | +| 6 | NO | +| 7 | YES | +| 8 | YES | +| 9 | YES | +| 10 | NO | +| 11 | YES | +| 12 | NO | +| 13 | NO | +| 14 | | diff --git a/2ndary/10/CSP-KT2/dcount.c b/2ndary/10/CSP-KT2/dcount.c new file mode 100644 index 0000000..e851210 --- /dev/null +++ b/2ndary/10/CSP-KT2/dcount.c @@ -0,0 +1,27 @@ +#include + +/* More than 8MB is used by this program, for *efficiency*. */ + +int main() +{ + long n, i, a0, m = 0, max = 0; + long a[100001] = {}, b[100001]; + + scanf("%ld", &n); + for (i = 0; i < n; i++) { + scanf("%ld", &a0); + if (!a[a0]) { + b[m] = a0; + m++; + } + a[a0]++; + } + + for (i = 0; i < m; i++) + if (a[b[i]] > max) + max = a[b[i]]; + + printf("%ld %ld\n", m, max); + + return 0; +} diff --git a/2ndary/10/CSP-KT2/hamming.c b/2ndary/10/CSP-KT2/hamming.c new file mode 100644 index 0000000..645eb17 --- /dev/null +++ b/2ndary/10/CSP-KT2/hamming.c @@ -0,0 +1,27 @@ +#include + +char *hamming(long m) +{ + while (m % 5 == 0) + m /= 5; + while (m % 3 == 0) + m /= 3; + while (m % 2 == 0) + m /= 2; + return (m > 1) ? "NO" : "YES"; +} + +int main() +{ + short n, i; + long a[10000]; + + scanf("%hd", &n); + for (i = 0; i < n; i++) + scanf("%ld", &a[i]); + + for (i = 0; i < n; i++) + printf("%s\n", hamming(a[i])); + + return 0; +} diff --git a/2ndary/10/CSP-KT2/negpairs.c b/2ndary/10/CSP-KT2/negpairs.c new file mode 100644 index 0000000..577fdf8 --- /dev/null +++ b/2ndary/10/CSP-KT2/negpairs.c @@ -0,0 +1,24 @@ +#include + +int main() +{ + long n, i; + long unsigned_a[201] = {}; + long *a = &unsigned_a[100]; + char a0; + long long v; + + scanf("%ld", &n); + for (i = 0; i < n; i++) { + scanf("%hhd", &a0); + a[a0]++; + } + + v = a[0] * (a[0] - 1) / 2; + for (i = 1; i <= 100; i++) + v += a[i] * a[-i]; + + printf("%lld\n", v); + + return 0; +} diff --git a/2ndary/10/CSP-KT2/sumarv.c b/2ndary/10/CSP-KT2/sumarv.c new file mode 100644 index 0000000..3e5bc7e --- /dev/null +++ b/2ndary/10/CSP-KT2/sumarv.c @@ -0,0 +1,19 @@ +#include + +int main() +{ + short n, i; + long b[10001] = {}; + + scanf("%hd", &n); + for (i = 1; i <= n; i++) { + scanf("%ld", &b[i]); + b[i] *= i; + } + + for (i = 1; i <= n; i++) + printf("%ld ", b[i] - b[i - 1]); + printf("\n"); + + return 0; +} diff --git a/2ndary/10/CSP-KT2/zpairs.c b/2ndary/10/CSP-KT2/zpairs.c new file mode 100644 index 0000000..d0d6186 --- /dev/null +++ b/2ndary/10/CSP-KT2/zpairs.c @@ -0,0 +1,28 @@ +#include + +int main() +{ + short m, n, i, j, v = 0; + long a[10000], b; + + scanf("%hd %hd", &n, &m); + for (i = 0; i < n; i++) + scanf("%ld", &a[i]); + + i = 0; + for (j = 0; j < m; j++) { + if (i >= n) + break; + scanf("%ld", &b); + while (b > a[i]) + i++; + if (b == a[i]) { + v++; + i++; + } + } + + printf("%hd\n", v); + + return 0; +} -- cgit 1.4.1