diff options
| -rwxr-xr-x | 12/TP-HN-2008/R2/DG | bin | 133348 -> 0 bytes | |||
| -rwxr-xr-x | 12/TP-HN-2008/R2/DG.INP | 6 | ||||
| -rwxr-xr-x | 12/TP-HN-2008/R2/DG.OUT | 1 | ||||
| -rwxr-xr-x | 12/TP-HN-2008/R2/DG.o | bin | 9392 -> 0 bytes | |||
| -rwxr-xr-x | 12/TP-HN-2008/R2/DG.pas | 83 | ||||
| -rw-r--r-- | 12/TP-HN-2008/R2/HC.pas | 23 | ||||
| -rwxr-xr-x | 12/TP-HN-2008/R2/R2.doc | bin | 64512 -> 0 bytes | |||
| -rw-r--r-- | 12/TP-HN-2008/R2/README.md | 115 | ||||
| -rw-r--r-- | 12/TP-HN-2008/R2/dg.c | 102 | ||||
| -rw-r--r-- | 12/TP-HN-2008/R2/hc.cpp | 73 | ||||
| -rwxr-xr-x | 12/TP-HN-2008/R2/tbc.pas (renamed from 12/TP-HN-2008/R2/TBC.PAS) | 0 |
11 files changed, 290 insertions, 113 deletions
diff --git a/12/TP-HN-2008/R2/DG b/12/TP-HN-2008/R2/DG Binary files differdeleted file mode 100755 index ad902a1..0000000 --- a/12/TP-HN-2008/R2/DG +++ /dev/null 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 Binary files differdeleted file mode 100755 index cf2e3e1..0000000 --- a/12/TP-HN-2008/R2/DG.o +++ /dev/null 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 Binary files differdeleted file mode 100755 index c804058..0000000 --- a/12/TP-HN-2008/R2/R2.doc +++ /dev/null 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 a<sub>1</sub>, a<sub>2</sub>, …, a<sub>n</sub>. Số +a<sub>p</sub> (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 a<sub>p</sub> += (a<sub>i</sub> + a<sub>j</sub> + a<sub>k</sub>) / 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 a<sub>i</sub> + (|a<sub>i</sub>| < 10<sup>8</sup>). + +### 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<br>4<br>3<br>6<br>3<br>5 | 2 | +| 3<br>1<br>2<br>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à a<sub>i, j</sub>. + +### 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à a<sub>i, j</sub> ≤ 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<br>2 1 9 1<br>5 0 3 4<br>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á 10<sup>5</sup>. 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à (x<sub>1</sub>, +y<sub>1</sub>) và (x<sub>2</sub>, y<sub>2</sub>) trong đó x<sub>1</sub>, +y<sub>1</sub>, x<sub>2</sub>, y<sub>2</sub> là các số nguyên và có giá trị +tuyệt đối không vượt quá 10<sup>6</sup>. 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 x<sub>1</sub>, y<sub>1</sub>, x<sub>2</sub>, + y<sub>2</sub>. + +### 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<br>0 1<br>1 0<br>0 -1<br>-1 0<br>-2 0 0 0 | 100 | 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 <math.h> +#include <stdio.h> + +#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 <iostream> +#include <fstream> +#include <functional> +#include <queue> +#include <vector> + +#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<long long, vector<long long>, greater<long long>> 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 index 1a26a91..1a26a91 100755 --- a/12/TP-HN-2008/R2/TBC.PAS +++ b/12/TP-HN-2008/R2/tbc.pas |