From 2f674dc80f0382f1c3178f435714960734dc9d3c Mon Sep 17 00:00:00 2001 From: Nguyễn Gia Phong Date: Sat, 6 Jun 2020 21:33:13 +0700 Subject: Reorganize stuff from secondary school --- 2ndary/12/TP-HN-2008/R1/BL1.PAS | 26 +++++++++ 2ndary/12/TP-HN-2008/R1/BL2.PAS | 57 +++++++++++++++++++ 2ndary/12/TP-HN-2008/R1/BL3.PAS | 45 +++++++++++++++ 2ndary/12/TP-HN-2008/R1/BL4.pas | 62 ++++++++++++++++++++ 2ndary/12/TP-HN-2008/R1/CLB.IN | 4 ++ 2ndary/12/TP-HN-2008/R1/CLB.OU | 0 2ndary/12/TP-HN-2008/R1/R1.DOC | Bin 0 -> 79872 bytes 2ndary/12/TP-HN-2008/R2/README.md | 115 ++++++++++++++++++++++++++++++++++++++ 2ndary/12/TP-HN-2008/R2/dg.c | 102 +++++++++++++++++++++++++++++++++ 2ndary/12/TP-HN-2008/R2/hc.cpp | 73 ++++++++++++++++++++++++ 2ndary/12/TP-HN-2008/R2/tbc.pas | 69 +++++++++++++++++++++++ 11 files changed, 553 insertions(+) create mode 100644 2ndary/12/TP-HN-2008/R1/BL1.PAS create mode 100644 2ndary/12/TP-HN-2008/R1/BL2.PAS create mode 100644 2ndary/12/TP-HN-2008/R1/BL3.PAS create mode 100644 2ndary/12/TP-HN-2008/R1/BL4.pas create mode 100644 2ndary/12/TP-HN-2008/R1/CLB.IN create mode 100644 2ndary/12/TP-HN-2008/R1/CLB.OU create mode 100644 2ndary/12/TP-HN-2008/R1/R1.DOC create mode 100644 2ndary/12/TP-HN-2008/R2/README.md create mode 100644 2ndary/12/TP-HN-2008/R2/dg.c create mode 100644 2ndary/12/TP-HN-2008/R2/hc.cpp create mode 100644 2ndary/12/TP-HN-2008/R2/tbc.pas (limited to '2ndary/12/TP-HN-2008') diff --git a/2ndary/12/TP-HN-2008/R1/BL1.PAS b/2ndary/12/TP-HN-2008/R1/BL1.PAS new file mode 100644 index 0000000..6931b1b --- /dev/null +++ b/2ndary/12/TP-HN-2008/R1/BL1.PAS @@ -0,0 +1,26 @@ +uses math; + +var + f : text; + m, n, i : byte; + a, b : double; +j +begin + assign(f, 'LT.IN'); + reset(f); + read(f, n, m); + close(f); + a := 1; + for i := 1 to n do + a := a * 2; + b := 1; + for i := 1 to m do + b := b * 3; + a := a + b; + for i := 1 to trunc(log10(a)) do + a := a / 10; + assign(f, 'LT.OU'); + rewrite(f); + writeln(f, trunc(a)); + close(f) +end. diff --git a/2ndary/12/TP-HN-2008/R1/BL2.PAS b/2ndary/12/TP-HN-2008/R1/BL2.PAS new file mode 100644 index 0000000..e228240 --- /dev/null +++ b/2ndary/12/TP-HN-2008/R1/BL2.PAS @@ -0,0 +1,57 @@ +type + rect = record + a : longint; + b : longint + end; + arec = array of rect; + +var + f : text; + c, d, e : rect; + +function join(g, h : rect) : arec; + var n : byte = 0; + procedure j01n(p, q : longint); + begin + inc(n); + setlength(join, n); + join[n - 1].a := p; + join[n - 1].b := q + end; + begin + if g.a = h.a then j01n(g.a, g.b + h.b); + if g.a = h.b then j01n(g.a, g.b + h.a); + if g.b = h.a then j01n(g.b, g.a + h.b); + if g.b = h.b then j01n(g.b, g.a + h.a); + end; + +procedure out(m : longint); + begin + assign(f, 'GH.OU'); + rewrite(f); + writeln(f, m); + close(f); + halt + end; + +procedure libl2(x, y, z : rect); + var i, j : rect; + begin + for i in join(x, y) do + for j in join(z, i) do + if (j.a = j.b) and (j.a <> 0) then + out(j.a) + end; + +begin + assign(f, 'GH.IN'); + reset(f); + readln(f, c.a, c.b); + readln(f, d.a, d.b); + readln(f, e.a, e.b); + close(f); + libl2(c, d, e); + libl2(d, e, c); + libl2(e, c, d); + out(0) +end. diff --git a/2ndary/12/TP-HN-2008/R1/BL3.PAS b/2ndary/12/TP-HN-2008/R1/BL3.PAS new file mode 100644 index 0000000..a49b4d6 --- /dev/null +++ b/2ndary/12/TP-HN-2008/R1/BL3.PAS @@ -0,0 +1,45 @@ +type ar = array[0..3] of longint; + +var + f : text; + m, n, i, j : shortint; + a : array[1..101, -1..102] of longint; + tmp, max : longint; + +function next(x, y : shortint) : ar; + begin + next[0] := a[x + 1, y - 2]; + next[1] := a[x + 1, y + 2]; + next[2] := a[x + 2, y - 1]; + next[3] := a[x + 2, y + 1] + end; + +begin + for i := 1 to 101 do + for j := -1 to 102 do + a[i, j] := 0; + assign(f, 'QM.IN'); + reset(f); + readln(f, m, n); + for i := 1 to m do + for j := 1 to n do + read(f, a[i, j]); + close(f); + for i := m - 1 downto 1 do + for j := 1 to n do + begin + max := 0; + for tmp in next(i, j) do + if tmp > max then + max := tmp; + a[i, j] := a[i, j] + max; + end; + assign(f, 'QM.OU'); + rewrite(f); + max := 0; + for i := 1 to n do + if a[1, i] > max then + max := a[1, i]; + writeln(f, max); + close(f); +end. diff --git a/2ndary/12/TP-HN-2008/R1/BL4.pas b/2ndary/12/TP-HN-2008/R1/BL4.pas new file mode 100644 index 0000000..c552b0d --- /dev/null +++ b/2ndary/12/TP-HN-2008/R1/BL4.pas @@ -0,0 +1,62 @@ +var + f: text; + n, i: int16; + a, b: array of int32; + + +procedure swp(var x, y: int32); + var + tmp: int32; + + begin + tmp := x; + x := y; + y := tmp + end; + + +procedure qsort(l, h: int16); + var + i, j: int16; + tmp: int32; + + begin + i := l; + j := h; + tmp := a[(l + h) div 2]; + + repeat + while a[i] < tmp do + inc(i); + while a[j] > tmp do + dec(j); + + if i <= j then + begin + swp(a[i], a[j]); + swp(b[i], b[j]); + inc(i); + dec(j) + end; + until i > j; + + if l < j then + qsort(l, j); + if i < h then + qsort(i, h) + end; + + +begin + assign(f, 'CLB.IN'); + reset(f); + readln(f, n); + setlength(a, n); + setlength(b, n); + for i := 0 to n - 1 do + readln(f, a[i], b[i]); + close(f); + qsort(0, n - 1); + for i := 0 to n - 1 do + writeln(a[i], ' ', b[i]) +end. diff --git a/2ndary/12/TP-HN-2008/R1/CLB.IN b/2ndary/12/TP-HN-2008/R1/CLB.IN new file mode 100644 index 0000000..662c775 --- /dev/null +++ b/2ndary/12/TP-HN-2008/R1/CLB.IN @@ -0,0 +1,4 @@ +3 +7 9 +3 8 +10 20 diff --git a/2ndary/12/TP-HN-2008/R1/CLB.OU b/2ndary/12/TP-HN-2008/R1/CLB.OU new file mode 100644 index 0000000..e69de29 diff --git a/2ndary/12/TP-HN-2008/R1/R1.DOC b/2ndary/12/TP-HN-2008/R1/R1.DOC new file mode 100644 index 0000000..5e29da2 Binary files /dev/null and b/2ndary/12/TP-HN-2008/R1/R1.DOC differ diff --git a/2ndary/12/TP-HN-2008/R2/README.md b/2ndary/12/TP-HN-2008/R2/README.md new file mode 100644 index 0000000..00ccc3e --- /dev/null +++ b/2ndary/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 a1, a2, …, an. Số +ap (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 ap += (ai + aj + ak) / 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 ai + (|ai| < 108). + +### 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
4
3
6
3
5 | 2 | +| 3
1
2
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à ai, j. + +### 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à ai, j ≤ 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
2 1 9 1
5 0 3 4
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á 105. 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à (x1, +y1) và (x2, y2) trong đó x1, +y1, x2, y2 là các số nguyên và có giá trị +tuyệt đối không vượt quá 106. 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 x1, y1, x2, + y2. + +### 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
0 1
1 0
0 -1
-1 0
-2 0 0 0 | 100 | diff --git a/2ndary/12/TP-HN-2008/R2/dg.c b/2ndary/12/TP-HN-2008/R2/dg.c new file mode 100644 index 0000000..e2422df --- /dev/null +++ b/2ndary/12/TP-HN-2008/R2/dg.c @@ -0,0 +1,102 @@ +#include +#include + +#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/2ndary/12/TP-HN-2008/R2/hc.cpp b/2ndary/12/TP-HN-2008/R2/hc.cpp new file mode 100644 index 0000000..1ea6ee3 --- /dev/null +++ b/2ndary/12/TP-HN-2008/R2/hc.cpp @@ -0,0 +1,73 @@ +#include +#include +#include +#include +#include + +#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, greater> 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/2ndary/12/TP-HN-2008/R2/tbc.pas b/2ndary/12/TP-HN-2008/R2/tbc.pas new file mode 100644 index 0000000..1a26a91 --- /dev/null +++ b/2ndary/12/TP-HN-2008/R2/tbc.pas @@ -0,0 +1,69 @@ +var + f : text; + i, l, m, n : integer; + a : array[1..1000] of longint; + +procedure qsort(l, h : integer); + var + i, j : integer; + x, tmp : longint; + begin + i := l; + j := h; + x := a[(i + j) div 2]; + repeat + while a[i] < x do inc(i); + while x < a[j] do dec(j); + if i <= j then + begin + tmp := a[i]; + a[i] := a[j]; + a[j] := tmp; + inc(i); + dec(j) + end + until i > j; + if l < j then qsort(l, j); + if i < h then qsort(i, h) + end; + +function biin(n0 : integer) : boolean; + var l, h, m : integer; + begin + l := 1; + h := n; + repeat + m := (l + h) div 2; + if a[m] = n0 then exit(true); + if a[m] < n0 then l := m + 1 + else h := m - 1 + until l > h; + biin := false + end; + +function libtbc(n0 : integer) : boolean; + var i, j : integer; + begin + for i := 1 to n0 - 1 do + for j := n0 + 1 to n do + if biin(a[n0] * 3 - a[i] - a[j]) then + exit(true); + libtbc := false + end; + +begin + assign(f, 'TBC.INP'); + reset(f); + readln(f, n); + for i := 1 to n do readln(f, a[i]); + close(f); + qsort(1, n); + m := 0; + for l := 2 to n - 1 do + if libtbc(l) then + inc(m); + assign(f, 'TBC.OUT'); + rewrite(f); + writeln(f, m); + close(f) +end. -- cgit 1.4.1