Revise 12/TP-HN-2008/R2

11 files changed, 290 insertions, 113 deletions

diff --git a/12/TP-HN-2008/R2/DG b/12/TP-HN-2008/R2/DG
deleted file mode 100755
index ad902a1..0000000
--- a/12/TP-HN-2008/R2/DG
+++ /dev/null
Binary files differdiff --git a/12/TP-HN-2008/R2/DG.INP b/12/TP-HN-2008/R2/DG.INP
deleted file mode 100755
index fb3ca57..0000000
--- a/12/TP-HN-2008/R2/DG.INP
+++ /dev/null
@@ -1,6 +0,0 @@
-4
-0 1
-1 0
-0 -1
--1 0
--2 0 0 0
diff --git a/12/TP-HN-2008/R2/DG.OUT b/12/TP-HN-2008/R2/DG.OUT
deleted file mode 100755
index c227083..0000000
--- a/12/TP-HN-2008/R2/DG.OUT
+++ /dev/null
@@ -1 +0,0 @@
-0
\ No newline at end of file
diff --git a/12/TP-HN-2008/R2/DG.o b/12/TP-HN-2008/R2/DG.o
deleted file mode 100755
index cf2e3e1..0000000
--- a/12/TP-HN-2008/R2/DG.o
+++ /dev/null
Binary files differdiff --git a/12/TP-HN-2008/R2/DG.pas b/12/TP-HN-2008/R2/DG.pas
deleted file mode 100755
index 2313685..0000000
--- a/12/TP-HN-2008/R2/DG.pas
+++ /dev/null
@@ -1,83 +0,0 @@
-type bigboo = [-1..1];
-
-var
-  f : text;
-  n, i, j : byte;
-  inp : array[0..100] of PointType;
-  P, Q : PointType;
-  P_out, Q_out : boolean;
-  s : int64 = 0;
-
-function stri2(A, B, C : PointType) : int64;
-  begin
-    stri2 := (C.y - A.y) * (A.x - B.x) - (C.x - A.x) * (A.y - B.y)
-  end;
-
-function outpoly(M : PointType) : int64;
-  begin
-    outpoly := s;
-    for i := 0 to n - 1 do
-      begin
-        outpoly := outpoly - abs(stri2(M, inp[i], inp[i + 1]))
-      end
-  end;
-
-function sign(x : smallint) : bigboo;
-  begin
-    case true of
-      x > 0 : exit(1);
-      x = 0 : exit(0);
-      x < 0 : exit(-1)
-    end
-  end;
-
-function intersect(A, B : PointType) : bigboo;
-  var b00, b01 : bigboo;
-  begin
-    b00 := sign(stri2(P, Q, A));
-    b01 := sign(stri2(P, Q, A));
-    if b00 = b01 then
-      if b00 = 0 then exit(0)
-      else exit(-1);
-    b00 := sign(stri2(A, B, P));
-    b01 := sign(stri2(A, B, Q));
-    if b00 = b01 then
-      if b00 = 0 then exit(0)
-      else exit(-1);
-    exit(1)
-  end;
-
-function lensqr(A, B : PointType) : int64;
-  begin
-    exit()
-  end;
-
-procedure out(M, N : PointType);
-  begin
-    assign(f, 'DG.OUT');
-    rewrite(f);
-    write(f, trunc(sqrt(sqr(A.x - B.x) + sqr(A.y - B.y)) * 100));
-    close(f);
-    halt
-  end;
-
-begin
-  assign(f, 'DG.INP');
-  reset(f);
-  readln(f, n);
-  for i := 0 to n - 1 do
-    readln(f, inp[i].x, inp[i].y);
-  inp[n] := inp[0];
-  readln(f, P.x, P.y, Q.x, Q.y);
-  close(f);
-  for i := 1 to n - 2 do
-    s := s + abs(stri2(inp[0], inp[i], inp[i + 1]));
-  if outpoly(P) = 0 then
-    P_out := false;
-  if outpoly(Q) = 0 then
-    Q_out := false;
-  if P_out and Q_out then
-    for i := 0 to n - 1 do
-
-  out(P, Q)
-end.
diff --git a/12/TP-HN-2008/R2/HC.pas b/12/TP-HN-2008/R2/HC.pas
deleted file mode 100644
index 8e6b182..0000000
--- a/12/TP-HN-2008/R2/HC.pas
+++ /dev/null
@@ -1,23 +0,0 @@
-var
-  f : text;
-  m, n, i, j : byte;
-  a : array[1..200, 0..200] of smallint;
-
-function out
-
-begin
-  assign(f, 'HC.INP');
-  reset(f);
-  readln(f, m, n);
-  for i := 1 to m do
-    begin
-      a[i, 0] := 0;
-      for j := 1 to n do
-        read(f, a[i, j])
-    end;
-  close(f);
-  assign(f, 'HC.OUT');
-  rewrite(f);
-  writeln(f, out(a));
-  close(f)
-end;
diff --git a/12/TP-HN-2008/R2/R2.doc b/12/TP-HN-2008/R2/R2.doc
deleted file mode 100755
index c804058..0000000
--- a/12/TP-HN-2008/R2/R2.doc
+++ /dev/null
Binary files differdiff --git a/12/TP-HN-2008/R2/README.md b/12/TP-HN-2008/R2/README.md
new file mode 100644
index 0000000..00ccc3e
--- /dev/null
+++ b/12/TP-HN-2008/R2/README.md
@@ -0,0 +1,115 @@
+# KÌ THI CHỌN HỌC SINH GIỎI CẤP THÀNH PHỐ LỚP 12 NĂM HỌC 2015 - 2016
+
+SỞ GIÁO DỤC VÀ ĐÀO TẠO HÀ NỘI
+
+Môn thi: TIN HỌC
+
+Ngày thi: 10/12/2008
+
+Thời gian làm bài: 180 phút
+
+## Tổng quan bài thi
+
+|  Bài  | Tệp chương trình | Tệp dữ liệu vào | Tệp kết quả ra | Thời gian |
+| :---: | :--------------: | :-------------: | :------------: | :-------: |
+|   1   |     TBC.PAS      |     TBC.INP     |    TBC.OUT     |  2 giây   |
+|   2   |      HC.PAS      |      HC.INP     |     HC.OUT     |  2 giây   |
+|   3   |      DG.PAS      |      DG.INP     |     DG.OUT     |  2 giây   |
+
+## Bài 1: Số trung bình cộng
+
+Cho dãy số nguyên a<sub>1</sub>, a<sub>2</sub>, …, a<sub>n</sub>. Số
+a<sub>p</sub> (1 ≤ p ≤ n) được gọi là một số trung bình cộng trong dãy nếu tồn
+tại 3 chỉ số i, j, k (1 ≤ i, j, k ≤ n) đôi một khác nhau, sao cho a<sub>p</sub>
+= (a<sub>i</sub> + a<sub>j</sub> + a<sub>k</sub>) / 3.
+
+### Yêu cầu
+
+Hãy tìm số lượng các số trung bình cộng trong dãy.
+
+### Dữ liệu
+
+* Dòng đầu ghi số nguyên dương n (3 ≤ n ≤ 1000);
+* Dòng thứ i trong n dòng tiếp theo ghi số nguyên a<sub>i</sub>
+  (|a<sub>i</sub>| < 10<sup>8</sup>).
+
+### Kết quả
+
+Một số duy nhất là đáp án của bài toán.
+
+### Ví dụ
+
+|          TBC.INP           | TBC.OUT |
+| :------------------------: | :-----: |
+| 5<br>4<br>3<br>6<br>3<br>5 |    2    |
+|      3<br>1<br>2<br>5      |    0    |
+
+*Chú ý: 50% số test có n ≤ 300.*
+
+### Bài 2: Hội chợ
+
+Một khu hội chợ có m × n gian hàng được bố trí trong một khu hình chữ nhật kích
+thước m × n. Các hàng của hình chữ nhật được đánh số từ trên xuống dưới bắt đầu
+từ 1 đến m, còn các cột – đánh số từ trái sang phải, bắt đầu từ 1 đến n, ô nằm
+giao của hàng i và cột j là gian hàng (i, j). Mỗi gian hàng trưng bày một sản
+phẩm và đều có cửa thông với các gian hàng chung cạnh với nó. Khách tham quan
+đi vào khu hội chợ từ một gian hàng bất kỳ bên trái (i bất kỳ, j = 1) và không
+nhất thiết phải thăm quan tất cả các gian hàng. Khách chỉ có thể đi ra khỏi khu
+hội chợ từ các gian hàng bên phải (i bất kỳ, j = n), tại mỗi gian hàng khách có
+thể di chuyển qua các gian hàng có cửa thông với nó. Khi đi vào gian hàng (i,
+j) thì khách tham quan phải mua vé giá là a<sub>i, j</sub>.
+
+### Yêu cầu
+
+Tính chi phí ít nhất mà khách tham quan phải trả khi tham quan khu hội chợ.
+
+### Dữ liệu
+
+* Dòng đầu tiên ghi số m, n (2 ≤ m, n ≤ 200).
+* m dòng sau, mỗi dòng n số nguyên không âm, cho biết giá vé các gian hàng của
+  khu hội chợ. Giá vé tại gian hàng (i, j) là a<sub>i, j</sub> ≤ 30000.
+
+### Kết quả
+
+Một số duy nhất là chi phí ít nhất tìm được.
+
+### Ví dụ
+
+|                HC.INP                | HC.OUT |
+| ------------------------------------ | :----: |
+| 3 4<br>2 1 9 1<br>5 0 3 4<br>2 1 9 1 |   10   |
+
+*Chú ý: 50% số test có m, n ≤ 20.*
+
+## Bài 3: Đa giác
+
+Trên mặt phẳng tọa độ, xét đa giác lồi n đỉnh, các đỉnh đều có tọa độ nguyên và
+có giá trị tuyệt đối không vượt quá 10<sup>5</sup>. Các đỉnh của đa giác được
+liệt kê theo chiều kim đồng hồ. 
+
+### Yêu cầu
+
+Cho đoạn thẳng xác định bởi hai điểm có tọa độ là (x<sub>1</sub>,
+y<sub>1</sub>) và (x<sub>2</sub>, y<sub>2</sub>) trong đó x<sub>1</sub>,
+y<sub>1</sub>, x<sub>2</sub>, y<sub>2</sub> là các số nguyên và có giá trị
+tuyệt đối không vượt quá 10<sup>6</sup>. Hãy xác định độ dài L là phần của đoạn
+thẳng nằm trong đa giác hay trên cạnh của đa giác và đưa ra số nguyên là phần
+nguyên của tích L * 100.
+
+### Dữ liệu
+
+* Dòng đầu tiên chứa số nguyên n (3 ≤ n ≤ 100);
+* Dòng thứ i trong n dòng sau chứa 2 số nguyên xác định tọa độ đỉnh i của đa
+  giác;
+* Dòng cuối cùng chứa 4 số nguyên x<sub>1</sub>, y<sub>1</sub>, x<sub>2</sub>,
+  y<sub>2</sub>.
+
+### Kết quả
+
+Một số nguyên là phần nguyên của tích L * 100.
+
+### Ví dụ
+
+|                   DG.INP                    | DG.OUT |
+| ------------------------------------------- | :----: |
+| 4<br>0 1<br>1 0<br>0 -1<br>-1 0<br>-2 0 0 0 |   100  |
diff --git a/12/TP-HN-2008/R2/dg.c b/12/TP-HN-2008/R2/dg.c
new file mode 100644
index 0000000..e2422df
--- /dev/null
+++ b/12/TP-HN-2008/R2/dg.c
@@ -0,0 +1,102 @@
+#include <math.h>
+#include <stdio.h>
+
+#define ABS(x) (((x) < 0) ? -(x) : (x))
+#define SQR(x) ((x) * (x))
+#define DET(a, b, c, d) ((a) * (d) - (b) * (c))
+#define MIN(a, b) (((a) < (b)) ? (a) : (b))
+#define MAX(a, b) (((a) > (b)) ? (a) : (b))
+
+typedef struct {
+	long x, y;
+} poin_t;
+
+typedef struct {
+	float x, y;
+} fpoin_t;
+
+long area2(poin_t A, poin_t B, poin_t C)
+{
+	return ABS(DET(C.x - A.x, A.x - B.x, C.y - A.y, A.y - B.y));
+}
+
+int main()
+{
+	FILE *f = fopen("DG.INP", "r");
+	char n, i, c = 0, b;
+	poin_t M, N, P, Q, polygon[101];
+	fpoin_t tmp, intersections[2];
+	long Mout = 0, Nout, d;
+	double res;
+
+	fscanf(f, "%hhd", &n);
+	for (i = 0; i < n; i++)
+		fscanf(f, "%ld %ld", &polygon[i].x, &polygon[i].y);
+	fscanf(f, "%ld %ld %ld %ld", &M.x, &M.y, &N.x, &N.y);
+	fclose(f);
+	f = fopen("DG.OUT", "w");
+	if (M.x == N.x && M.y == N.y) {
+		fputs("0\n", f);
+		fclose(f);
+		return 0;
+	}
+
+	for (i = 1; i < n - 1; i++)
+		Mout += area2(*polygon, polygon[i], polygon[i + 1]);
+	for (Nout = Mout, polygon[n] = *polygon, i = 0; i < n; i++) {
+		Mout -= area2(M, polygon[i], polygon[i + 1]);
+		Nout -= area2(N, polygon[i], polygon[i + 1]);
+	}
+	if (!Mout && !Nout) {
+		fprintf(f, "%ld\n",
+		        (long) (sqrt(SQR(M.x - N.x) + SQR(M.y - N.y)) * 100));
+		fclose(f);
+		return 0;
+	}
+
+	for (i = 0; i < n; i++) {
+		P = polygon[i];
+		Q = polygon[i + 1];
+		d = DET(M.x - N.x, M.y - N.y, P.x - Q.x, P.y - Q.y);
+		if (!d)
+			continue;
+
+		tmp.x = DET(DET(M.x, M.y, N.x, N.y), M.x - N.x,
+		            DET(P.x, P.y, Q.x, Q.y), P.x - Q.x) / (double) d;
+		tmp.y = DET(DET(M.x, M.y, N.x, N.y), M.y - N.y,
+		            DET(P.x, P.y, Q.x, Q.y), P.y - Q.y) / (double) d;
+
+		if (tmp.x < MAX(MIN(M.x, N.x), MIN(P.x, Q.x))
+		    || tmp.x > MIN(MAX(M.x, N.x), MAX(P.x, Q.x))
+		    || tmp.y < MAX(MIN(M.y, N.y), MIN(P.y, Q.y))
+		    || tmp.y > MIN(MAX(M.y, N.y), MAX(P.y, Q.y)))
+			continue;
+
+		for (b = d = 0; d < c; d++)
+			if (intersections[d].x == tmp.x
+			    && intersections[d].y == tmp.y)
+				b = 1;
+		if (b)
+			continue;
+
+		intersections[c].x = tmp.x;
+		intersections[c].y = tmp.y;
+		c++;
+	}
+
+	if (!Mout && c)
+		res = SQR(M.x - intersections[0].x)
+		      + SQR(M.y - intersections[0].y);
+	else if (!Nout && c)
+		res = SQR(N.x - intersections[0].x)
+		      + SQR(N.y - intersections[0].y);
+	else if (c == 2)
+		res = SQR(intersections[0].x - intersections[1].x)
+		      + SQR(intersections[0].y - intersections[1].y);
+	else
+		res = 0;
+	fprintf(f, "%ld\n", (long) (sqrt(res) * 100));
+	fclose(f);
+
+	return 0;
+}
diff --git a/12/TP-HN-2008/R2/hc.cpp b/12/TP-HN-2008/R2/hc.cpp
new file mode 100644
index 0000000..1ea6ee3
--- /dev/null
+++ b/12/TP-HN-2008/R2/hc.cpp
@@ -0,0 +1,73 @@
+#include <iostream>
+#include <fstream>
+#include <functional>
+#include <queue>
+#include <vector>
+
+#define ENC(a, x, y) (((a) << 16) + ((x) << 8) + (y))
+
+using namespace std;
+
+int
+main()
+{
+  long long m, n, i, j, a[200][200];
+  ifstream infile;
+  infile.open("HC.INP");
+  infile >> m >> n;
+  for (i = 0; i < m; i++)
+    for (j = 0; j < n; j++)
+      infile >> a[i][j];
+  infile.close();
+
+  priority_queue<long long, vector<long long>, greater<long long>> heap;
+  long long path[200][200] = {};
+  for (i = 0; i < m; i++)
+    {
+      heap.push(ENC(*a[i], i, 0));
+      path[i][0] = 1;
+    }
+
+  long long tmp, x, y;
+  while (!heap.empty())
+    {
+      tmp = heap.top();
+      heap.pop();
+      x = tmp >> 8 & 255;
+      y = tmp & 255;
+      tmp >>= 16;
+      if (y == n - 1)
+        break;
+
+      if (!path[x][y + 1])
+        {
+          heap.push(ENC(tmp + a[x][y + 1], x, y + 1));
+          path[x][y + 1] = 1;
+        }
+
+      if (y)
+        if (x && !path[x - 1][y])
+          {
+            heap.push(ENC(tmp + a[x - 1][y], x - 1, y));
+            path[x - 1][y] = 1;
+          }
+        else if (x < m - 1 && !path[x + 1][y])
+          {
+            heap.push(ENC(tmp + a[x + 1][y], x + 1, y));
+            path[x + 1][y] = 1;
+          }
+
+      if (y > 1 && !path[x][y - 1])
+        {
+          heap.push(ENC(tmp + a[x][y - 1], x, y - 1));
+          path[x][y - 1] = 1;
+        }
+    }
+
+  ofstream outfile;
+  outfile.open("HC.OUT");
+  outfile << tmp << endl;
+  outfile.close();
+
+  return 0;
+}
diff --git a/12/TP-HN-2008/R2/TBC.PAS b/12/TP-HN-2008/R2/tbc.pas
index 1a26a91..1a26a91 100755
--- a/12/TP-HN-2008/R2/TBC.PAS
+++ b/12/TP-HN-2008/R2/tbc.pas