diff options
Diffstat (limited to '09')
| -rw-r--r-- | 09/Q-Huế-2014/README.md | 53 | ||||
| -rw-r--r-- | 09/Q-Huế-2014/bai1.pas | 15 | ||||
| -rw-r--r-- | 09/Q-Huế-2014/bai2.pas | 35 | ||||
| -rw-r--r-- | 09/Q-Huế-2014/bai3.pas | 34 | ||||
| -rw-r--r-- | 09/TP-HN-2014/README.md | 159 | ||||
| -rw-r--r-- | 09/TP-HN-2014/cau1.cpp | 51 | ||||
| -rw-r--r-- | 09/TP-HN-2014/cau1.pas | 46 | ||||
| -rw-r--r-- | 09/TP-HN-2014/cau2.cpp | 32 | ||||
| -rw-r--r-- | 09/TP-HN-2014/cau2.pas | 31 | ||||
| -rw-r--r-- | 09/TP-HN-2014/cau3.c | 40 | ||||
| -rw-r--r-- | 09/TP-HN-2014/cau3.pas | 59 | ||||
| -rw-r--r-- | 09/TP-HN-2014/cau4.c | 48 | ||||
| -rw-r--r-- | 09/TP-HN-2014/cau4.pas | 89 |
13 files changed, 0 insertions, 692 deletions
diff --git a/09/Q-Huế-2014/README.md b/09/Q-Huế-2014/README.md deleted file mode 100644 index 2da9e8e..0000000 --- a/09/Q-Huế-2014/README.md +++ /dev/null @@ -1,53 +0,0 @@ -# THI CHỌN HỌC SINH GIỎI CẤP THÀNH PHỐ - -UBND THÀNH PHỐ HUẾ - -PHÒNG GIÁO DỤC VÀ ĐÀO TẠO - -MÔN TIN HỌC - NĂM HỌC: 2013-2014 - -Thời gian: 120 phút (Không kể thời gian giao đề) - -## Bài 1 (3 điểm) - -Hai số tự nhiên `n`, `m` được gọi là nguyên tố tương đương nếu chúng có chung -các ước số nguyên tố. - -Hãy viết chương trình nhập vào hai số `n`, `m` và kiểm -tra chúng có là nguyên tố tương đương với nhau hay không. - -**Ví dụ:** Số 75 và số 15 là nguyên tố tương đương vì chúng có cùng các ước số -nguyên tố là 3 và 5. - -## Bài 2 (3 điểm) - -Cho hệ phương trình bậc nhất hai ẩn: - - ax + by = c - a'x + b'y = c' - -Hãy viết chương trình giải hệ phương trình trên, đồng thời xác định vị trí -tương đối của hai đường thẳng `d: ax + by = c` và `d': a'x + b'y =c'` đã tạo -nên hệ phương trình. - -## Bài 3 (4 điểm) - -Cho hai xâu `X`, `Y` chứa các kí tự số từ 0 đến 9 và không dài quá 250 kí tự. - -Hãy viết chương trình tạo ra xâu `ST` thoả mãn các điều kiện sau: - -* Gồm các kí tự số vừa có mặt ở xâu `X`, vừa có mặt ở xâu `Y` -* Các kí tự số trong xâu `ST` chỉ xuất hiện duy nhất một lần -* Giá trị xâu `ST` nhận được là một số đạt giá trị lớn nhất - -Dữ liệu vào cho bởi file `INPUT.INP` chứa giá trị xâu `X` và xâu `Y`, mỗi xâu -nằm trên một dòng. - -Dữ liệu ra chứa ở file `OUTPUT.OUT` là số lớn nhất nhận được. - -**Ví dụ:** - -| INPUT.INP | OUTPUT.OUT | -| --------- | ---------- | -| 19012304 | 43210 | -| 034012 | | diff --git a/09/Q-Huế-2014/bai1.pas b/09/Q-Huế-2014/bai1.pas deleted file mode 100644 index 7bd0d92..0000000 --- a/09/Q-Huế-2014/bai1.pas +++ /dev/null @@ -1,15 +0,0 @@ -var - n, m, p: qword; - -begin - read(n, m); - - while m <> 0 do - begin - p := n mod m; - n := m; - m := p - end; - - writeln(n <> 1) -end. diff --git a/09/Q-Huế-2014/bai2.pas b/09/Q-Huế-2014/bai2.pas deleted file mode 100644 index 172137d..0000000 --- a/09/Q-Huế-2014/bai2.pas +++ /dev/null @@ -1,35 +0,0 @@ -var - a, b, c, e, p, k, tmp: real; - -function det(a, b, c, d: real): real; - begin - exit(a * d - b * c) - end; - -begin - read(a, b, c, e, p, k); - - tmp := det(a, b, e, p); - - if tmp <> 0 then - begin - writeln('x = ', (det(c, b, k, p) / tmp):0:6); - writeln('y = ', (det(a, c, e, k) / tmp):0:6); - writeln('Hai đường thẳng cắt nhau.') - end - else if c <> k then - begin - writeln('Phương trình vô nghiệm.'); - writeln('Hai đường thẳng song song.') - end - else - begin - if a = 0 then - writeln('y = ', (c / b):0:6) - else if b = 0 then - writeln('x = ', (c / a):0:6) - else - writeln('x = ', (-b / a):0:6, 'y + ', (c / a):0:6); - writeln('Hai đường thẳng trùng nhau.') - end; -end. diff --git a/09/Q-Huế-2014/bai3.pas b/09/Q-Huế-2014/bai3.pas deleted file mode 100644 index 91fc05f..0000000 --- a/09/Q-Huế-2014/bai3.pas +++ /dev/null @@ -1,34 +0,0 @@ -var - x, y: string; - f: text; - a: array[0 .. 9] of shortint; - b: shortint; - c: char; - -begin - assign(f, 'INPUT.INP'); - reset(f); - readln(f, x); - readln(f, y); - close(f); - - fillchar(a, 0, sizeof(a)); - - for c in x do - a[ord(c) - 48] := 1; - - for c in y do - begin - b := ord(c) - 48; - if a[b] = 1 then - a[b] := 2 - end; - - assign(f, 'OUTPUT.OUT'); - rewrite(f); - for b := 9 downto 0 do - if a[b] = 2 then - write(f, b); - writeln(f); - close(f) -end. diff --git a/09/TP-HN-2014/README.md b/09/TP-HN-2014/README.md deleted file mode 100644 index 5d15789..0000000 --- a/09/TP-HN-2014/README.md +++ /dev/null @@ -1,159 +0,0 @@ -# KỲ THI HỌC SINH GIỎI THÀNH PHỐ LỚP 9 NĂM HỌC 2013 - 2014 - -SỞ GIÁO DỤC VÀ ĐÀO TẠO HÀ NỘI - -Môn thi: TIN HỌC - -Ngày thi: 31/03/2014 - -Thời gian làm bài: 150 phút - -## Tổng quan bài thi - -| Câu | Tệp chương trình | Tệp dữ liệu | Tệp kết quả | Điểm | -| :---: | :--------------: | :---------: | :---------: | :---: | -| 1 | CAU1.PAS | CAU1.INP | CAU1.OUT | 6 | -| 2 | CAU2.PAS | CAU2.INP | CAU2.OUT | 6 | -| 3 | CAU3.PAS | CAU3.INP | CAU3.OUT | 4 | -| 4 | CAU4.PAS | CAU4.INP | CAU4.OUT | 4 | - -## Câu 1: Hiệu hai phân số - -Cho bốn số nguyên dương a, b, c, d, mỗi số có giá trị không vượt quá -10<sup>5</sup>. - -### Yêu cầu - -Tìm hai số nguyên x, y để phân số tối giản <sup>x</sup>/<sub>y</sub> và bằng -hiệu của hai phân số <sup>a</sup>/<sub>b</sub> - <sup>c</sup>/<sub>d</sub>, -trong đó y > 0. - -### Dữ liệu - -* Dòng đầu chứ hai số a, b; -* Dòng thứ hai chứa hai số c, d. - -### Kết quả - -Hai số x và y trên cùng một dòng, cách nhau một dấu cách. - -### Ví dụ - -| CAU1.INP | CAU1.OUT | -| ----------- | :------: | -| 1 6<br>5 12 | -1 4 | - -#### Giải thích - -<sup>1</sup>/<sub>6</sub> - <sup>5</sup>/<sub>12</sub> = -<sup>-1</sup>/<sub>4</sub> - -## Câu 2: Đua Robot - -Trong cuộc đua tốc độ có n Robot tham gia được đánh số từ 1 đến n. Đường đua -có độ dài d (mét). Robot thứ i (1 ≤ i ≤ n) có vận tốc đua không đổi là -v<sub>i</sub> (mét/phút). Các Robot xuất phát theo thứ tự từ 1 đến n và cách -nhau 1 phút. Robot i gọi là vượt Robot j (1 ≤ j ≤ n) nếu i xuất phát sau j và -về đích trước j. - -### Yêu cầu - -Xác định số lần vượt nhau của tất cả các Robot trong cuộc đua. - -### Dữ liệu - -* Dòng đầu chứa hai số nguyên dương n và d, n ≤ 10<sup>3</sup>, - d ≤ 10<sup>9</sup>; -* Dòng tiếp theo chứa n số nguyên dương v<sub>i</sub>, 1 ≤ i ≤ n, mỗi số không - vượt quá 1000. - -### Kết quả - -Số lần vượt nhau của tất cả các Robot trong cuộc đua. - -### Ví dụ - -| CAU2.INP | CAU2.OUT | -| ----------------- | :------: | -| 5 10<br>1 2 4 3 8 | 7 | - -#### Giải thích - -* Robot 2 vượt Robot 1; -* Robot 3 vượt Robot 1, 2; -* Robot 4 vượt Robot 1; -* Robot 5 vượt Robot 1, 2, 4. - -Tổng số lần vượt là 7. - -## Câu 3: Tìm kiếm trong xâu - -Cho xâu s có độ dài tối đa 250 kí tự gồm chữ cái in hoa, in thường và chữ số. - -### Yêu cầu - -Đếm xem trong xâu s có bao nhiêu kí tự khác nhau và tìm độ dài đoạn kí tự liên -tiếp dài nhất trong xâu s tạo thành xâu x đối xứng. Xâu kí tự x được gọi là đối -xứng nếu đọc từ trái sang phải hoặc ngược lại ta đều thu được xâu như nhau. - -### Dữ liệu - -Một dòng duy nhất chứa xâu s. - -### Kết quả - -* Dòng thứ nhất ghi số lượng kí tự khác nhau trong s; -* Dòng thứ hai ghi độ dài xâu x tìm được. - -### Ví dụ - -| CAU3.INP | CAU3.OUT | -| :---------------: | :------: | -| AbcabA12321ABCcba | 9<br>7 | - -#### Giải thích - -Các kí tự khác nhau gồm: `1`, `2`, `3`, `A`, `B`, `C`, `a`, `b`, `c`. - -Xâu X tìm được là: `A12321A`. - -## Câu 4: Trồng cây - -Dọc theo một tuyến phố thẳng có n vị trí kế tiếp nhau để trồng cây đánh số từ 1 -đến n. Hiện tại chỉ có vị trí k (1 ≤ k ≤ n) đã trồng một cây có độ cao -a<sub>k</sub>, còn các vị trí khác để trống. Theo dự kiến, người ta sẽ trồng -cây có độ cao a<sub>i</sub> tại vị trí thứ i (1 ≤ i ≤ n, i ≠ k). Tuy nhiên, để -tăng vẻ đẹp cho hàng cây, người ta muốn tìm một phương án sắp xếp các cây cần -trồng vào các vị trí thích hợp (trừ vị trí k) sao cho tổng tất cả các độ chênh -lệch của hai cây trồng liền nhau là nhỏ nhất. Độ chênh lệch của hai cây là giá -trị tuyệt đối hiệu độ cao hai cây. - -### Yêu cầu - -Tìm giá trị nhỏ nhất t của tổng tất cả các độ chênh lệch của hai cây trồng liền -nhau. - -### Dữ liệu - -* Dòng đầu chứa hai số nguyên dương n và d, n ≤ 10<sup>3</sup>, 1 ≤ k ≤ n; -* Dòng sau chứa n số nguyên dương a<sub>i</sub>, 1 ≤ i ≤ n, là độ cao của cây - thứ i theo dự kiến. Mỗi số đều không vượt quá 10<sup>6</sup>. - -### Kết quả - -Số t tìm được. - -### Ví dụ - -| CAU4.INP | CAU4.OUT | -| ---------------- | :------: | -| 5 2<br>7 3 4 2 6 | 5 | - -#### Giải thích - -* Vị trí 1 trồng cây có độ cao 2; -* Vị trí 3 trồng cây có độ cao 4; -* Vị trí 4 trồng cây có độ cao 6; -* Vị trí 5 trồng cây có độ cao 7. - -Tổng độ chênh lệch nhỏ nhất là 5. diff --git a/09/TP-HN-2014/cau1.cpp b/09/TP-HN-2014/cau1.cpp deleted file mode 100644 index 274cef6..0000000 --- a/09/TP-HN-2014/cau1.cpp +++ /dev/null @@ -1,51 +0,0 @@ -#include <iostream> -#include <fstream> - -using namespace std; - -long -gcd(long x, long y) -{ - long z; - while (y) - { - z = x; - x = y; - y = z % x; - } - - return x; -} - -int -main() -{ - ifstream infile; - long a, b, c, d; - infile.open("CAU1.INP"); - infile >> a >> b >> c >> d; - infile.close(); - - long y = b * d / gcd(b, d); - long x = a * y / b - c * y / d; - if (!x) - y = 1; - else - { - a = gcd(x, y); - x /= a; - y /= a; - if (y < 0) - { - x *= -1; - y *= -1; - } - } - - ofstream outfile; - outfile.open("CAU1.OUT"); - outfile << x << ' ' << y << endl; - outfile.close(); - - return 0; -} diff --git a/09/TP-HN-2014/cau1.pas b/09/TP-HN-2014/cau1.pas deleted file mode 100644 index 466d4c4..0000000 --- a/09/TP-HN-2014/cau1.pas +++ /dev/null @@ -1,46 +0,0 @@ -var - f: text; - a, b, g: int64; - c, d: smallint; - - -function gcd(x, y: int64): int64; - var z: int64; - - begin - while y <> 0 do - begin - z := y; - y := x mod y; - x := z - end; - - gcd := a - end; - - -begin - assign(f, 'CAU1.INP'); - reset(f); - read(f, a, b, c, d); - close(f); - - a := a * d - c * b; - b := b * d; - - g := gcd(a, b); - - a := a div g; - b := b div g; - - if b < 0 then - begin - a := -a; - b := -b - end; - - assign(f, 'CAU1.OUT'); - rewrite(f); - writeln(f, a, ' ', b); - close(f) -end. diff --git a/09/TP-HN-2014/cau2.cpp b/09/TP-HN-2014/cau2.cpp deleted file mode 100644 index 8c87168..0000000 --- a/09/TP-HN-2014/cau2.cpp +++ /dev/null @@ -1,32 +0,0 @@ -#include <stdlib.h> -#include <iostream> -#include <fstream> - -using namespace std; - -int -main() -{ - ifstream infile; - infile.open("CAU2.INP"); - short n, i, j; - long d, count = 0; - infile >> n >> d; - short* v = (short*) malloc(n * sizeof(short)); - for (i = 0; i < n; i++) - { - infile >> v[i]; - for (j = 0; j < i; j++) - if (d * (v[i] - v[j]) > v[i] * v[j] * (i - j)) - count++; - } - infile.close(); - free(v); - - ofstream outfile; - outfile.open("CAU2.OUT"); - outfile << count << endl; - outfile.close(); - - return 0; -} diff --git a/09/TP-HN-2014/cau2.pas b/09/TP-HN-2014/cau2.pas deleted file mode 100644 index aed61ed..0000000 --- a/09/TP-HN-2014/cau2.pas +++ /dev/null @@ -1,31 +0,0 @@ -var - f: text; - n, i, j: smallint; - d: longint; - v: array of smallint; - t: array of real; - -begin - assign(f, 'CAU2.INP'); - reset(f); - readln(f, n, d); - setlength(v, n); - for i := 0 to n - 1 do - read(f, v[i]); - close(f); - - setlength(t, n); - for i := 0 to n - 1 do - t[i] := i + d / v[i]; - - d := 0; - for i := 1 to n - 1 do - for j := 0 to i - 1 do - if t[i] < t[j] then - inc(d); - - assign(f, 'CAU2.OUT'); - rewrite(f); - writeln(f, d); - close(f) -end. diff --git a/09/TP-HN-2014/cau3.c b/09/TP-HN-2014/cau3.c deleted file mode 100644 index cbb2ce4..0000000 --- a/09/TP-HN-2014/cau3.c +++ /dev/null @@ -1,40 +0,0 @@ -#include <stdio.h> -#include <string.h> - -char ispalin(char *s, unsigned char len) -{ - unsigned char i, j; - for (i = 0; i < (len + 1) / 2; i++) - if (s[i] != s[len - i - 1]) - return 0; - return 1; -} - -unsigned char maxpalin(char s[256]) -{ - unsigned char i, j, k, len = strlen(s); - for (i = len - 1; i; i--) - for (j = 0; j + i <= len; j++) - if (ispalin(s + j, i)) - return i; -} - -int main() -{ - FILE *f = fopen("CAU3.INP", "r"); - char s[256]; - fscanf(f, "%s\n", s); - fclose(f); - - unsigned char i, count[128] = {}; - for (i = 0; i < strlen(s); count[s[i++]]++); - for (i = 1; i < 128; i++) - if (count[i]) - (*count)++; - - f = fopen("CAU3.OUT", "w"); - fprintf(f, "%hhd\n%hhd\n", *count, maxpalin(s)); - fclose(f); - - return 0; -} diff --git a/09/TP-HN-2014/cau3.pas b/09/TP-HN-2014/cau3.pas deleted file mode 100644 index 1785da9..0000000 --- a/09/TP-HN-2014/cau3.pas +++ /dev/null @@ -1,59 +0,0 @@ -var - f: text; - s: string; - c: char; - a: array of byte; - i, j: byte; - tmp: byte = 0; - - -function palin( - s: string; - l, h: byte -): boolean; - - begin - while l <= h do - begin - if s[l] <> s[h] then - exit(false); - - inc(l); - dec(h); - end; - - palin := true - end; - - - -begin - assign(f, 'CAU3.INP'); - reset(f); - readln(f, s); - close(f); - - setlength(a, 256); - for i := 0 to 255 do - a[i] := 0; - - for c in s do - inc(a[ord(c)]); - - for i in a do - if i > 0 then - inc(tmp); - - assign(f, 'CAU3.OUT'); - rewrite(f); - writeln(f, tmp); - - tmp := 0; - for i := 1 to length(s) - 1 do - for j := i + tmp to length(s) do - if palin(s, i, j) then - tmp := j - i + 1; - - writeln(f, tmp); - close(f) -end. diff --git a/09/TP-HN-2014/cau4.c b/09/TP-HN-2014/cau4.c deleted file mode 100644 index 49e3df6..0000000 --- a/09/TP-HN-2014/cau4.c +++ /dev/null @@ -1,48 +0,0 @@ -#include <stdlib.h> -#include <stdio.h> - -int cmp(const void *x, const void *y) -{ - return *(int *) x - *(int *) y; -} - -int main() -{ - FILE *f = fopen("CAU4.INP", "r"); - int n, d, k; - fscanf(f, "%d %d", &n, &d); - int *a = (int *) malloc(n * sizeof(int)); - for (k = 0; k < n; k++) - fscanf(f, "%d", a + k); - k = a[--d]; - fclose(f); - - qsort(a, n, sizeof(int), cmp); - int t = 0; - for (int i = 1; i < n; i++) - t += abs(a[i] - a[i - 1]); - int idx = (int *) bsearch(&k, a, n, sizeof(int), cmp) - a; - if ((idx - d) * (idx - n + d + 1)) { - int t0, t1; - if (idx < d) { - t0 = (t - abs(a[n - d + idx] - a[n - d + idx - 1]) - + abs(a[n - d + idx] - *a)); - d = n - d - 1; - t1 = (t - abs(a[idx - d] - a[idx - d - 1]) - + abs(a[n - 1] - a[idx - d - 1])); - } else { - t0 = (t - abs(a[idx - d] - a[idx - d - 1]) - + abs(a[n - 1] - a[idx - d - 1])); - d = n - d - 1; - t1 = (t - abs(a[n - d + idx] - a[n - d + idx - 1]) - + abs(a[n - d + idx] - *a)); - } - t = (t0 < t1) ? t0 : t1; - } - - f = fopen("CAU4.OUT", "w"); - fprintf(f, "%d\n", t); - fclose(f); - - return 0; -} diff --git a/09/TP-HN-2014/cau4.pas b/09/TP-HN-2014/cau4.pas deleted file mode 100644 index 1e79c04..0000000 --- a/09/TP-HN-2014/cau4.pas +++ /dev/null @@ -1,89 +0,0 @@ -var - f: text; - n, k, i: smallint; - a, c: array of longint; - b: array of boolean; - d: longint = 0; - - -procedure foo( - idx: smallint; - delta: longint -); - - var - i: smallint; - next: byte = 1; - - begin - if (idx = k + 1) and (k > 0) then - delta := delta + abs(c[k] - c[k - 1]); - - if delta >= d then - exit; - - if idx + 1 = k then - inc(next); - - if idx = n then - begin - d := delta; - exit - end; - - for i := 0 to n - 2 do - if b[i] then - begin - b[i] := false; - c[idx] := a[i]; - - if idx > 0 then - foo(idx + next, delta + abs(c[idx] - c[idx - 1])) - else - foo(idx + next, 0); - - b[i] := true; - c[idx] := 0 - end - end; - - -begin - assign(f, 'CAU4.INP'); - reset(f); - readln(f, n, k); - setlength(a, n); - for i := 0 to n - 1 do - read(f, a[i]); - close(f); - - setlength(c, n); - dec(k); - c[k] := a[k]; - - for i := 0 to k - 1 do - c[i] := 0; - for i := k + 1 to n - 1 do - c[i] := 0; - - for i := 1 to n - 1 do - d := d + abs(a[i] - a[i - 1]); - - for i := k to n - 2 do - a[i] := a[i + 1]; - setlength(a, n - 1); - - setlength(b, n - 1); - for i := 0 to n - 2 do - b[i] := true; - - if k = 0 then - foo(1, 0) - else - foo(0, 0); - - assign(f, 'CAU4.OUT'); - rewrite(f); - writeln(f, d); - close(f) -end. |