diff options
| -rw-r--r-- | others/other/README.md | 64 | ||||
| -rw-r--r-- | others/other/diffsum.pas | 42 | ||||
| -rwxr-xr-x | others/other/diffsum.py | 17 | ||||
| -rw-r--r-- | others/other/lseq.c | 58 |
4 files changed, 179 insertions, 2 deletions
diff --git a/others/other/README.md b/others/other/README.md index 1426c71..8126221 100644 --- a/others/other/README.md +++ b/others/other/README.md @@ -12,15 +12,75 @@ Tệp `BIN.INP` gồm một dòng duy nhất ghi số n. Tệp `BIN.OUT` gồm một dòng ghi biểu diễn nhị phân của n. +### Giới hạn + +n ≤ 10<sup>18</sup>. + ### Ví dụ | BIN.INP | BIN.OUT | | :-----: | :-----: | | 109 | 1101101 | +## DiffSum + +Lập chương trình phân tích số nguyên dương n thành tổng của các số nguyên dương +khác nhau sao cho tích của các số hạng này là lớn nhất có thể. + +### Dữ liệu + +Tệp `DIFFSUM.INP` gồm một dòng duy nhất ghi số n. + +### Kết quả + +Tệp `DIFFSUM.OUT` ghi các số hạng của cách phân tích tìm được theo thứ tự tăng +dần trên một dòng. + ### Giới hạn -n ≤ 10<sup>18</sup>. +n ≤ 10<sup>5</sup>. + +### Ví dụ + +| DIFFSUM.INP | DIFFSUM.OUT | +| :---------: | :---------: | +| 5 | 2 3 | +| 10 | 2 3 5 | + +## Tìm dãy số nguyên liên tiếp + +Cho dãy gồm n số tự nhiên đôi một khác nhau a<sub>1</sub>, a<sub>2</sub>, …, +a<sub>n</sub>. Nếu trong dãy đã cho có chứa số 0, bạn được phép thay số 0 bằng +một số nguyên dương bất kì khác. + +### Yêu cầu + +Hãy chọn trong dãy gồm nhiều nhất các số sao cho các số đã chọn tạo thành một +dãy số tự nhiên liên tiếp. + +### Dữ liệu + +Tệp `LSEQ.INP`: + +* Dòng thứ nhất chứa số nguyên dương n. +* Dòng thứ hai dãy số tự nhiên a<sub>1</sub>, a<sub>2</sub>, …, a<sub>n</sub>. + +### Kết quả + +Tệp `LSEQ.OUT` gồm một dòng duy nhất ghi độ dài lớn nhất của dãy số tự nhiên +liên tiếp chọn được. + +### Giới hạn + +* n ≤ 10<sup>6</sup>. +* a<sub>i</sub> ≤ 10<sup>6</sup> ∀ 1 ≤ i ≤ n. + +### Ví dụ + +| LSEQ.INP | LSEQ.OUT | Giải thích | +| ------------------ | :------: | ------------------------------------ | +| 5<br>2 9 3 7 4 | 3 | Chọn dãy 2, 3, 4 | +| 7<br>1 2 4 7 6 0 8 | 5 | Thay 0 bởi 5, chọn dãy 4, 5, 6, 7, 8 | ## Trò chơi với dãy số @@ -160,7 +220,7 @@ Tệp `DICT.INP` gồm n + q + 2 dòng: Tệp `DICT.OUT` gồm q dòng, mỗi dòng gồm một số nguyên là câu trả lời cho truy vấn tương ứng. -## Giới hạn +### Giới hạn * 1 ≤ n, q ≤ 20000. * 1 ≤ Độ dài w, s ≤ 20. diff --git a/others/other/diffsum.pas b/others/other/diffsum.pas new file mode 100644 index 0000000..e37152c --- /dev/null +++ b/others/other/diffsum.pas @@ -0,0 +1,42 @@ +var + f: text; + n, i, tmp: smallint; + a: array of smallint; + +begin + assign(f, 'DIFFSUM.INP'); + reset(f); + read(f, n); + close(f); + + if n > 1 then + setlength(a, trunc(sqrt(n * 2 + 2.25) - 1.5)) + else + setlength(a, 1); + tmp := 0; + for i := 0 to length(a) - 2 do + begin + a[i] := i + 2; + inc(tmp, a[i]) + end; + a[length(a) - 1] := n - tmp; + + if length(a) > 1 then + while a[length(a) - 1] - a[length(a) - 2] > 2 do + for i := length(a) - 1 downto 1 do + begin + tmp := (a[i] - 1 - a[i - 1]) div 2; + if tmp > 0 then + begin + dec(a[i], tmp); + inc(a[i - 1], tmp) + end + end; + + assign(f, 'DIFFSUM.OUT'); + rewrite(f); + for i in a do + write(f, i, ' '); + writeln(f); + close(f) +end. diff --git a/others/other/diffsum.py b/others/other/diffsum.py new file mode 100755 index 0000000..697db0c --- /dev/null +++ b/others/other/diffsum.py @@ -0,0 +1,17 @@ +#!/usr/bin/env python3 + +with open("DIFFSUM.INP") as f: + n = int(f.readline()) + +a = list(range(2, int((n * 8 + 9) ** 0.5 - 3) // 2 + 1)) +a.append(n - sum(a)) + +while len(a) > 1 and a[-1] - a[-2] > 2: + for i in reversed(range(1, len(a))): + delta = (a[i] - 1 - a[i - 1]) // 2 + if delta > 0: + a[i] -= delta + a[i - 1] += delta + +with open("DIFFSUM.OUT", "w") as f: + f.write(' '.join(map(str, a)) + '\n') diff --git a/others/other/lseq.c b/others/other/lseq.c new file mode 100644 index 0000000..c0e4e81 --- /dev/null +++ b/others/other/lseq.c @@ -0,0 +1,58 @@ +#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 main() +{ + FILE *f = fopen("LSEQ.INP", "r"); + long n, *a, i, *start, *end, length = 1, tmp; + char b = 0; + + fscanf(f, "%ld", &n); + a = malloc(n * sizeof(long)); + for(i = 0; i < n; i++) + fscanf(f, "%ld", a + i); + fclose(f); + + qsort(a, n, sizeof(long), cmp); + start = malloc(n * sizeof(long)); + start[0] = !*a; + for (i = start[0] + 1; i < n; i++) + if (a[i] - 1 - a[i - 1]) + start[length++] = i; + start = realloc(start, length * sizeof(long)); + + end = malloc(length * sizeof(long)); + end[length - 1] = n - 1; + for (i = 1; i < length; i++) + end[i - 1] = start[i] - 1; + + n = 0; + if (*a) + for (i = 0; i < length; i++) { + tmp = end[i] - start[i] + 1; + n = (tmp > n) ? tmp : n; + } + else + for (i = 0; i < length; i++) { + tmp = end[i] - start[i - 1] + 1; + if (!i || a[end[i]] - a[start[i - 1]] - tmp) + tmp += start[i - 1] - start[i]; + n = (++tmp > n) ? tmp : n; + } + + f = fopen("LSEQ.OUT", "w"); + fprintf(f, "%ld\n", n); + fclose(f); + + return 0; +} |