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/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 +++++++++++++++++++++++ 4 files changed, 359 insertions(+) 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/R2') 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