From f97ad3e9e225a288e7a8a53c2ef0acb45a47dbde Mon Sep 17 00:00:00 2001 From: Raphael McSinyx Date: Sat, 19 Nov 2016 19:00:47 +0700 Subject: Thêm đề 12 Thanh Hoá 2008-2009 MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- "12/TP-ThanhHo\303\241-2009/BAI4.PAS" | 29 +++++ "12/TP-ThanhHo\303\241-2009/README.md" | 173 +++++++++++++++++++++++++ "12/TP-ThanhHo\303\241-2009/bai1.pas" | 39 ++++++ "12/TP-ThanhHo\303\241-2009/bai2.pas" | 41 ++++++ "12/TP-ThanhHo\303\241-2009/bai4.pas" | 72 ++++++++++ "12/TP-ThanhHo\303\241-2009/bai4.py" | 28 ++++ "12/TP-ThanhHo\303\241-2009/bai4pas_srcgen.py" | 19 +++ "12/TP-ThanhHo\303\241-2009/bai5.pas" | 112 ++++++++++++++++ "12/TP-ThanhHo\303\241-2009/sortnfind.pas" | 83 ++++++++++++ 9 files changed, 596 insertions(+) create mode 100644 "12/TP-ThanhHo\303\241-2009/BAI4.PAS" create mode 100644 "12/TP-ThanhHo\303\241-2009/README.md" create mode 100644 "12/TP-ThanhHo\303\241-2009/bai1.pas" create mode 100644 "12/TP-ThanhHo\303\241-2009/bai2.pas" create mode 100644 "12/TP-ThanhHo\303\241-2009/bai4.pas" create mode 100755 "12/TP-ThanhHo\303\241-2009/bai4.py" create mode 100755 "12/TP-ThanhHo\303\241-2009/bai4pas_srcgen.py" create mode 100644 "12/TP-ThanhHo\303\241-2009/bai5.pas" create mode 100644 "12/TP-ThanhHo\303\241-2009/sortnfind.pas" (limited to '12') diff --git "a/12/TP-ThanhHo\303\241-2009/BAI4.PAS" "b/12/TP-ThanhHo\303\241-2009/BAI4.PAS" new file mode 100644 index 0000000..8706032 --- /dev/null +++ "b/12/TP-ThanhHo\303\241-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\303\241-2009/README.md" "b/12/TP-ThanhHo\303\241-2009/README.md" new file mode 100644 index 0000000..b64db6b --- /dev/null +++ "b/12/TP-ThanhHo\303\241-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 a1, a2, …, +aN 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, ai < 5000 với mọi i = 1, 2, …, N + +### Ví dụ + +| BAI1.INP | BAI1.OUT | +| --------------------- | :------: | +| 7 8
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 a1, a2, …, an 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ố a1, a2, …, + an. 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
0 2 6 4 | 1 | +| 3 3
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
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
0 0 0 1
1 1 0 1
0 0 1 0 | 4 | diff --git "a/12/TP-ThanhHo\303\241-2009/bai1.pas" "b/12/TP-ThanhHo\303\241-2009/bai1.pas" new file mode 100644 index 0000000..511d074 --- /dev/null +++ "b/12/TP-ThanhHo\303\241-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\303\241-2009/bai2.pas" "b/12/TP-ThanhHo\303\241-2009/bai2.pas" new file mode 100644 index 0000000..5b43c06 --- /dev/null +++ "b/12/TP-ThanhHo\303\241-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\303\241-2009/bai4.pas" "b/12/TP-ThanhHo\303\241-2009/bai4.pas" new file mode 100644 index 0000000..04839af --- /dev/null +++ "b/12/TP-ThanhHo\303\241-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\303\241-2009/bai4.py" "b/12/TP-ThanhHo\303\241-2009/bai4.py" new file mode 100755 index 0000000..f5c5a26 --- /dev/null +++ "b/12/TP-ThanhHo\303\241-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\303\241-2009/bai4pas_srcgen.py" "b/12/TP-ThanhHo\303\241-2009/bai4pas_srcgen.py" new file mode 100755 index 0000000..e345caa --- /dev/null +++ "b/12/TP-ThanhHo\303\241-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\303\241-2009/bai5.pas" "b/12/TP-ThanhHo\303\241-2009/bai5.pas" new file mode 100644 index 0000000..867b9d2 --- /dev/null +++ "b/12/TP-ThanhHo\303\241-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\303\241-2009/sortnfind.pas" "b/12/TP-ThanhHo\303\241-2009/sortnfind.pas" new file mode 100644 index 0000000..52e8d6b --- /dev/null +++ "b/12/TP-ThanhHo\303\241-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. -- cgit 1.4.1