about summary refs log tree commit diff
path: root/others/other
diff options
context:
space:
mode:
Diffstat (limited to 'others/other')
-rw-r--r--others/other/README.md62
-rw-r--r--others/other/fdp.c50
-rw-r--r--others/other/interval.c65
3 files changed, 177 insertions, 0 deletions
diff --git a/others/other/README.md b/others/other/README.md
new file mode 100644
index 0000000..dade74b
--- /dev/null
+++ b/others/other/README.md
@@ -0,0 +1,62 @@
+# Các bài tập khác
+
+## Tìm đoạn thẳng v2
+
+Trên 1 đoạn trục số [−c, c], cho N đoạn thẳng, đoạn thứ i là [a<sub>i</sub>,
+b<sub>i</sub>].
+
+### Yêu cầu
+
+Cho một điểm M với toạ độ x. Hãy cho biết M thuộc bao nhiêu đoạn thẳng đã cho ở
+trên, và cụ thể là những đoạn nào? Nếu M không thuộc đoạn nào trong các đoạn đã
+cho, hãy chỉ ra 1 đoạn dài nhất chứa điểm M và không có điểm trong chung với
+bất kì đoạn nào trong N đoạn đã cho (không có điểm chung ngoài hai điểm đầu
+mút).
+
+### Dữ liệu
+
+Tệp `INTERVAL.INP`:
+
+* Dòng thứ nhất ghi ba số nguyên N, c và x (1 ≤ N ≤ 10<sup>5</sup>; |x| ≤ c ≤
+  10<sup>9</sup>).
+* N dòng tiếp theo, dòng thứ i + 1 ghi hai số nguyên a<sub>i</sub>,
+  b<sub>i</sub> (1 ≤ i ≤ N; |a<sub>i</sub>|, |b<sub>i</sub>| ≤ c).
+
+### Kết quả
+
+Tệp `INTERVAL.OUT`:
+
+* Dòng thứ nhất ghi số tự nhiên K là số đoạn chứa điểm M.
+* Dòng thứ hai:
+    * Nếu K dương, ghi K số là số thứ tự của K đoạn chứa M.
+    * Nếu K = 0, ghi hai số nguyên là toạ độ hai đầu mút của đoạn thẳng dài
+      nhất chứa M và không có điểm trong chung với N đoạn đã cho.
+
+### Ví dụ
+
+|             INTERVAL.INP            | INTERVAL.OUT |
+| ----------------------------------- | ------------ |
+| 4 20 2<br>1 3<br>2 4<br>7 10<br>0 1 |   2<br>1 2   |
+| 3 10 5<br>1 2<br>-4 4<br>6 9        |   0<br>4 6   |
+
+## Phân tích số
+
+Lập chương trình nhập vào 2 số nguyên dương n và m.
+
+Tìm số tự nhiên k lớn nhất sao cho n! chia hết cho m<sup>k</sup>.
+
+### Dữ liệu
+
+Tệp `FDP.INP` gồm một dòng ghi hai số nguyên dương n và m (n ≤ 10<sup>18</sup>;
+2 ≤ m ≤ 10<sup>12</sup>).
+
+### Kết quả
+
+Tệp `FDP.OUT` gồm một dòng duy nhất ghi số tự nhiên k.
+
+### Ví dụ
+
+| FDP.INP | FDP.OUT |
+| :-----: | :-----: |
+|  10 10  |    2    |
+| 100 15  |   24    |
diff --git a/others/other/fdp.c b/others/other/fdp.c
new file mode 100644
index 0000000..439716b
--- /dev/null
+++ b/others/other/fdp.c
@@ -0,0 +1,50 @@
+#include <math.h>
+#include <stdio.h>
+
+int main()
+{
+	FILE *F = fopen("FDP.INP", "r");
+	long long n, m, j, factors[11];
+	long i;
+	char f = 0, fm[11] = {}, fn[11] = {}, k = 127;
+
+	fscanf(F, "%lld %lld", &n, &m);
+	fclose(F);
+
+	if (m % 2 == 0) {
+		factors[0] = 2;
+		do {
+			m /= 2;
+			fm[0]++;
+		} while (m % 2 == 0);
+		f = 1;
+	}
+
+	for (i = 3; i <= (long) sqrt((double) m); i += 2)
+		if (m % i == 0) {
+			factors[f] = i;
+			do {
+				m /= i;
+				fm[f]++;
+			} while (m % i == 0);
+			f++;
+		}
+
+	if (m != 1) {
+		factors[f] = m;
+		fm[f] = 1;
+		f++;
+	}
+
+	for (i = 0; i < f; i++) {
+		for (j = factors[i]; j <= n; j *= factors[i])
+			fn[i] += n / j;
+		k = (fn[i] / fm[i] < k) ? (fn[i] / fm[i]) : k;
+	}
+
+	F = fopen("FDP.OUT", "w");
+	fprintf(F, "%hhd\n", k);
+	fclose(F);
+
+	return 0;
+}
diff --git a/others/other/interval.c b/others/other/interval.c
new file mode 100644
index 0000000..c068952
--- /dev/null
+++ b/others/other/interval.c
@@ -0,0 +1,65 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+int sign(long x)
+{
+	return (x) ? ((x > 0) ? 1 : -1) : x;
+}
+
+int cmp(const void *x, const void *y)
+{
+	return sign(*(long *) x - *(long *) y);
+}
+
+int CMP(const void *x, const void *y)
+{
+	return -cmp(x, y);
+}
+
+int main()
+{
+	FILE *f = fopen("INTERVAL.INP", "r");
+	short n, i, k = 0, *r;
+	long c, x, *a, *b;
+
+	fscanf(f, "%hd %ld %ld", &n, &c, &x);
+	a = malloc(n * sizeof(long));
+	b = malloc(n * sizeof(long));
+
+	for (i = 0; i < n; i++)
+		fscanf(f, "%ld %ld", a + i, b + i);
+
+	fclose(f);
+
+	r = calloc(n, sizeof(short));
+	for (i = 0; i < n; i++)
+		if (a[i] <= x && b[i] >= x)
+			k += r[i] = 1;
+
+	f = fopen("INTERVAL.OUT", "w");
+
+	if (k) {
+		fprintf(f, "%hd\n", k);
+
+		for (i = 0; i < n; i++)
+			if (r[i])
+				fprintf(f, "%hd ", i + 1);
+		putc(10, f);
+	} else {
+		qsort(a, n, sizeof(long), cmp);
+		qsort(b, n, sizeof(long), CMP);
+
+		free(r);
+		r = malloc(2 * sizeof(short));
+		for (i = 0; i < n && b[i] > x; i++);
+		r[0] = (i == n) ? -c : b[i];
+		for (i = 0; i < n && a[i] < x; i++);
+		r[1] = (i == n) ? c : a[i];
+
+		fprintf(f, "0\n%hd %hd\n", r[0], r[1]);
+	}
+
+	fclose(f);
+
+	return 0;
+}