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 --- 12/TP-HN-2008/R2/README.md | 115 --------------------------------------------- 12/TP-HN-2008/R2/dg.c | 102 ---------------------------------------- 12/TP-HN-2008/R2/hc.cpp | 73 ---------------------------- 12/TP-HN-2008/R2/tbc.pas | 69 --------------------------- 4 files changed, 359 deletions(-) delete mode 100644 12/TP-HN-2008/R2/README.md delete mode 100644 12/TP-HN-2008/R2/dg.c delete mode 100644 12/TP-HN-2008/R2/hc.cpp delete mode 100644 12/TP-HN-2008/R2/tbc.pas (limited to '12/TP-HN-2008/R2') diff --git a/12/TP-HN-2008/R2/README.md b/12/TP-HN-2008/R2/README.md deleted file mode 100644 index 00ccc3e..0000000 --- a/12/TP-HN-2008/R2/README.md +++ /dev/null @@ -1,115 +0,0 @@ -# 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/12/TP-HN-2008/R2/dg.c b/12/TP-HN-2008/R2/dg.c deleted file mode 100644 index e2422df..0000000 --- a/12/TP-HN-2008/R2/dg.c +++ /dev/null @@ -1,102 +0,0 @@ -#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/12/TP-HN-2008/R2/hc.cpp b/12/TP-HN-2008/R2/hc.cpp deleted file mode 100644 index 1ea6ee3..0000000 --- a/12/TP-HN-2008/R2/hc.cpp +++ /dev/null @@ -1,73 +0,0 @@ -#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/12/TP-HN-2008/R2/tbc.pas b/12/TP-HN-2008/R2/tbc.pas deleted file mode 100644 index 1a26a91..0000000 --- a/12/TP-HN-2008/R2/tbc.pas +++ /dev/null @@ -1,69 +0,0 @@ -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