Reorganize stuff from secondary school

6 files changed, 289 insertions, 0 deletions

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 = (a<sub>1</sub>, a<sub>2</sub>, ..., a<sub>n</sub>). Hãy
+cho biết có bao nhiêu cặp chỉ số (i, j) trong đó i ≠ j thỏa mãn a<sub>i</sub> =
+−a<sub>j</sub>
+
+**Dữ liệu:** Vào từ thiết bị nhập chuẩn:
+
+* Dòng 1 chứa số nguyên dương n ≤ 10<sup>6</sup>
+* Dòng 2 chứa n số nguyên a<sub>1</sub>, a<sub>2</sub>, ..., a<sub>n</sub> cách
+  nhau bởi dấu cách (∀i: |a<sub>i</sub>| ≤ 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 a<sub>i</sub> = −a<sub>j</sub>.
+
+**Ví dụ:**
+
+|       Sample Input        | Sample Output |
+| ------------------------- | :-----------: |
+| 9<br>-3 -2 -1 0 9 0 1 2 3 |       4       |
+| 6<br>0 0 0 0              |       6       |
+
+## Bài 2. THỐNG KÊ (DCOUNT.*)
+
+Cho dãy số nguyên không âm A = (a<sub>1</sub>, a<sub>2</sub>, ...,
+a<sub>n</sub>) 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 ≤ 10<sup>6</sup>)
+* Dòng tiếp theo gồm n số là các phần tử của dãy A, (0 ≤ a<sub>i</sub> ≤
+  10<sup>6</sup>)
+
+**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<br>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 = (b<sub>1</sub>, b<sub>2</sub>, ..., b<sub>n</sub>), hãy
+tìm dãy số nguyên A = (a<sub>1</sub>, a<sub>2</sub>, ..., a<sub>n</sub>) 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
+b<sub>i</sub>:
+
+a<sub>1</sub> + a<sub>2</sub> + ... + a<sub>n</sub> = b<sub>i</sub> 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 ≤ 10<sup>5</sup>
+* Dòng 2 chứa n số nguyên b<sub>1</sub>, b<sub>2</sub>, ..., b<sub>n</sub> cách
+  nhau bởi dấu cách (∀i: |b<sub>i</sub>| ≤ 10<sup>9</sup>)
+
+**Kết quả:** Ghi ra thiết bị xuất chuẩn n số a<sub>1</sub>, a<sub>2</sub>, ...,
+a<sub>n</sub> theo đúng thứ tự cách nhau bởi dấu cách.
+
+**Ví dụ:**
+
+|  Sample Input  | Sample Output |
+| -------------- | ------------- |
+| 5<br>1 2 2 3 4 | 1 3 2 6 8     |
+
+## Bài 4. GHÉP CẶP (ZPAIRS.*)
+
+Cho hai dãy số A = (a<sub>1</sub>, a<sub>2</sub>, ..., a<sub>n</sub>) và dãy số
+B = (b<sub>1</sub>, b<sub>2</sub>, ..., b<sub>n</sub>) đã đượ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ử a<sub>i</sub> của dãy A và một phần
+tử b<sub>j</sub> của dãy B thành một cặp (a<sub>i</sub>, b<sub>j</sub>). Chi
+phí của cặp này được tính bằng |a<sub>i</sub> − b<sub>j</sub>|.
+
+**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 ≤ 10<sup>5</sup>).
+* Dòng 2: gồm n số nguyên sắp theo thứ tự không giảm là dãy A = (a<sub>1</sub>,
+  a<sub>2</sub>, ..., a<sub>n</sub>), |a<sub>i</sub>| ≤ 10<sup>9</sup>.
+* Dòng 3: gồm m số nguyên sắp theo thứ tự không giảm là dãy B =
+  ,(b<sub>1</sub>, b<sub>2</sub>, ..., b<sub>n</sub>) |b<sub>i</sub>| ≤
+  10<sup>9</sup>.
+
+**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<br>1 2 2 3<br>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à a<sub>1</sub> = 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 a<sub>1</sub>, a<sub>2</sub>, ...,
+a<sub>n</sub> (a<sub>i</sub> ≤ 10<sup>9</sup>). Với mỗi số a<sub>i</sub> 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 ≤ 10<sup>5</sup>)
+* n dòng tiếp theo, mỗi dòng ghi một số nguyên của dãy a<sub>1</sub>,
+  a<sub>2</sub>, ..., a<sub>n</sub> (a<sub>i</sub> ≤ 10<sup>9</sup>).
+
+**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ố a<sub>i</sub> 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 <stdio.h>
+
+/* 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 <stdio.h>
+
+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 <stdio.h>
+
+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 <stdio.h>
+
+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 <stdio.h>
+
+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;
+}