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 ++++++++++++ 3 files changed, 201 insertions(+) create mode 100644 others/coastline/README.md create mode 100644 others/coastline/dig.c create mode 100644 others/coastline/grid.c (limited to 'others/coastline') 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; +} -- cgit 1.4.1