From f4f486fb4b37b72ca345f95881e44043c728b2c3 Mon Sep 17 00:00:00 2001 From: Raphael McSinyx Date: Tue, 10 Jan 2017 10:46:15 +0700 Subject: Add others/other --- others/other/README.md | 62 ++++++++++++++++++++++++++++++++++++++++++++++ others/other/fdp.c | 50 +++++++++++++++++++++++++++++++++++++ others/other/interval.c | 65 +++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 177 insertions(+) create mode 100644 others/other/README.md create mode 100644 others/other/fdp.c create mode 100644 others/other/interval.c 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à [ai, +bi]. + +### 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 ≤ 105; |x| ≤ c ≤ + 109). +* N dòng tiếp theo, dòng thứ i + 1 ghi hai số nguyên ai, + bi (1 ≤ i ≤ N; |ai|, |bi| ≤ 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
1 3
2 4
7 10
0 1 | 2
1 2 | +| 3 10 5
1 2
-4 4
6 9 | 0
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 mk. + +### Dữ liệu + +Tệp `FDP.INP` gồm một dòng ghi hai số nguyên dương n và m (n ≤ 1018; +2 ≤ m ≤ 1012). + +### 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 +#include + +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 +#include + +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; +} -- cgit 1.4.1