From 95b46c031c06a7e0e2d3744185ea3a6c3fa866bf Mon Sep 17 00:00:00 2001 From: Raphael McSinyx Date: Fri, 25 Aug 2017 15:21:07 +0700 Subject: Revise 12/TP-HN-2008/R2 --- 12/TP-HN-2008/R2/DG | Bin 133348 -> 0 bytes 12/TP-HN-2008/R2/DG.INP | 6 --- 12/TP-HN-2008/R2/DG.OUT | 1 - 12/TP-HN-2008/R2/DG.o | Bin 9392 -> 0 bytes 12/TP-HN-2008/R2/DG.pas | 83 -------------------------------- 12/TP-HN-2008/R2/HC.pas | 23 --------- 12/TP-HN-2008/R2/R2.doc | Bin 64512 -> 0 bytes 12/TP-HN-2008/R2/README.md | 115 +++++++++++++++++++++++++++++++++++++++++++++ 12/TP-HN-2008/R2/TBC.PAS | 69 --------------------------- 12/TP-HN-2008/R2/dg.c | 102 ++++++++++++++++++++++++++++++++++++++++ 12/TP-HN-2008/R2/hc.cpp | 73 ++++++++++++++++++++++++++++ 12/TP-HN-2008/R2/tbc.pas | 69 +++++++++++++++++++++++++++ 12 files changed, 359 insertions(+), 182 deletions(-) delete mode 100755 12/TP-HN-2008/R2/DG delete mode 100755 12/TP-HN-2008/R2/DG.INP delete mode 100755 12/TP-HN-2008/R2/DG.OUT delete mode 100755 12/TP-HN-2008/R2/DG.o delete mode 100755 12/TP-HN-2008/R2/DG.pas delete mode 100644 12/TP-HN-2008/R2/HC.pas delete mode 100755 12/TP-HN-2008/R2/R2.doc create mode 100644 12/TP-HN-2008/R2/README.md delete mode 100755 12/TP-HN-2008/R2/TBC.PAS create mode 100644 12/TP-HN-2008/R2/dg.c create mode 100644 12/TP-HN-2008/R2/hc.cpp create mode 100755 12/TP-HN-2008/R2/tbc.pas diff --git a/12/TP-HN-2008/R2/DG b/12/TP-HN-2008/R2/DG deleted file mode 100755 index ad902a1..0000000 Binary files a/12/TP-HN-2008/R2/DG and /dev/null differ diff --git a/12/TP-HN-2008/R2/DG.INP b/12/TP-HN-2008/R2/DG.INP deleted file mode 100755 index fb3ca57..0000000 --- a/12/TP-HN-2008/R2/DG.INP +++ /dev/null @@ -1,6 +0,0 @@ -4 -0 1 -1 0 -0 -1 --1 0 --2 0 0 0 diff --git a/12/TP-HN-2008/R2/DG.OUT b/12/TP-HN-2008/R2/DG.OUT deleted file mode 100755 index c227083..0000000 --- a/12/TP-HN-2008/R2/DG.OUT +++ /dev/null @@ -1 +0,0 @@ -0 \ No newline at end of file diff --git a/12/TP-HN-2008/R2/DG.o b/12/TP-HN-2008/R2/DG.o deleted file mode 100755 index cf2e3e1..0000000 Binary files a/12/TP-HN-2008/R2/DG.o and /dev/null differ diff --git a/12/TP-HN-2008/R2/DG.pas b/12/TP-HN-2008/R2/DG.pas deleted file mode 100755 index 2313685..0000000 --- a/12/TP-HN-2008/R2/DG.pas +++ /dev/null @@ -1,83 +0,0 @@ -type bigboo = [-1..1]; - -var - f : text; - n, i, j : byte; - inp : array[0..100] of PointType; - P, Q : PointType; - P_out, Q_out : boolean; - s : int64 = 0; - -function stri2(A, B, C : PointType) : int64; - begin - stri2 := (C.y - A.y) * (A.x - B.x) - (C.x - A.x) * (A.y - B.y) - end; - -function outpoly(M : PointType) : int64; - begin - outpoly := s; - for i := 0 to n - 1 do - begin - outpoly := outpoly - abs(stri2(M, inp[i], inp[i + 1])) - end - end; - -function sign(x : smallint) : bigboo; - begin - case true of - x > 0 : exit(1); - x = 0 : exit(0); - x < 0 : exit(-1) - end - end; - -function intersect(A, B : PointType) : bigboo; - var b00, b01 : bigboo; - begin - b00 := sign(stri2(P, Q, A)); - b01 := sign(stri2(P, Q, A)); - if b00 = b01 then - if b00 = 0 then exit(0) - else exit(-1); - b00 := sign(stri2(A, B, P)); - b01 := sign(stri2(A, B, Q)); - if b00 = b01 then - if b00 = 0 then exit(0) - else exit(-1); - exit(1) - end; - -function lensqr(A, B : PointType) : int64; - begin - exit() - end; - -procedure out(M, N : PointType); - begin - assign(f, 'DG.OUT'); - rewrite(f); - write(f, trunc(sqrt(sqr(A.x - B.x) + sqr(A.y - B.y)) * 100)); - close(f); - halt - end; - -begin - assign(f, 'DG.INP'); - reset(f); - readln(f, n); - for i := 0 to n - 1 do - readln(f, inp[i].x, inp[i].y); - inp[n] := inp[0]; - readln(f, P.x, P.y, Q.x, Q.y); - close(f); - for i := 1 to n - 2 do - s := s + abs(stri2(inp[0], inp[i], inp[i + 1])); - if outpoly(P) = 0 then - P_out := false; - if outpoly(Q) = 0 then - Q_out := false; - if P_out and Q_out then - for i := 0 to n - 1 do - - out(P, Q) -end. diff --git a/12/TP-HN-2008/R2/HC.pas b/12/TP-HN-2008/R2/HC.pas deleted file mode 100644 index 8e6b182..0000000 --- a/12/TP-HN-2008/R2/HC.pas +++ /dev/null @@ -1,23 +0,0 @@ -var - f : text; - m, n, i, j : byte; - a : array[1..200, 0..200] of smallint; - -function out - -begin - assign(f, 'HC.INP'); - reset(f); - readln(f, m, n); - for i := 1 to m do - begin - a[i, 0] := 0; - for j := 1 to n do - read(f, a[i, j]) - end; - close(f); - assign(f, 'HC.OUT'); - rewrite(f); - writeln(f, out(a)); - close(f) -end; diff --git a/12/TP-HN-2008/R2/R2.doc b/12/TP-HN-2008/R2/R2.doc deleted file mode 100755 index c804058..0000000 Binary files a/12/TP-HN-2008/R2/R2.doc and /dev/null differ diff --git a/12/TP-HN-2008/R2/README.md b/12/TP-HN-2008/R2/README.md new file mode 100644 index 0000000..00ccc3e --- /dev/null +++ b/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/12/TP-HN-2008/R2/TBC.PAS b/12/TP-HN-2008/R2/TBC.PAS deleted file mode 100755 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. diff --git a/12/TP-HN-2008/R2/dg.c b/12/TP-HN-2008/R2/dg.c new file mode 100644 index 0000000..e2422df --- /dev/null +++ b/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/12/TP-HN-2008/R2/hc.cpp b/12/TP-HN-2008/R2/hc.cpp new file mode 100644 index 0000000..1ea6ee3 --- /dev/null +++ b/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/12/TP-HN-2008/R2/tbc.pas b/12/TP-HN-2008/R2/tbc.pas new file mode 100755 index 0000000..1a26a91 --- /dev/null +++ b/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