Add 9/TP-HN-2014

6 files changed, 385 insertions, 1 deletions

diff --git a/12/TP-ThanhHoá-2009/README.md b/12/TP-ThanhHoá-2009/README.md
index b64db6b..f5d69a1 100644
--- a/12/TP-ThanhHoá-2009/README.md
+++ b/12/TP-ThanhHoá-2009/README.md
@@ -16,7 +16,7 @@ Thời gian: 180 phút
 |   2   |     BAI2.PAS     |     BAI2.INP    |    BAI2.OUT    |   5   |
 |   3   |     BAI3.PAS     |     BAI3.INP    |    BAI3.OUT    |   4   |
 |   4   |     BAI4.PAS     |     BAI4.INP    |    BAI4.OUT    |   3   |
-|   4   |     BAI5.PAS     |     BAI5.INP    |    BAI5.OUT    |   3   |
+|   5   |     BAI5.PAS     |     BAI5.INP    |    BAI5.OUT    |   3   |
 
 Giới hạn thời gian cho mỗi test là 3 giây.
 
diff --git a/9/TP-HN-2014/README.md b/9/TP-HN-2014/README.md
new file mode 100644
index 0000000..8a21e84
--- /dev/null
+++ b/9/TP-HN-2014/README.md
@@ -0,0 +1,159 @@
+# KỲ THI HỌC SINH GIỎI THÀNH PHỐ LỚP 9 NĂM HỌC 2013 - 2014
+
+SỞ GIÁO DỤC VÀ ĐÀO TẠO HÀ NỘI
+
+Môn thi: TIN HỌC
+
+Ngày thi: 31/03/2014
+
+Thời gian làm bài: 150 phút
+
+## Tổng quan bài thi
+
+|  Câu  | Tệp chương trình | Tệp dữ liệu | Tệp kết quả |  Điểm |
+| :---: | :--------------: | :---------: | :---------: | :---: |
+|   1   |     CAU1.PAS     |   CAU1.INP  |   CAU1.OUT  |   6   |
+|   2   |     CAU2.PAS     |   CAU2.INP  |   CAU2.OUT  |   6   |
+|   3   |     CAU3.PAS     |   CAU3.INP  |   CAU3.OUT  |   4   |
+|   4   |     CAU4.PAS     |   CAU4.INP  |   CAU4.OUT  |   4   |
+
+## Câu 1: Hiệu hai phân số
+
+Cho bốn số nguyên dương a, b, c, d, mỗi số có giá trị không vượt quá
+10<sup>5</sup>.
+
+### Yêu cầu
+
+Tìm hai số nguyên x, y để phân số tối giản <sup>x</sup>/<sub>y</sub> và bằng
+hiệu của hai phân số <sup>a</sup>/<sub>b</sub> - <sup>c</sup>/<sub>d</sub>,
+trong đó y > 0.
+
+### Dữ liệu
+
+* Dòng đầu chứ hai số a, b;
+* Dòng thứ hai chứa hai số c, d.
+
+### Kết quả
+
+Hai số x và y trên cùng một dòng, cách nhau một dấu cách.
+
+### Ví dụ
+
+|   CAU1.INP  | CAU1.OUT |
+| ----------- | :------: |
+| 1 6<br>5 12 |   -1 4   |
+
+#### Giải thích
+
+<sup>1</sup>/<sub>6</sub> - <sup>5</sup>/<sub>12</sub> =
+<sup>-1</sup>/<sub>4</sub>
+
+## Câu 2: Đua Robot
+
+Trong cuộc đua tốc độc có n Robot tham gia được đánh số từ 1 đến n. Đường đua
+có độ dài d (mét). Robot thứ i (1 ≤ i ≤ n) có vận tốc đua không đổi là
+v<sub>i</sub> (mét/phút). Các Robot xuất phát theo thứ tự từ 1 đến n và cách
+nhau 1 phút. Robot i gọi là vượt Robot j (1 ≤ j ≤ n) nếu i xuất phát sau j và
+về đích trước j.
+
+### Yêu cầu
+
+Xác định số lần vượt nhau của tất cả các Robot trong cuộc đua.
+
+### Dữ liệu
+
+* Dòng đầu chứa hai số nguyên dương n và d, n ≤ 10<sup>3</sup>,
+  d ≤ 10<sup>9</sup>;
+* Dòng tiếp theo chứa n số nguyên dương v<sub>i</sub>, 1 ≤ i ≤ n, mỗi số không
+  vượt quá 1000.
+
+### Kết quả
+
+Số lần vượt nhau của tất cả các Robot trong cuộc đua.
+
+### Ví dụ
+
+|      CAU2.INP     | CAU2.OUT |
+| ----------------- | :------: |
+| 5 10<br>1 2 4 3 8 |     7    |
+
+#### Giải thích
+
+* Robot 2 vượt Robot 1;
+* Robot 3 vượt Robot 1, 2;
+* Robot 4 vượt Robot 1;
+* Robot 5 vượt Robot 1, 2, 4.
+
+Tổng số lần vượt là 7.
+
+## Câu 3: Tìm kiếm trong xâu
+
+Cho xâu s có độ dài tối đa 250 kí tự gồm chữ cái in hoa, in thường và chữ số.
+
+### Yêu cầu
+
+Đếm xem trong xâu s có bao nhiêu kí tự khác nhau và tìm độ dài đoạn kí tự liên
+tiếp dài nhất trong xâu s tạo thành xâu x đối xứng. Xâu kí tự x được gọi là đối
+xứng nếu đọc từ trái sang phải hoặc ngược lại ta đều thu được xâu như nhau.
+
+### Dữ liệu
+
+Một dòng duy nhất chứa xâu s.
+
+### Kết quả
+
+* Dòng thứ nhất ghi số lượng kí tự khác nhau trong s;
+* Dòng thứ hai ghi độ dài xâu x tìm được.
+
+### Ví dụ
+
+|      CAU3.INP     | CAU3.OUT |
+| :---------------: | :------: |
+| AbcabA12321ABCcba |  9<br>7  |
+
+#### Giải thích
+
+Các kí tự khác nhau gồm: `1`, `2`, `3`, `A`, `B`, `C`, `a`, `b`, `c`.
+
+Xâu X tìm được là: `A12321A`.
+
+## Câu 4: Trồng cây
+
+Dọc theo một tuyến phố thẳng có n vị trí kế tiếp nhau để trồng cây đánh số từ 1
+đến n. Hiện tại chỉ có vị trí k (1 ≤ k ≤ n) đã trồng một cây có độ cao
+a<sub>k</sub>, còn các vị trí khác để trống. Theo dự kiến, người ta sẽ trồng
+cây có độ cao a<sub>i</sub> tại vị trí thứ i (1 ≤ i ≤ n, i ≠ k). Tuy nhiên, để
+tăng vẻ đẹp cho hàng cây, người ta muốn tìm một phương án sắp xếp các cây cần
+trồng vào các vị trí thích hợp (trừ vị trí k) sao cho tổng tất cả các độ chênh
+lệch của hai cây trồng liền nhau là nhỏ nhất. Độ chênh lệch của hai cây là giá
+trị tuyệt đối hiệu độ cao hai cây.
+
+### Yêu cầu
+
+Tìm giá trị nhỏ nhất t của tổng tất cả các độ chênh lệch của hai cây trồng liền
+nhau.
+
+### Dữ liệu
+
+* Dòng đầu chứa hai số nguyên dương n và d, n ≤ 10<sup>3</sup>, 1 ≤ k ≤ n;
+* Dòng sau chứa n số nguyên dương a<sub>i</sub>, 1 ≤ i ≤ n, là độ cao của cây
+  thứ i theo dự kiến. Mỗi số đều không vượt quá 10<sup>6</sup>.
+
+### Kết quả
+
+Số t tìm được.
+
+### Ví dụ
+
+|     CAU4.INP     | CAU4.OUT |
+| ---------------- | :------: |
+| 5 2<br>7 3 4 2 6 |     5    |
+
+#### Giải thích
+
+* Vị trí 1 trồng cây có độ cao 2;
+* Vị trí 3 trồng cây có độ cao 4;
+* Vị trí 4 trồng cây có độ cao 6;
+* Vị trí 5 trồng cây có độ cao 7.
+
+Tổng độ chênh lệch nhỏ nhất là 5.
diff --git a/9/TP-HN-2014/cau1.pas b/9/TP-HN-2014/cau1.pas
new file mode 100644
index 0000000..466d4c4
--- /dev/null
+++ b/9/TP-HN-2014/cau1.pas
@@ -0,0 +1,46 @@
+var
+  f: text;
+  a, b, g: int64;
+  c, d: smallint;
+
+
+function gcd(x, y: int64): int64;
+  var z: int64;
+
+  begin
+    while y <> 0 do
+      begin
+        z := y; 
+        y := x mod y;
+        x := z
+      end;
+
+    gcd := a
+  end;
+
+
+begin
+  assign(f, 'CAU1.INP');
+  reset(f);
+  read(f, a, b, c, d);
+  close(f);
+
+  a := a * d - c * b;
+  b := b * d;
+
+  g := gcd(a, b);
+
+  a := a div g;
+  b := b div g;
+
+  if b < 0 then
+    begin
+      a := -a;
+      b := -b
+    end;
+
+  assign(f, 'CAU1.OUT');
+  rewrite(f);
+  writeln(f, a, ' ', b);
+  close(f)
+end.
diff --git a/9/TP-HN-2014/cau2.pas b/9/TP-HN-2014/cau2.pas
new file mode 100644
index 0000000..aed61ed
--- /dev/null
+++ b/9/TP-HN-2014/cau2.pas
@@ -0,0 +1,31 @@
+var
+  f: text;
+  n, i, j: smallint;
+  d: longint;
+  v: array of smallint;
+  t: array of real;
+
+begin
+  assign(f, 'CAU2.INP');
+  reset(f);
+  readln(f, n, d);
+  setlength(v, n);
+  for i := 0 to n - 1 do
+    read(f, v[i]);
+  close(f);
+
+  setlength(t, n);
+  for i := 0 to n - 1 do
+    t[i] := i + d / v[i];
+
+  d := 0;
+  for i := 1 to n - 1 do
+    for j := 0 to i - 1 do
+      if t[i] < t[j] then
+        inc(d);
+
+  assign(f, 'CAU2.OUT');
+  rewrite(f);
+  writeln(f, d);
+  close(f)
+end.
diff --git a/9/TP-HN-2014/cau3.pas b/9/TP-HN-2014/cau3.pas
new file mode 100644
index 0000000..1785da9
--- /dev/null
+++ b/9/TP-HN-2014/cau3.pas
@@ -0,0 +1,59 @@
+var
+  f: text;
+  s: string;
+  c: char;
+  a: array of byte;
+  i, j: byte;
+  tmp: byte = 0;
+
+
+function palin(
+  s: string;
+  l, h: byte
+): boolean;
+
+  begin
+    while l <= h do
+      begin
+        if s[l] <> s[h] then
+          exit(false);
+
+        inc(l);
+        dec(h);
+      end;
+
+    palin := true
+  end;
+
+
+
+begin
+  assign(f, 'CAU3.INP');
+  reset(f);
+  readln(f, s);
+  close(f);
+
+  setlength(a, 256);
+  for i := 0 to 255 do
+    a[i] := 0;
+
+  for c in s do
+    inc(a[ord(c)]);
+
+  for i in a do
+    if i > 0 then
+      inc(tmp);
+
+  assign(f, 'CAU3.OUT');
+  rewrite(f);
+  writeln(f, tmp);
+
+  tmp := 0;
+  for i := 1 to length(s) - 1 do
+    for j := i + tmp to length(s) do
+      if palin(s, i, j) then
+        tmp := j - i + 1;
+
+  writeln(f, tmp);
+  close(f)
+end.
diff --git a/9/TP-HN-2014/cau4.pas b/9/TP-HN-2014/cau4.pas
new file mode 100644
index 0000000..1e79c04
--- /dev/null
+++ b/9/TP-HN-2014/cau4.pas
@@ -0,0 +1,89 @@
+var
+  f: text;
+  n, k, i: smallint;
+  a, c: array of longint;
+  b: array of boolean;
+  d: longint = 0;
+
+
+procedure foo(
+  idx: smallint;
+  delta: longint
+);
+
+  var
+    i: smallint;
+    next: byte = 1;
+
+  begin
+    if (idx = k + 1) and (k > 0) then
+      delta := delta + abs(c[k] - c[k - 1]);
+
+    if delta >= d then
+      exit;
+
+    if idx + 1 = k then
+      inc(next);
+
+    if idx = n then
+      begin
+        d := delta;
+        exit
+      end;
+
+    for i := 0 to n - 2 do
+      if b[i] then
+        begin
+          b[i] := false;
+          c[idx] := a[i];
+
+          if idx > 0 then
+            foo(idx + next, delta + abs(c[idx] - c[idx - 1]))
+          else
+            foo(idx + next, 0);
+
+          b[i] := true;
+          c[idx] := 0
+        end
+  end;
+
+
+begin
+  assign(f, 'CAU4.INP');
+  reset(f);
+  readln(f, n, k);
+  setlength(a, n);
+  for i := 0 to n - 1 do
+    read(f, a[i]);
+  close(f);
+
+  setlength(c, n);
+  dec(k);
+  c[k] := a[k];
+
+  for i := 0 to k - 1 do
+    c[i] := 0;
+  for i := k + 1 to n - 1 do
+    c[i] := 0;
+
+  for i := 1 to n - 1 do
+    d := d + abs(a[i] - a[i - 1]);
+
+  for i := k to n - 2 do
+    a[i] := a[i + 1];
+  setlength(a, n - 1);
+
+  setlength(b, n - 1);
+  for i := 0 to n - 2 do
+    b[i] := true;
+
+  if k = 0 then
+    foo(1, 0)
+  else
+    foo(0, 0);
+
+  assign(f, 'CAU4.OUT');
+  rewrite(f);
+  writeln(f, d);
+  close(f)
+end.