others/other: Add diffsum.{py,pas} and lseq.c

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;
+}