Add 12/QG-2007/maxiseq.c

2 files changed, 79 insertions, 0 deletions

diff --git a/12/QG-2007/README.md b/12/QG-2007/README.md
new file mode 100644
index 0000000..a58798f
--- /dev/null
+++ b/12/QG-2007/README.md
@@ -0,0 +1,43 @@
+# KÌ THI CHỌN HỌC SINH GIỎI QUỐC GIA THPT NĂM 2007
+
+## Dãy con không giảm dài nhất
+
+Cho dãy số nguyên dương a<sub>1</sub>, a<sub>2</sub>, …, a<sub>n</sub>.
+
+Dãy số a<sub>i</sub>, a<sub>i+1</sub>, …, a<sub>j</sub> thỏa mãn a<sub>i</sub>
+≤ a<sub>i+1</sub> ≤ … ≤ a<sub>j</sub> với 1 ≤ i ≤ j ≤ n được gọi là dãy con
+không giảm của dãy số đã cho và khi đó số j - i + 1 được gọi là độ dài của dãy
+con này. 
+
+### Yêu cầu
+
+Hãy tìm dãy con có độ dài lớn nhất trong số các dãy con không giảm của dãy số
+đã cho mà các phần tử của nó đều thuộc dãy số (u<sub>k</sub>) xác định bởi:
+
+* u<sub>1</sub> = 1;
+* u<sub>k</sub> = u<sub>k-1</sub> + k (k ≥ 2).
+
+### Dữ liệu
+
+* Dòng đầu tiên chứa một số nguyên dương n (n ≤ 10000);
+* Dòng thứ i trong n dòng tiếp theo chứa một số nguyên dương a<sub>i</sub> là
+  số hạng thứ i của dãy số đã cho (a<sub>i</sub> ≤ 10<sup>8</sup>, i = 1, 2, …,
+  n).
+
+### Kết quả
+
+Số nguyên d là độ dài của dãy con không giảm tìm được (quy ước rằng nếu không
+có dãy con nào thỏa mãn điều kiện đặt ra thì d = 0). 
+
+### Ví dụ
+
+|                   MAXISEQ.INP                   | MAXISEQ.OUT |
+| ----------------------------------------------- | :---------: |
+| 8<br>2<br>2007<br>6<br>6<br>15<br>16<br>3<br>21 |      3      |
+
+#### Giải thích
+
+Các dãy con không giảm của dãy số đã cho mà các phần tử của nó đều thuộc dãy
+(u<sub>k</sub>) là: 6, 6, 15 và 3, 21 (vì u<sub>2</sub> = 3, u<sub>3</sub> = 6,
+u<sub>5</sub> = 15, u<sub>6</sub> = 21). Dãy cần tìm là 6, 6, 15 có độ dài là
+3. 
diff --git a/12/QG-2007/maxiseq.c b/12/QG-2007/maxiseq.c
new file mode 100644
index 0000000..94c15c8
--- /dev/null
+++ b/12/QG-2007/maxiseq.c
@@ -0,0 +1,36 @@
+#include <math.h>
+#include <stdio.h>
+
+char is_in_u(long x)
+{
+	long y = (long) sqrt(x *= 2);
+	return y * (y + 1) == x;
+}
+
+int main()
+{
+	FILE *f = fopen("MAXISEQ.INP", "r");
+	short n, i, max = 0, start = -1;
+	long a, b;
+
+	fscanf(f, "%hd\n", &n);
+	for (i = 0; i < n; i++) {
+		b = a;
+		fscanf(f, "%ld\n", &a);
+		if (!is_in_u(a) || start >= 0 && b > a) {
+			start = -1;
+			continue;
+		}
+		if (start < 0)
+			start = i;
+		if (i - start >= max)
+			max = i - start + 1;
+	}
+	fclose(f);
+
+	f = fopen("MAXISEQ.OUT", "w");
+	fprintf(f, "%hd\n", max);
+	fclose(f);
+
+	return 0;
+}