Thêm đề 12 Thanh Hoá 2008-2009

9 files changed, 596 insertions, 0 deletions

diff --git a/12/TP-ThanhHoá-2009/BAI4.PAS b/12/TP-ThanhHoá-2009/BAI4.PAS
new file mode 100644
index 0000000..8706032
--- /dev/null
+++ b/12/TP-ThanhHoá-2009/BAI4.PAS
@@ -0,0 +1,29 @@
+const
+  m: array[1..9] of byte = (0, 0, 1, 1, 0, 0, 4, 7, 0);
+  equa: array[1..9] of ansistring = (
+    #10,
+    #10,
+    #10'1+2-3=0'#10,
+    #10'1-2-3+4=0'#10,
+    #10,
+    #10,
+    #10'1+2-3+4-5-6+7=0'#10'1+2-3-4+5+6-7=0'#10'1-2+3+4-5+6-7=0'#10'1-2-3-4-5+6+7=0'#10,
+    #10'1+2+3+4-5-6-7+8=0'#10'1+2+3-4+5-6+7-8=0'#10'1+2-3+4+5+6-7-8=0'#10'1+2-3-4-5-6+7+8=0'#10'1-2+3-4-5+6-7+8=0'#10'1-2-3+4+5-6-7+8=0'#10'1-2-3+4-5+6+7-8=0'#10,
+    #10
+  );
+
+var
+  n: byte;
+  f: text;
+
+begin
+  assign(f, 'BAI4.INP');
+  reset(f);
+  read(f, n);
+  close(f);
+
+  assign(f, 'BAI4.OUT');
+  rewrite(f);
+  write(f, m[n], equa[n]);
+  close(f)
+end.
diff --git a/12/TP-ThanhHoá-2009/README.md b/12/TP-ThanhHoá-2009/README.md
new file mode 100644
index 0000000..b64db6b
--- /dev/null
+++ b/12/TP-ThanhHoá-2009/README.md
@@ -0,0 +1,173 @@
+# Kì thi học sinh giỏi tỉnh Thanh Hoá lớp 12 năm học 2008 - 2009
+
+Sở Giáo dục và Đào tạo Thanh Hoá
+
+Môn thi: Tin học
+
+Ngày thi: 28/03/2009
+
+Thời gian: 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 |  Điểm |
+| :---: | :--------------: | :-------------: | :------------: | :---: |
+|   1   |     BAI1.PAS     |     BAI1.INP    |    BAI1.OUT    |   5   |
+|   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   |
+
+Giới hạn thời gian cho mỗi test là 3 giây.
+
+Dữ liệu vào là đúng đắn, không cần phải kiểm tra.
+
+## Bài 1: Số nguyên tố
+
+Cho dãy số gồm có N số nguyên dương a<sub>1</sub>, a<sub>2</sub>, …,
+a<sub>N</sub> và một số nguyên dương K.
+
+### Yêu cầu
+
+Hãy cho biết số lượng các phần tử có giá trị nhỏ hơn K là số nguyên tố của dãy
+số trên.
+
+### Dữ liệu
+
+* Dòng đầu tiên là hai số N và K.
+* Dòng tiếp theo lần lượt là N số nguyên của dãy số.
+
+### Kết quả
+
+Số M là số lượng các phần tử của dãy số thoả mãn yêu cầu đề bài.
+
+### Giới hạn
+
+* 0 < N < 50000
+* 0 < K, a<sub>i</sub> < 5000 với mọi i = 1, 2, …, N
+
+### Ví dụ
+
+|        BAI1.INP       | BAI1.OUT |
+| --------------------- | :------: |
+| 7 8<br>1 2 3 8 7 6 11 |     3    |
+
+## Bài 2: Trung bình cộng
+
+Cho dãy gồm n số nguyên a<sub>1</sub>, a<sub>2</sub>, …, a<sub>n</sub> và số
+nguyên K. 
+
+### Yêu cầu
+
+Cho biết trong dãy số đã cho có tồn tại hay không một cặp số mà trung bình cộng
+của chúng là K.
+
+### Dữ liệu
+
+* Dòng đầu tiên ghi hai số n, K.
+* Dòng tiếp theo lần lượt ghi n số a<sub>1</sub>, a<sub>2</sub>, …,
+  a<sub>n</sub>. Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu
+  cách trống. 
+
+### Kết quả
+
+* Số 1 nếu tồn tại một cặp số thoả mãn yêu cầu bài toán.
+* Số 0 nếu không tồn tại cặp số nào thoả mãn yêu cầu bài toán.
+
+### Giới hạn
+
+* 0 < N < 50000
+* |K|, |ai| < 1000 với mọi i = 1, 2, …, n
+
+### Ví dụ
+
+|    BAI2.INP    | BAI2.OUT |
+| -------------- | :------: |
+| 4 5<br>0 2 6 4 |     1    |
+| 3 3<br>1 2 3   |     0    |
+
+## Bài 3: Xâu đối xứng
+
+Xâu đối xứng là xâu đọc giống nhau nếu ta bắt đầu đọc từ trái qua phải hoặc từ
+phải qua trái. Ví dụ, xâu `RADAR` là xâu đối xứng, xâu `TOMATO` không phải là
+xâu đối xứng.
+
+### Yêu cầu
+
+Cho một xâu S gồm không quá 200 kí tự. Cho biết S có phải là xâu đối xứng hay
+không? Nếu không, cho biết số kí tự ít nhất cần thêm vào S để S trở thành xâu
+đối xứng.
+
+### Dữ liệu
+
+Gồm duy nhất 1 dòng ghi xâu S.
+
+### Kết quả
+
+Số k là số kí tự ít nhất cần thêm vào S để S trở thành xâu đối xứng. Nếu xâu S
+đã cho là đối xứng thì ghi k = 0.
+
+### Ví dụ
+
+| BAI3.INP | BAI3.OUT |
+| :------: | :------: |
+|   RADAR  |     0    |
+|  TOMATO  |     3    |
+
+## Bài 4: Biểu thức Zero
+
+Cuội viết liên tiếp các số tự nhiên từ 1 đến N thành dãy: 1 2 3 … N. Cuội đố
+Bờm điền các dấu phép toán + hoặc - vào giữa 2 số tự nhiên liên tiếp sao cho
+biểu thức thu được có kết quả bằng 0.
+
+### Yêu cầu
+
+Bạn hãy giúp Bờm viết chương trình liệt kê tất cả các cách điền dấu phép toán
+thích hợp.
+
+### Dữ liệu
+
+Gồm 1 dòng duy nhất ghi số N (N < 10).
+
+### Kết quả
+
+* Dòng đầu tiên ghi số M là số cách điền dấu vào biểu thức.
+* M dòng tiếp theo, mỗi dòng ghi một kết quả tìm được.
+
+### Ví dụ
+
+| BAI4.INP |   BAI4.OUT   |
+| :------: | ------------ |
+|     2    | 0            |
+|     3    | 1<br>1+2-3=0 |
+
+## Bài 5: Miền 0
+
+Cho một hình chữ nhật gồm M hàng, N cột, được chia thành MxN ô vuông. Mỗi ô
+vuông được ghi một trong hai số nguyên 0 hoặc 1. 
+
+Miền 0 là một miền liên tục các số 0 thuộc các ô chung cạnh với nhau. Diện tích
+miền là số lượng các ô vuông cùng giá trị thuộc miền đó.
+
+### Yêu cầu
+
+Tính diện tích miền 0 lớn nhất của hình chữ nhật đã cho.
+
+### Dữ liệu
+
+* Dòng đầu tiên ghi hai số M, N.
+* M dòng tiếp theo, mỗi dòng ghi N số lần lượt là giá trị các ô trong bảng số.
+
+### Kết quả
+
+Số nguyên duy nhất là diện tích miền 0 lớn nhất.
+
+### Giới hạn
+
+1 < M, N < 100.
+
+### Ví dụ
+
+|               BAI5.INP               | BAI5.OUT |
+| ------------------------------------ | :------: |
+| 3 4<br>0 0 0 1<br>1 1 0 1<br>0 0 1 0 |     4    |
diff --git a/12/TP-ThanhHoá-2009/bai1.pas b/12/TP-ThanhHoá-2009/bai1.pas
new file mode 100644
index 0000000..511d074
--- /dev/null
+++ b/12/TP-ThanhHoá-2009/bai1.pas
@@ -0,0 +1,39 @@
+var
+  prime: array[1..4999] of boolean;
+  n, i, k, a, j: word;
+  f: text;
+
+begin
+  fillchar(prime, sizeof(prime), true);
+  prime[1] := false;
+
+  for i := 2 to 70 do
+    if prime[i] then
+      for j := 2 to 4999 div i do
+        prime[i * j] := false;
+
+  for i := 1 to 4999 do
+    if prime[i] then
+      writeln(i);
+
+  assign(f, 'BAI1.INP');
+  reset(f);
+
+  readln(f, n, k);
+
+  j := 0;
+  for i := 1 to n do
+    begin
+      read(f, a);
+      if (a < k) and
+         prime[a] then
+        inc(j)
+    end;
+
+  close(f);
+
+  assign(f, 'BAI1.OUT');
+  rewrite(f);
+  writeln(f, j);
+  close(f)
+end.
diff --git a/12/TP-ThanhHoá-2009/bai2.pas b/12/TP-ThanhHoá-2009/bai2.pas
new file mode 100644
index 0000000..5b43c06
--- /dev/null
+++ b/12/TP-ThanhHoá-2009/bai2.pas
@@ -0,0 +1,41 @@
+var
+  n: word;
+  k, a: smallint;
+  f: text;
+  b: array[-999..999] of byte;
+
+
+function libai2(): byte;
+  var
+    i: smallint;
+
+  begin
+    for i := -999 to k - 1 do
+      if (b[i] > 0) and
+         (b[k * 2 - i] > 0) then
+        exit(1);
+
+    if b[k] > 1 then
+      exit(1);
+
+    exit(0)
+  end;
+
+
+begin
+  assign(f, 'BAI2.INP');
+  reset(f);
+  readln(f, n, k);
+  fillchar(b, sizeof(b), 0);
+  repeat
+    read(f, a);
+    inc(b[a]);
+    dec(n)
+  until n = 0;
+  close(f);
+
+  assign(f, 'BAI2.OUT');
+  rewrite(f);
+  writeln(f, libai2());
+  close(f)
+end.
diff --git a/12/TP-ThanhHoá-2009/bai4.pas b/12/TP-ThanhHoá-2009/bai4.pas
new file mode 100644
index 0000000..04839af
--- /dev/null
+++ b/12/TP-ThanhHoá-2009/bai4.pas
@@ -0,0 +1,72 @@
+var
+  f: text;
+  n, i: shortint;
+  a: array of string;
+
+
+function minus(num, bit: shortint): boolean;
+  begin
+    minus := num shr bit mod 2 = 1
+  end;
+
+
+function cal(n, b: shortint): boolean;
+  var
+    i, s: shortint;
+
+  begin
+    s := 0;
+
+    for i := 2 to n do
+      if minus(b, n - i) then
+        s := s - i
+      else
+        s := s + i;
+
+    cal := s = -1
+  end;
+
+
+function equa(n, b: shortint): string;
+  var
+    i: shortint;
+
+  begin
+    equa := '1';
+
+    for i := 2 to n do
+      begin
+        if minus(b, n - i) then
+          equa := equa + '-'
+        else
+          equa := equa + '+';
+
+        equa := equa + char(i + 48)
+      end;
+
+    equa := equa + '=0'
+  end;
+
+
+begin
+  assign(f, 'BAI4.INP');
+  reset(f);
+  readln(f, n);
+  close(f);
+  setlength(a, 0);
+
+  if n mod 4 mod 3 = 0 then
+    for i := 1 to 1 shl (n - 1) - 1 do
+      if cal(n, i) then
+        begin
+          setlength(a, length(a) + 1);
+          a[length(a) - 1] := equa(n, i)
+        end;
+
+  assign(f, 'BAI4.OUT');
+  rewrite(f);
+  writeln(f, length(a));
+  for i := 0 to length(a) - 1 do
+    writeln(f, a[i]);
+  close(f)
+end.
diff --git a/12/TP-ThanhHoá-2009/bai4.py b/12/TP-ThanhHoá-2009/bai4.py
new file mode 100755
index 0000000..f5c5a26
--- /dev/null
+++ b/12/TP-ThanhHoá-2009/bai4.py
@@ -0,0 +1,28 @@
+#!/usr/bin/env python3
+
+
+def ops(number, length):
+    b = bin(number)[2:]
+    return '+' * (length - len(b)) + b.replace('0', '+').replace('1', '-')
+
+
+def libai4(n):
+    seq, l = list(range(1, n + 1)), []
+
+    for i in range(2 ** (n - 1)):
+        s = ''.join(["{}{}".format(*j) for j in zip(ops(i, n), seq)])[1:]
+        if eval(s) == 0:
+            l.append(s + '=0\n')
+
+    return l
+
+
+if __name__ == '__main__':
+    with open('BAI4.INP') as f:
+        n = int(f.read())
+
+    with open('BAI4.OUT', 'w') as f:
+        l = libai4(n)
+        f.write('{}\n'.format(len(l)))
+        for s in l:
+            f.write(s)
diff --git a/12/TP-ThanhHoá-2009/bai4pas_srcgen.py b/12/TP-ThanhHoá-2009/bai4pas_srcgen.py
new file mode 100755
index 0000000..e345caa
--- /dev/null
+++ b/12/TP-ThanhHoá-2009/bai4pas_srcgen.py
@@ -0,0 +1,19 @@
+#!/usr/bin/env python3
+
+from bai4 import libai4
+
+
+with open("BAI4.PAS", "w") as f:
+    f.write("const\n  m: array[1..9] of byte = (")
+    l = [libai4(i) for i in range(1, 10)]
+    f.write(", ".join([str(len(i)) for i in l]))
+    f.write(");\n  equa: array[1..9] of ansistring = (\n");
+    l0 = []
+    for i in l:
+        s = "    #10" + "".join(["'" + j.replace("\n", "'#10") for j in i])
+        l0.append(s)
+    f.write(",\n".join(l0))
+    f.write("\n  );\n\nvar\n  n: byte;\n  f: text;\n\nbegin\n")
+    f.write("  assign(f, 'BAI4.INP');\n  reset(f);\n  read(f, n);\n")
+    f.write("  close(f);\n\n  assign(f, 'BAI4.OUT');\n  rewrite(f);\n")
+    f.write("  write(f, m[n], equa[n]);\n  close(f)\nend.\n")
diff --git a/12/TP-ThanhHoá-2009/bai5.pas b/12/TP-ThanhHoá-2009/bai5.pas
new file mode 100644
index 0000000..867b9d2
--- /dev/null
+++ b/12/TP-ThanhHoá-2009/bai5.pas
@@ -0,0 +1,112 @@
+uses
+  sortnfind;
+
+var
+  f: text;
+  rect: array of boolean;
+  mem: array of intar;
+  m, n: byte;
+  tmp, i, idx0, idx1: smallint;
+
+
+function locate(x: smallint): smallint;
+  var
+    i: smallint;
+
+  begin
+    for i := 0 to length(mem) - 1 do
+      if binin(mem[i], x) then
+        exit(i)
+  end;
+
+
+procedure mv(
+  src: intar;
+  var dest: intar
+);
+
+  var
+    lendest, lensrc, i: smallint;
+
+  begin
+    lendest := length(dest);
+    lensrc := length(src);
+    setlength(dest, lendest + lensrc);
+
+    for i := 0 to lensrc - 1 do
+      dest[i + lendest] := src[i];
+
+    setlength(src, 0);
+    qsort(dest)
+  end;
+
+
+begin
+  assign(f, 'BAI5.INP');
+  reset(f);
+  readln(f, m, n);
+  setlength(rect, m * n);
+
+  for i := 0 to m * n - 1 do
+    begin
+      read(f, tmp);
+
+      if tmp = 0 then
+        rect[i] := true
+      else
+        rect[i] := false
+    end;
+  close(f);
+
+  setlength(mem, 0);
+
+  for i := 0 to m * n - 1 do
+    if rect[i] then
+      begin
+        idx0 := -1;
+        idx1 := -1;
+
+        if (i > 0) and rect[i - 1] then
+          idx0 := locate(i - 1);
+
+        if (i >= n) and rect[i - n] then
+          if idx0 = -1 then
+            idx0 := locate(i - n)
+          else
+            begin
+              tmp := locate(i - n);
+
+              if tmp < idx0 then
+                begin
+                  idx1 := idx0;
+                  idx0 := tmp
+                end
+              else if tmp > idx0 then
+                idx1 := tmp
+            end;
+
+        if idx0 + idx1 = -2 then
+          begin
+            setlength(mem, length(mem) + 1);
+            setlength(mem[length(mem) - 1], 1);
+            mem[length(mem) - 1][0] := i;
+            continue
+          end;
+
+        setlength(mem[idx0], length(mem[idx0]) + 1);
+        mem[idx0][length(mem[idx0]) - 1] := i;
+
+        if idx1 > 0 then
+          mv(mem[idx1], mem[idx0])
+      end;
+
+  tmp := 0;
+  for i := 0 to length(mem) - 1 do
+    if length(mem[i]) > tmp then
+      tmp := length(mem[i]);
+
+  assign(f, 'BAI5.OUT');
+  rewrite(f);
+  writeln(f, tmp);
+  close(f)
+end.
diff --git a/12/TP-ThanhHoá-2009/sortnfind.pas b/12/TP-ThanhHoá-2009/sortnfind.pas
new file mode 100644
index 0000000..52e8d6b
--- /dev/null
+++ b/12/TP-ThanhHoá-2009/sortnfind.pas
@@ -0,0 +1,83 @@
+unit sortnfind;
+
+interface
+
+  type
+    intar = array of smallint;
+
+  procedure qsort(var a : intar);
+
+  function binin(
+    a: intar;
+    x: smallint
+  ): boolean;
+
+implementation
+
+  procedure qsort(var a : intar);
+
+    procedure sort(l, r: longint);
+      var
+        i, j, x, y: longint;
+
+      begin
+        i := l;
+        j := r;
+        x := a[(l + r) div 2];
+
+        repeat
+          while a[i] < x do
+            inc(i);
+
+          while x < a[j] do
+            dec(j);
+
+          if i <= j then
+            begin
+              y := a[i];
+              a[i] := a[j];
+              a[j] := y;
+              inc(i);
+              j := j - 1
+            end
+        until i > j;
+
+        if l < j then
+          sort(l, j);
+
+        if i < r then
+          sort(i, r)
+      end;
+
+    begin
+       sort(0, length(a) - 1)
+    end;
+
+
+  function binin(
+    a: intar;
+    x: smallint
+  ): boolean;
+
+    var
+      l, h, mid: word;
+
+    begin
+      l := 0;
+      h := length(a) - 1;
+
+      while l <= h do
+        begin
+          mid := (l + h) div 2;
+          if x = a[mid] then
+            exit(true)
+          else if x < a[mid] then
+            h := mid - 1
+          else
+            l := mid + 1
+        end;
+
+      binin := false
+    end;
+
+end.