Add NTU/{pali2,editpic}.c and update README.md

9 files changed, 521 insertions, 0 deletions

diff --git a/09/Q-Huế-2014/README.md b/09/Q-Huế-2014/README.md
new file mode 100644
index 0000000..2da9e8e
--- /dev/null
+++ b/09/Q-Huế-2014/README.md
@@ -0,0 +1,53 @@
+# THI CHỌN HỌC SINH GIỎI CẤP THÀNH PHỐ
+
+UBND THÀNH PHỐ HUẾ
+
+PHÒNG GIÁO DỤC VÀ ĐÀO TẠO
+
+MÔN TIN HỌC - NĂM HỌC: 2013-2014
+
+Thời gian: 120 phút (Không kể thời gian giao đề)
+
+## Bài 1 (3 điểm)
+
+Hai số tự nhiên `n`, `m` được gọi là nguyên tố tương đương nếu chúng có chung
+các ước số nguyên tố.
+
+Hãy viết chương trình nhập vào hai số `n`, `m` và kiểm
+tra chúng có là nguyên tố tương đương với nhau hay không.
+
+**Ví dụ:** Số 75 và số 15 là nguyên tố tương đương vì chúng có cùng các ước số
+nguyên tố là 3 và 5. 
+
+## Bài 2 (3 điểm)
+
+Cho hệ phương trình bậc nhất hai ẩn:
+
+    ax + by = c
+    a'x + b'y = c'
+
+Hãy viết chương trình giải hệ phương trình trên, đồng thời xác định vị trí
+tương đối của hai đường thẳng `d: ax + by = c` và `d': a'x + b'y =c'` đã tạo
+nên hệ phương trình.
+
+## Bài 3 (4 điểm)
+
+Cho hai xâu `X`, `Y` chứa các kí tự số từ 0 đến 9 và không dài quá 250 kí tự.
+
+Hãy viết chương trình tạo ra xâu `ST` thoả mãn các điều kiện sau:
+
+* Gồm các kí tự số vừa có mặt ở xâu `X`, vừa có mặt ở xâu `Y`
+* Các kí tự số trong xâu `ST` chỉ xuất hiện duy nhất một lần
+* Giá trị xâu `ST` nhận được là một số đạt giá trị lớn nhất
+
+Dữ liệu vào cho bởi file `INPUT.INP` chứa giá trị xâu `X` và xâu `Y`, mỗi xâu
+nằm trên một dòng.
+
+Dữ liệu ra chứa ở file `OUTPUT.OUT` là số lớn nhất nhận được.
+
+**Ví dụ:**
+
+| INPUT.INP | OUTPUT.OUT |
+| --------- | ---------- |
+| 19012304  | 43210      |
+| 034012    |            |
diff --git a/09/Q-Huế-2014/bai1.pas b/09/Q-Huế-2014/bai1.pas
new file mode 100644
index 0000000..7bd0d92
--- /dev/null
+++ b/09/Q-Huế-2014/bai1.pas
@@ -0,0 +1,15 @@
+var
+  n, m, p: qword;
+
+begin
+  read(n, m);
+
+  while m <> 0 do
+    begin
+      p := n mod m;
+      n := m;
+      m := p
+    end;
+
+  writeln(n <> 1)
+end.
diff --git a/09/Q-Huế-2014/bai2.pas b/09/Q-Huế-2014/bai2.pas
new file mode 100644
index 0000000..172137d
--- /dev/null
+++ b/09/Q-Huế-2014/bai2.pas
@@ -0,0 +1,35 @@
+var
+  a, b, c, e, p, k, tmp: real;
+
+function det(a, b, c, d: real): real;
+  begin
+    exit(a * d - b * c)
+  end;
+
+begin
+  read(a, b, c, e, p, k);
+
+  tmp := det(a, b, e, p);
+  
+  if tmp <> 0 then
+    begin
+      writeln('x = ', (det(c, b, k, p) / tmp):0:6);
+      writeln('y = ', (det(a, c, e, k) / tmp):0:6);
+      writeln('Hai đường thẳng cắt nhau.')
+    end
+  else if c <> k then
+    begin
+      writeln('Phương trình vô nghiệm.');
+      writeln('Hai đường thẳng song song.')
+    end
+  else
+    begin
+      if a = 0 then
+        writeln('y = ',  (c / b):0:6)
+      else if b = 0 then
+        writeln('x = ', (c / a):0:6)
+      else
+        writeln('x = ', (-b / a):0:6, 'y + ', (c / a):0:6);
+      writeln('Hai đường thẳng trùng nhau.')
+    end;
+end.
diff --git a/09/Q-Huế-2014/bai3.pas b/09/Q-Huế-2014/bai3.pas
new file mode 100644
index 0000000..91fc05f
--- /dev/null
+++ b/09/Q-Huế-2014/bai3.pas
@@ -0,0 +1,34 @@
+var
+  x, y: string;
+  f: text;
+  a: array[0 .. 9] of shortint;
+  b: shortint;
+  c: char;
+
+begin
+  assign(f, 'INPUT.INP');
+  reset(f);
+  readln(f, x);
+  readln(f, y);
+  close(f);
+
+  fillchar(a, 0, sizeof(a));
+
+  for c in x do
+    a[ord(c) - 48] := 1;
+
+  for c in y do
+    begin
+      b := ord(c) - 48;
+      if a[b] = 1 then
+        a[b] := 2
+    end;
+
+  assign(f, 'OUTPUT.OUT');
+  rewrite(f);
+  for b := 9 downto 0 do
+    if a[b] = 2 then
+      write(f, b);
+  writeln(f);
+  close(f)
+end.
diff --git a/09/TP-HN-2014/README.md b/09/TP-HN-2014/README.md
new file mode 100644
index 0000000..8a21e84
--- /dev/null
+++ b/09/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/09/TP-HN-2014/cau1.pas b/09/TP-HN-2014/cau1.pas
new file mode 100644
index 0000000..466d4c4
--- /dev/null
+++ b/09/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/09/TP-HN-2014/cau2.pas b/09/TP-HN-2014/cau2.pas
new file mode 100644
index 0000000..aed61ed
--- /dev/null
+++ b/09/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/09/TP-HN-2014/cau3.pas b/09/TP-HN-2014/cau3.pas
new file mode 100644
index 0000000..1785da9
--- /dev/null
+++ b/09/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/09/TP-HN-2014/cau4.pas b/09/TP-HN-2014/cau4.pas
new file mode 100644
index 0000000..1e79c04
--- /dev/null
+++ b/09/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.