From 94f49ef11037832a173d268ca932fe34cf78b472 Mon Sep 17 00:00:00 2001 From: Raphael McSinyx Date: Wed, 9 Nov 2016 11:02:27 +0700 Subject: Thêm kì thi thử Duyên Hải MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- others/coastline/README.md | 120 +++++++++++++++++++++ others/coastline/dig.c | 49 +++++++++ others/coastline/grid.c | 32 ++++++ "others/l\341\272\255p-l\341\273\213ch/ctmt.pas" | 86 --------------- "others/l\341\272\255p-l\341\273\213ch/llgc2m.pas" | 44 -------- .../l\341\272\255p-l\341\273\213ch.pdf" | Bin 52261 -> 0 bytes .../l\341\272\255p-l\341\273\213ch/xepviec.pas" | 53 --------- others/mkcal/ctmt.pas | 86 +++++++++++++++ others/mkcal/llgc2m.pas | 44 ++++++++ "others/mkcal/l\341\272\255p-l\341\273\213ch.pdf" | Bin 0 -> 52261 bytes others/mkcal/xepviec.pas | 53 +++++++++ 11 files changed, 384 insertions(+), 183 deletions(-) create mode 100644 others/coastline/README.md create mode 100644 others/coastline/dig.c create mode 100644 others/coastline/grid.c delete mode 100755 "others/l\341\272\255p-l\341\273\213ch/ctmt.pas" delete mode 100755 "others/l\341\272\255p-l\341\273\213ch/llgc2m.pas" delete mode 100755 "others/l\341\272\255p-l\341\273\213ch/l\341\272\255p-l\341\273\213ch.pdf" delete mode 100755 "others/l\341\272\255p-l\341\273\213ch/xepviec.pas" create mode 100755 others/mkcal/ctmt.pas create mode 100755 others/mkcal/llgc2m.pas create mode 100755 "others/mkcal/l\341\272\255p-l\341\273\213ch.pdf" create mode 100755 others/mkcal/xepviec.pas diff --git a/others/coastline/README.md b/others/coastline/README.md new file mode 100644 index 0000000..5582125 --- /dev/null +++ b/others/coastline/README.md @@ -0,0 +1,120 @@ +# KÌ THI THỬ DUYÊN HẢI + +Bộ môn TIN HỌC + +TRƯỜNG THPT CHUYÊN KHTN + +## BIGNUM + +Trên đường đến Núi Cốc tham gia thi Duyên Hải, Ming nhặt được một dãy số, vốn +là người thích số 11, Ming quyết định sắp xếp lại các chữ số để tạo thành một +số chia hết cho 11. + +Hãy xác định số lớn nhất mà Ming có thể tạo ra? + +### INPUT + +Dòng đầu ghi số N ≤ 1000, là số các chữ số trong dãy số của Ming. Dòng sau ghi +N chữ số. + +### OUTPUT + +In ra số lớn nhất Ming có thể tạo ra, hoặc -1 nếu không thể sắp xếp. + +### GIỚI HẠN + +50% số test có N ≤ 20. + +| Sample Input | Sample Output | +| -------------- | ------------- | +| 9
112233456 | 645231312 | +| 2
12 | -1 | + +## GRID + +Cho một bảng, mỗi ô chỉ chứa một trong hai loại ký tự: dấu chấm `.` hoặc dấu +sao `*`. + +Hãy thay thế một số lượng tối thiểu (có thể = 0) ký tự `.` bằng ký tự `*`, sao +cho tất cả các ký tự `*` tạo thành một hình chữ nhật. + +Bên trong hình chữ nhật chỉ có `*` và không có ký tự `.`. + +### INPUT + +Dòng đầu tiên ghi hai số nguyên H và W - số hàng và số cột của bảng. H dòng +tiếp theo, mỗi dòng chứa W kí tự `*` hoặc `.`. Đảm bảo có ít nhất một ký tự +`*`. Các ký tự viết liền nhau, không có dấu cách ở giữa. + +### OUTPUT + +In ra bảng đã thay đổi. Giữa các ký tự không có khoảng trống. + +### GIỚI HẠN + +2 < W, H < 50 + +| Sample Input | Sample Output | +| -------------------------------- | ----------------------- | +| `2 3`
`*..`
`.*.` | `**.`
`**.` | +| `3 3`
`*.*`
`.*.`
`...` | `***`
`***`
`...` | + +## DIGITSUM + +Xét các số nguyên dương liên tiếp: a, a + 1, a + 2, a + 3, ..., b. Số đầu tiên +là a và số cuối cùng là b. Chọn k số liên tiếp từ các số này và tìm ra tổng các +chữ số của chúng. Hãy tìm tổng lớn nhất có thể được? + +Ví dụ: a = 11, b = 48, k = 7. + +Ta có: trong chuỗi các số nguyên {11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, +22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35 36; 37, 38, 39, 40, 41, +42, 43, 44, 45, 46, 47, 48} sẽ có các bộ với 7 số sau (11, 12, 13, 14,15, 16, +17), (12, 13, 14, 15, 16, 17, 18), (13, 14, 15, 16, 17, 18, 19), ..., (42, 43, +44, 45, 46, 47, 48). + +Bộ đầu tiên sẽ nhận được 1 + 1 + 1 + 2 + 1 + 3 + 1 + 4 + 1 + 5 + 1 + 6 + 1 + 7 += 35, bộ thứ 2 được 42, rồi 49, 47, 45, 43, 41, 39, 37, 35, 42, 49, 56, 54, 52, +50, 48, 46, 44, 42, 49, 56, 63, 61, 59, 57, 55, 53, 51, 49, 56 và cuối cùng là +63. Như vậy tổng lớn nhất là 63, được lấy từ 2 bộ bảy (33, 34, 35, 36,37, 38, +39) và (42, 43, 44, 45, 46, 47, 48). Số cần tìm trong trường hợp này là 63. + +Viết chương trình, đọc a, b và k rồi tính ra kết quả. + +### INPUT + +1 dòng duy nhất ghi các số nguyên dương a, b và k, cách nhau một dấu cách. + +### OUTPUT + +In ra giá trị lớn nhất có thể được. + +### GIỚI HẠN + +* 1 ≤ a < b ≤ 50 000 000. +* 2 ≤ k ≤ 10 000 +* k ≤ b - a + 1. +* Trong 30% test : k × (b-a) ≤ 1 000 000. +* Trong 70% các test : b ≤ 5 000 000. + +| Sample Input | Sample Output | +| ------------ | ------------- | +| 11 48 7 | 63 | + +## DIG + +Cho một số nguyên dương N. Hãy viết chương trình tìm số có k chữ số nhỏ nhất (0 +< k < 30), trong đó mỗi chữ số (0-9) xuất hiện ít nhất một lần và không có chữ +số nào của N. + +### INPUT + +Gồm 2 số nguyên k và N, cách nhau một dấu cách. + +### OUTPUT + +In ra đáp số của đề bài, nếu không có in ra số "0". + +| Sample Input | Sample Output | +| ------------ | ------------- | +| 4 201345 | 6789 | diff --git a/others/coastline/dig.c b/others/coastline/dig.c new file mode 100644 index 0000000..8770a6b --- /dev/null +++ b/others/coastline/dig.c @@ -0,0 +1,49 @@ +#include +#include + +int main() +{ + char k, n[21], digits[10] = {}, i, avail = 0, j; + + scanf("%hhd %s", &k, n); + + for (i = 0; i < strlen(n); i++) + digits[n[i] - 48] = 1; + + for (i = 0; i < 10; i++) + if (!digits[i]) + avail++; + + if (avail == 1 && !digits[0] || !avail || avail > k) { + putchar(48); + } else { + if (!digits[0]) + for (i = 1; i < 10; i++) + if (!digits[i]) { + putchar(i + 48); + digits[i] = 1; + avail--; + k--; + break; + } + + for (i = 0; i < 10 && k; i++) + if (!digits[i]) { + for (j = 0; j <= k - avail; j++) + putchar(i + 48); + k = avail - 1; + digits[i] = 1; + break; + } + + for (i = 0; i < 10 && k; i++) + if (!digits[i]) { + putchar(i + 48); + k--; + } + } + + putchar(10); + + return 0; +} diff --git a/others/coastline/grid.c b/others/coastline/grid.c new file mode 100644 index 0000000..b468190 --- /dev/null +++ b/others/coastline/grid.c @@ -0,0 +1,32 @@ +#include + +int main() +{ + char w, h, i, j, t = -1, r = -1, b = -1, l = -1; + + scanf("%hhd %hhd\n", &h, &w); + + for (i = 0; i < h; i++) { + for (j = 0; j < w; j++) + if (getchar() == 42) { + if (t < 0 && l < 0) { + t = i; + l = j; + } + b = (b < i) ? i : b; + r = (r < j) ? j : r; + } + getchar(); + } + + for (i = 0; i < h; i++) { + for (j = 0; j < w; j++) + if (i >= t && i <= b && j >= l && j <= r) + putchar(42); + else + putchar(46); + putchar(10); + } + + return 0; +} diff --git "a/others/l\341\272\255p-l\341\273\213ch/ctmt.pas" "b/others/l\341\272\255p-l\341\273\213ch/ctmt.pas" deleted file mode 100755 index bdd30f0..0000000 --- "a/others/l\341\272\255p-l\341\273\213ch/ctmt.pas" +++ /dev/null @@ -1,86 +0,0 @@ -const - inp = 'ctmt.inp'; - out = 'ctmt.out'; -type - int200 = 1..200; - intday = 0..8640000; -var - f : text; - n, i, j, ln2, ln3 : int200; - a, b : array[1..200] of intday; - p, q, r, s , max0, max1 : intday; - ln0, ln1 : 0..1; -procedure swab(i0, j0 : int200); - var tmp : intday; - begin - tmp := a[i0]; - a[i0] := a[j0]; - a[j0] := tmp; - tmp := b[i0]; - b[i0] := b[j0]; - b[j0] := tmp - end; -procedure del(m : int200); - var o : int200; - begin - dec(n); - for o := m to n do - begin - a[o] := a[o + 1]; - b[o] := b[o + 1] - end - end; -begin - assign(f, inp); - reset(f); - readln(f, n); - for i := 1 to n do - readln(f, a[i], b[i]); - readln(f, p, q); - readln(f, r, s); - close(f); - for i := 1 to n - 1 do - for j := i + 1 to n do - if a[i] > a[j] then swab(i, j); - i := 1; - while i < n do - begin - j := i + 1; - while j <= n do - begin - if (a[j] <= b[i]) and (b[i] <= b[j]) then - begin - b[i] := b[j]; - del(j) - end - else inc(j) - end; - inc(i) - end; - ln0 := 0; - ln1 := 0; - max0 := 0; - max1 := 0; - for i := 1 to n do - begin - if (a[i] <= p) and (q <= b[i]) then ln0 := 1; - if (i < n) and (b[i] < r) and (s < a[i + 1]) then ln1 := 1; - if b[i] - a[i] >= max0 then - begin - ln2 := i; - max0 := b[i] - a[i] - end; - if (i < n) and (a[i + 1] - b[i] > max1) then - begin - ln3 := i; - max1 := a[i + i] - b[i] - end - end; - assign(f, out); - rewrite(f); - writeln(f, ln0); - writeln(f, ln1); - writeln(f, a[ln2], ' ', b[ln2]); - writeln(f, b[ln3] + 1, ' ', a[ln3 + 1] - 1); - close(f) -end. diff --git "a/others/l\341\272\255p-l\341\273\213ch/llgc2m.pas" "b/others/l\341\272\255p-l\341\273\213ch/llgc2m.pas" deleted file mode 100755 index 3fc8ef2..0000000 --- "a/others/l\341\272\255p-l\341\273\213ch/llgc2m.pas" +++ /dev/null @@ -1,44 +0,0 @@ -uses math; -var - f : text; - n, i : byte; - a, b, c, c0 : array[1..255] of byte; - d : array[1..255] of boolean; - out : cardinal; -procedure libgc2m(m : byte; o0, o1 : cardinal); - var j : byte; - begin - if m > 0 then begin - for j := 1 to n do - if d[j] then begin - d[j] := false; - c[n - m + 1] := j; - libgc2m(m - 1, o0 + a[j], max(o0 + a[j], o1) + b[j]); - d[j] := true; - end - end else - if (o1 < out) or (out = 0) then begin - out := o1; - for j := 1 to n do c0[j] := c[j] - end - end; -begin - assign(f, 'llgc2m.inp'); - reset(f); - readln(f, n); - for i := 1 to n do read(f, a[i], b[i]); - close(f); - for i := 1 to n do d[i] := true; - out := 0; - for i := 1 to n do begin - d[i] := false; - c[1] := i; - libgc2m(n - 1, a[i], a[i] + b[i]); - d[i] := true - end; - assign(f, 'llgc2m.out'); - rewrite(f); - writeln(f, out); - for i := 1 to n do write(f, c0[i], ' '); - close(f) -end. diff --git "a/others/l\341\272\255p-l\341\273\213ch/l\341\272\255p-l\341\273\213ch.pdf" "b/others/l\341\272\255p-l\341\273\213ch/l\341\272\255p-l\341\273\213ch.pdf" deleted file mode 100755 index 48ad249..0000000 Binary files "a/others/l\341\272\255p-l\341\273\213ch/l\341\272\255p-l\341\273\213ch.pdf" and /dev/null differ diff --git "a/others/l\341\272\255p-l\341\273\213ch/xepviec.pas" "b/others/l\341\272\255p-l\341\273\213ch/xepviec.pas" deleted file mode 100755 index cfa39d6..0000000 --- "a/others/l\341\272\255p-l\341\273\213ch/xepviec.pas" +++ /dev/null @@ -1,53 +0,0 @@ -const - inp = 'xepviec.inp'; - out = 'xepviec.out'; -type int200 = 0..200; -var - f : text; - n, i, j, k, l, tmp : int200; - a : array[0..200, 0..200] of int200; -function next(m : int200) : boolean; - var i0, j0 : int200; - begin - for i0 := 1 to a[0, 0] do - for j0 := 2 to a[i0, 0] do - if m = a[i0, j0] then exit(false); - next := true; - end; -begin - assign(f, inp); - reset(f); - readln(f, n); - i := 0; - repeat - inc(i); - j := 0; - repeat - inc(j); - read(f, a[i, j]) - until eoln(f); - a[i, 0] := j - until eof(f); - close(f); - a[0, 0] := i - 1; - for i := 1 to n do - for j := 1 to a[0, 0] do - if (a[j, 0] > 0) and next(a[j, 1]) then - begin - tmp := a[j, 1]; - a[0, i] := tmp; - for k := 1 to a[0, 0] do - if a[k, 1] = tmp then - begin - dec(a[k, 0]); - for l := 1 to a[k, 0] do - a[k, l] := a[k, l + 1] - end; - break - end; - assign(f, out); - rewrite(f); - for i := 1 to n do - write(f, a[0, i], ' '); - close(f) -end. diff --git a/others/mkcal/ctmt.pas b/others/mkcal/ctmt.pas new file mode 100755 index 0000000..bdd30f0 --- /dev/null +++ b/others/mkcal/ctmt.pas @@ -0,0 +1,86 @@ +const + inp = 'ctmt.inp'; + out = 'ctmt.out'; +type + int200 = 1..200; + intday = 0..8640000; +var + f : text; + n, i, j, ln2, ln3 : int200; + a, b : array[1..200] of intday; + p, q, r, s , max0, max1 : intday; + ln0, ln1 : 0..1; +procedure swab(i0, j0 : int200); + var tmp : intday; + begin + tmp := a[i0]; + a[i0] := a[j0]; + a[j0] := tmp; + tmp := b[i0]; + b[i0] := b[j0]; + b[j0] := tmp + end; +procedure del(m : int200); + var o : int200; + begin + dec(n); + for o := m to n do + begin + a[o] := a[o + 1]; + b[o] := b[o + 1] + end + end; +begin + assign(f, inp); + reset(f); + readln(f, n); + for i := 1 to n do + readln(f, a[i], b[i]); + readln(f, p, q); + readln(f, r, s); + close(f); + for i := 1 to n - 1 do + for j := i + 1 to n do + if a[i] > a[j] then swab(i, j); + i := 1; + while i < n do + begin + j := i + 1; + while j <= n do + begin + if (a[j] <= b[i]) and (b[i] <= b[j]) then + begin + b[i] := b[j]; + del(j) + end + else inc(j) + end; + inc(i) + end; + ln0 := 0; + ln1 := 0; + max0 := 0; + max1 := 0; + for i := 1 to n do + begin + if (a[i] <= p) and (q <= b[i]) then ln0 := 1; + if (i < n) and (b[i] < r) and (s < a[i + 1]) then ln1 := 1; + if b[i] - a[i] >= max0 then + begin + ln2 := i; + max0 := b[i] - a[i] + end; + if (i < n) and (a[i + 1] - b[i] > max1) then + begin + ln3 := i; + max1 := a[i + i] - b[i] + end + end; + assign(f, out); + rewrite(f); + writeln(f, ln0); + writeln(f, ln1); + writeln(f, a[ln2], ' ', b[ln2]); + writeln(f, b[ln3] + 1, ' ', a[ln3 + 1] - 1); + close(f) +end. diff --git a/others/mkcal/llgc2m.pas b/others/mkcal/llgc2m.pas new file mode 100755 index 0000000..3fc8ef2 --- /dev/null +++ b/others/mkcal/llgc2m.pas @@ -0,0 +1,44 @@ +uses math; +var + f : text; + n, i : byte; + a, b, c, c0 : array[1..255] of byte; + d : array[1..255] of boolean; + out : cardinal; +procedure libgc2m(m : byte; o0, o1 : cardinal); + var j : byte; + begin + if m > 0 then begin + for j := 1 to n do + if d[j] then begin + d[j] := false; + c[n - m + 1] := j; + libgc2m(m - 1, o0 + a[j], max(o0 + a[j], o1) + b[j]); + d[j] := true; + end + end else + if (o1 < out) or (out = 0) then begin + out := o1; + for j := 1 to n do c0[j] := c[j] + end + end; +begin + assign(f, 'llgc2m.inp'); + reset(f); + readln(f, n); + for i := 1 to n do read(f, a[i], b[i]); + close(f); + for i := 1 to n do d[i] := true; + out := 0; + for i := 1 to n do begin + d[i] := false; + c[1] := i; + libgc2m(n - 1, a[i], a[i] + b[i]); + d[i] := true + end; + assign(f, 'llgc2m.out'); + rewrite(f); + writeln(f, out); + for i := 1 to n do write(f, c0[i], ' '); + close(f) +end. diff --git "a/others/mkcal/l\341\272\255p-l\341\273\213ch.pdf" "b/others/mkcal/l\341\272\255p-l\341\273\213ch.pdf" new file mode 100755 index 0000000..48ad249 Binary files /dev/null and "b/others/mkcal/l\341\272\255p-l\341\273\213ch.pdf" differ diff --git a/others/mkcal/xepviec.pas b/others/mkcal/xepviec.pas new file mode 100755 index 0000000..cfa39d6 --- /dev/null +++ b/others/mkcal/xepviec.pas @@ -0,0 +1,53 @@ +const + inp = 'xepviec.inp'; + out = 'xepviec.out'; +type int200 = 0..200; +var + f : text; + n, i, j, k, l, tmp : int200; + a : array[0..200, 0..200] of int200; +function next(m : int200) : boolean; + var i0, j0 : int200; + begin + for i0 := 1 to a[0, 0] do + for j0 := 2 to a[i0, 0] do + if m = a[i0, j0] then exit(false); + next := true; + end; +begin + assign(f, inp); + reset(f); + readln(f, n); + i := 0; + repeat + inc(i); + j := 0; + repeat + inc(j); + read(f, a[i, j]) + until eoln(f); + a[i, 0] := j + until eof(f); + close(f); + a[0, 0] := i - 1; + for i := 1 to n do + for j := 1 to a[0, 0] do + if (a[j, 0] > 0) and next(a[j, 1]) then + begin + tmp := a[j, 1]; + a[0, i] := tmp; + for k := 1 to a[0, 0] do + if a[k, 1] = tmp then + begin + dec(a[k, 0]); + for l := 1 to a[k, 0] do + a[k, l] := a[k, l + 1] + end; + break + end; + assign(f, out); + rewrite(f); + for i := 1 to n do + write(f, a[0, i], ' '); + close(f) +end. -- cgit 1.4.1