From c67182c04491f2cf8b67e78b68aebf32aea25470 Mon Sep 17 00:00:00 2001 From: Raphael McSinyx Date: Sun, 1 Jan 2017 20:42:05 +0700 Subject: Update others/{mHoang,mkcal} --- others/mHoang/README.md | 75 +++++++++++ others/mHoang/decor.c | 13 ++ others/mHoang/decor.py | 15 +++ others/mHoang/pfactor.c | 21 +++ others/mHoang/triangle.c | 19 +++ others/mHoang20150916/README.md | 42 ------ others/mHoang20150916/pfactor.c | 21 --- others/mHoang20150916/triangle.c | 19 --- others/mkcal/README.md | 148 ++++++++++++++++++++++ others/mkcal/llgcmm.pas | 97 ++++++++++++++ "others/mkcal/l\341\272\255p-l\341\273\213ch.pdf" | Bin 52261 -> 0 bytes 11 files changed, 388 insertions(+), 82 deletions(-) create mode 100644 others/mHoang/README.md create mode 100644 others/mHoang/decor.c create mode 100755 others/mHoang/decor.py create mode 100644 others/mHoang/pfactor.c create mode 100644 others/mHoang/triangle.c delete mode 100644 others/mHoang20150916/README.md delete mode 100644 others/mHoang20150916/pfactor.c delete mode 100644 others/mHoang20150916/triangle.c create mode 100644 others/mkcal/README.md create mode 100644 others/mkcal/llgcmm.pas delete mode 100755 "others/mkcal/l\341\272\255p-l\341\273\213ch.pdf" diff --git a/others/mHoang/README.md b/others/mHoang/README.md new file mode 100644 index 0000000..05aa6bc --- /dev/null +++ b/others/mHoang/README.md @@ -0,0 +1,75 @@ +# mHoang + +## THỪA SỐ NGUYÊN TỐ (PFACTOR.*) + +Cho số nguyên dương n, tìm số nguyên tố p lớn nhất là ước số của n. + +### Dữ liệu + +Vào từ thiết bị nhập chuẩn số nguyên n, (2 ≤ n ≤ 1014). + +### Kết quả + +Ghi ra thiết bị xuất chuẩn một số nguyên duy nhất là ước số nguyên tố lớn nhất +của n. + +### Ví dụ + +| Sample Input | Sample Output | +| :----------: | :-----------: | +| 10 | 5 | + +## TAM GIÁC (TRIANGLE.*) + +Cho ba số nguyên a, b, c là độ dài ba cạnh của một tam giác, hãy cho biết tam +giác đó là tam giác vuông, nhọn, hay tù. + +### Dữ liệu + +Vào từ thiết bị nhập chuẩn ba số nguyên dương a, b, c cách nhau bởi dấu cách. + +### Kết quả + +Ghi ra thiết bị xuất chuẩn số 0, 1, hay 2 tùy theo tam giác đó là vuông, nhọn, +hay tù. + +### Ví dụ + +| Sample Input | Sample Output | +| :----------: | :-----------: | +| 3 4 5 | 0 | +| 3 3 3 | 1 | +| 3 4 6 | 2 | + +## HỆ THỐNG ĐÈN MÀU (DECOR.*) + +Để trang trí cho một lễ hội, ban tổ chức đã dùng một hệ thống đèn màu gồm n đèn +đánh số từ 1 đến n. Mỗi đèn có khả năng sáng màu xanh hoặc màu đỏ. Các đèn được +điều khiển theo quy tắc sau: + +* Bấm công tắc lần 1, tất cả các đèn đều sáng màu xanh. +* Bấm công tắc lần 2, tất cả các đèn có số thứ tự chia hết cho 2 sẽ đổi màu + (xanh thành đỏ và ngược lại). +* Bấm công tắc lần 3, tất cả các đèn có số thứ tự chia hết cho 3 sẽ đổi màu + (xanh thành đỏ và ngược lại). +* ... +* Bấm công tắc lần n, tất cả các đèn có số thứ tự chia hết cho n sẽ đổi màu + (xanh thành đỏ và ngược lại). + +### Yêu cầu + +Xác định số đèn sáng màu xanh sau n lần bấm công tắc. + +### Dữ liệu + +Vào từ thiết bị nhập chuẩn số nguyên dương n ≤ 1018. + +### Kết quả + +Ghi ra thiết bị xuất chuẩn số đèn xanh sau lần bấm công tắc thứ n. + +### Ví dụ + +| Sample Input | Sample Output | +| :----------: | :-----------: | +| 6 | 2 | diff --git a/others/mHoang/decor.c b/others/mHoang/decor.c new file mode 100644 index 0000000..54cb2c6 --- /dev/null +++ b/others/mHoang/decor.c @@ -0,0 +1,13 @@ +#include +#include + +int main() +{ + unsigned long long n; + + scanf("%lld", &n); + + printf("%ld\n", (unsigned long) sqrt(n)); + + return 0; +} diff --git a/others/mHoang/decor.py b/others/mHoang/decor.py new file mode 100755 index 0000000..a083f6d --- /dev/null +++ b/others/mHoang/decor.py @@ -0,0 +1,15 @@ +#!/usr/bin/env python3 + +# Dễ thấy các đèn đổi màu lẻ lần có màu xanh, chẵn lần màu đỏ. +# +# Xét đèn thứ i: +# * Giả sử phân tích i thành các ước nguyên tố: i = p1 ** q1 + ... + pm ** qm, +# khi đó i sẽ có k = (q1 + 1) * ... * (qm + 1) ước nguyên dương. +# * Đèn thứ i sẽ được đổi màu ở lần bấm công tắc nhận i làm bội, hay sẽ đổi màu +# k lần. +# * k lẻ khi và chỉ khi q1 + 1, ..., qm + 1 đều lẻ hay q1, ..., qm đều chẵn tức +# là i là số chính phương. +# +# Vậy kết quả cần tìm là số số chính phương từ 1 đến n. + +print(int(int(input()) ** 0.5)) diff --git a/others/mHoang/pfactor.c b/others/mHoang/pfactor.c new file mode 100644 index 0000000..fee50b5 --- /dev/null +++ b/others/mHoang/pfactor.c @@ -0,0 +1,21 @@ +#include +#include + +int main() +{ + long long n, sqrtn; + long i, tmp; + + scanf("%lld", &n); + sqrtn = sqrt(n); + + for (i = 2; i <= sqrtn && n > 1; i++) + while (n % i == 0) { + n /= i; + tmp = i; + } + + printf("%lld\n", (n == 1) ? tmp : n); + + return 0; +} diff --git a/others/mHoang/triangle.c b/others/mHoang/triangle.c new file mode 100644 index 0000000..0f5d28e --- /dev/null +++ b/others/mHoang/triangle.c @@ -0,0 +1,19 @@ +#include + +char angle(long x, long y, long z) +{ + long long tmp = x * x + y * y - z * z; + + return (tmp ? (tmp > 0 ? 1 : 2) : tmp); +} + +int main() +{ + long a, b, c; + + scanf("%ld %ld %ld", &a, &b, &c); + + printf("%hhd\n", angle(a, b, c) * angle(b, c, a) * angle(c, a, b)); + + return 0; +} diff --git a/others/mHoang20150916/README.md b/others/mHoang20150916/README.md deleted file mode 100644 index 3f6d5b0..0000000 --- a/others/mHoang20150916/README.md +++ /dev/null @@ -1,42 +0,0 @@ -# mHoang - -## THỪA SỐ NGUYÊN TỐ (PFACTOR.*) - -Cho số nguyên dương n, tìm số nguyên tố p lớn nhất là ước số của n. - -### Dữ liệu - -Vào từ thiết bị nhập chuẩn số nguyên n, (2 ≤ n ≤ 1014). - -### Kết quả - -Ghi ra thiết bị xuất chuẩn một số nguyên duy nhất là ước số nguyên tố lớn nhất -của n. - -### Ví dụ - -| Sample Input | Sample Output | -| :----------: | :-----------: | -| 10 | 5 | - -## TAM GIÁC (TRIANGLE.*) - -Cho ba số nguyên a, b, c là độ dài ba cạnh của một tam giác, hãy cho biết tam -giác đó là tam giác vuông, nhọn, hay tù. - -### Dữ liệu - -Vào từ thiết bị nhập chuẩn ba số nguyên dương a, b, c cách nhau bởi dấu cách. - -### Kết quả - -Ghi ra thiết bị xuất chuẩn số 0, 1, hay 2 tùy theo tam giác đó là vuông, nhọn, -hay tù. - -### Ví dụ - -| Sample Input | Sample Output | -| :----------: | :-----------: | -| 3 4 5 | 0 | -| 3 3 3 | 1 | -| 3 4 6 | 2 | diff --git a/others/mHoang20150916/pfactor.c b/others/mHoang20150916/pfactor.c deleted file mode 100644 index fee50b5..0000000 --- a/others/mHoang20150916/pfactor.c +++ /dev/null @@ -1,21 +0,0 @@ -#include -#include - -int main() -{ - long long n, sqrtn; - long i, tmp; - - scanf("%lld", &n); - sqrtn = sqrt(n); - - for (i = 2; i <= sqrtn && n > 1; i++) - while (n % i == 0) { - n /= i; - tmp = i; - } - - printf("%lld\n", (n == 1) ? tmp : n); - - return 0; -} diff --git a/others/mHoang20150916/triangle.c b/others/mHoang20150916/triangle.c deleted file mode 100644 index 0f5d28e..0000000 --- a/others/mHoang20150916/triangle.c +++ /dev/null @@ -1,19 +0,0 @@ -#include - -char angle(long x, long y, long z) -{ - long long tmp = x * x + y * y - z * z; - - return (tmp ? (tmp > 0 ? 1 : 2) : tmp); -} - -int main() -{ - long a, b, c; - - scanf("%ld %ld %ld", &a, &b, &c); - - printf("%hhd\n", angle(a, b, c) * angle(b, c, a) * angle(c, a, b)); - - return 0; -} diff --git a/others/mkcal/README.md b/others/mkcal/README.md new file mode 100644 index 0000000..bebe188 --- /dev/null +++ b/others/mkcal/README.md @@ -0,0 +1,148 @@ +# Bài tập lập lịch + +## Chương trình máy tính + +Giả sử trong một phiên làm việc từ thời điểm 0 đến 8640000, một trung tâm tính +toán cần thực hiện n chương trình, chương trình i được thực hiện trong đoạn +thời gian [ai, bi]. + +### Yêu cầu + +* Cho đoạn thời gian [p0, q0], kiểm tra xem mọi thời điểm + của đoạn luôn có chương trình chạy hay không. +* Cho đoạn thời gian [r0, s0], kiểm tra xem mọi thời điểm + của đoạn luôn không có chương trình chạy hay không. +* Tìm đoạn thời gian [p, q] dài nhất luôn có chương trình chạy. +* Tìm đoạn thời gian [r, s] dài nhất không có chương trình chạy. + +### Dữ liệu vào + +* Dòng đầu ghi số nguyên dương n. +* n dòng tiếp theo, với i từ 1 đến n, dòng thứ i + 1 ghi hai số tự nhiên + ai và bi. +* Dòng thứ n + 2 ghi hai số tự nhiên p0, q0. +* Dòng thứ n + 3 ghi hai số tự nhiên r0, s0. + +### Dữ liệu ra + +* Dòng đầu ghi 1 nếu đoạn thời gian [p0, q0] luôn có + chương trình chạy, ghi 0 nếu không phải. +* Dòng thứ hai ghi 1 nếu đoạn thời gian [r0, s0] không có + chương trình nào chạy, ghi 0 nếu có. +* Dòng thứ ba ghi hai số p và q. +* Dòng thứ tư ghi hai số r và s. + +### Giới hạn + +* n ≤ 200 +* 0 ≤ ai ≤ bi < 8640000 +* 0 ≤ p0 ≤ q0 < 8640000 +* 0 ≤ r0 ≤ s0 < 8640000 + +### Ví dụ + +| CTMT.OUT | CTMT.INP | +| --------------- | --------------- | +| 5 | 1 | +| 1000 10000 | 0 | +| 2000 30000 | 8000000 8500000 | +| 20000 100000 | 500001 7999999 | +| 200000 500000 | | +| 8000000 8500000 | | +| 1000 100000 | | +| 0 1000 | | + +## Xếp việc + +Cho n công việc, mỗi công việc phải làm trước một số công việc nào đó khác. + +Hãy xếp lịch thực hiện đủ n công việc. + +### Dữ liệu vào + +* Dòng đầu là số nguyên dương n. +* Các dòng tiếp, đầu dòng là số thứ tự i của một công việc, tiếp theo là số thứ + tự của các công việc phải làm sau i. + +### Dữ liệu ra + +Thứ thự thực hiện của n công việc in trên một dòng. + +### Giới hạn + +* 2 ≤ n ≤ 200 +* 1 ≤ i ≤ n + + +### Ví dụ + +| XEPVIEC.INP | XEPVIEC.OUT | +| ----------- | -------------------- | +| 10 | 1 2 7 9 4 6 3 5 8 10 | +| 1 2 3 | | +| 2 4 10 | | +| 3 5 | | +| 4 6 8 | | +| 5 8 | | +| 6 3 | | +| 7 9 5 | | +| 9 4 10 | | + +## Lập lịch gia công trên hai máy + +Một sản phẩm gồm n chi tiết, mỗi chi tiết phải gia công lần lượt trên hai máy a +và b. Thời gian thực hiện chi tiết i trên máy a là ai, trên máy b là +bi. + +Hãy xếp lịch hoàn thành sản phẩm với thời gian ngắn nhất. + +### Dữ liệu vào + +* Dòng đầu là số nguyên dương n. +* n dòng tiếp theo, dòng thứ i + 1 lần lượt là hai số nguyên dương + ai, bi. + +### Dữ liệu ra + +* Dòng đầu là thời gian ngắn nhất để hoàn thành sản phẩm. +* Dòng thứ hai ghi thứ tự gia công các chi tiết để hoàn thành trong thời gian + ngắn nhất này. + +### Ví dụ + +| LLGC2M.INP | LLGC2M.OUT | +| ---------- | ---------- | +| 5 | 26 | +| 3 3 | 1 4 2 5 3 | +| 4 3 | | +| 6 2 | | +| 5 7 | | +| 6 3 | | + +## Lập lịch chia n việc cho m máy + +Cho n công việc, công việc i hoàn thành trong thời gian ti. Các công +việc được thực hiện trên m máy có công suất như nhau. + +Hãy phân chia công việc cho các máy sao cho thời gian hoàn thành ngắn nhất. + +### Dữ liệu vào + +* Dòng đầu lần lượt ghi hai số nguyên dương n và m. +* Dòng thứ hai là n số nguyên dương t1, t2, ..., + tn. + +### Dữ liệu ra + +* Dòng đầu là thời gian ngắn nhất để hoàn thành công việc. +* m dòng tiếp theo, dòng thứ i + 1 ghi số thứ tự các công việc thực hiện trên + máy i để hoàn thành công việc trong thời gian ngắn nhất này. + +### Ví dụ + +| LLGCMM.INP | LLGCMM.OUT | +| ----------- | ---------- | +| 6 3 | 8 | +| 2 5 8 1 5 1 | 3 | +| | 2 4 1 | +| | 5 6 | diff --git a/others/mkcal/llgcmm.pas b/others/mkcal/llgcmm.pas new file mode 100644 index 0000000..76ea699 --- /dev/null +++ b/others/mkcal/llgcmm.pas @@ -0,0 +1,97 @@ +type + foo_t = record + t, idx: integer + end; + +var + f: text; + n, m, i, j, k: integer; + a: array of foo_t; + b: array of array of foo_t; + c: array of longint; + foo: foo_t; + tmp: longint; + + +procedure swp(var x, y: foo_t); + var + tmp: integer; + + begin + tmp := x.t; + x.t := y.t; + y.t := tmp; + + tmp := x.idx; + x.idx := y.idx; + y.idx := tmp + end; + + +begin + assign(f, 'LLGCMM.INP'); + reset(f); + + readln(f, n, m); + setlength(a, n); + + for i := 0 to n - 1 do + read(f, a[i].t); + + close(f); + + for i := 1 to n do + a[i - 1].idx := i; + + for i := 0 to n - 2 do + for j := i to n - 1 do + if a[i].t < a[j].t then + swp(a[i], a[j]); + + setlength(b, m); + setlength(c, m); + + for i := 0 to m - 1 do + begin + setlength(b[i], 0); + c[i] := 0 + end; + + for i := 0 to n - 1 do + begin + tmp := c[0]; + k := 0; + + for j := 1 to m - 1 do + if c[j] < tmp then + begin + k := j; + tmp := c[j] + end; + + setlength(b[k], length(b[k]) + 1); + b[k][length(b[k]) - 1].t := a[i].t; + b[k][length(b[k]) - 1].idx := a[i].idx; + c[k] := c[k] + a[i].t + end; + + tmp := 0; + for i := 0 to m - 1 do + if c[i] > tmp then + tmp := c[i]; + + assign(f, 'LLGCMM.OUT'); + rewrite(f); + + writeln(f, tmp); + + for i := 0 to m - 1 do + begin + for foo in b[i] do + write(f, foo.idx, ' '); + + writeln(f); + end; + + 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" deleted file mode 100755 index 48ad249..0000000 Binary files "a/others/mkcal/l\341\272\255p-l\341\273\213ch.pdf" and /dev/null differ -- cgit 1.4.1