about summary refs log tree commit diff
path: root/others/mkcal
diff options
context:
space:
mode:
Diffstat (limited to 'others/mkcal')
-rw-r--r--others/mkcal/README.md148
-rw-r--r--others/mkcal/llgcmm.pas97
-rwxr-xr-xothers/mkcal/lập-lịch.pdfbin52261 -> 0 bytes
3 files changed, 245 insertions, 0 deletions
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 [a<sub>i</sub>, b<sub>i</sub>].
+
+### Yêu cầu
+
+* Cho đoạn thời gian [p<sub>0</sub>, q<sub>0</sub>], 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 [r<sub>0</sub>, s<sub>0</sub>], 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
+  a<sub>i</sub> và b<sub>i</sub>.
+* Dòng thứ n + 2 ghi hai số tự nhiên p<sub>0</sub>, q<sub>0</sub>.
+* Dòng thứ n + 3 ghi hai số tự nhiên r<sub>0</sub>, s<sub>0</sub>.
+
+### Dữ liệu ra
+
+* Dòng đầu ghi 1 nếu đoạn thời gian [p<sub>0</sub>, q<sub>0</sub>] 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 [r<sub>0</sub>, s<sub>0</sub>] 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 ≤ a<sub>i</sub> ≤ b<sub>i</sub> < 8640000
+* 0 ≤ p<sub>0</sub> ≤ q<sub>0</sub> < 8640000
+* 0 ≤ r<sub>0</sub> ≤ s<sub>0</sub> < 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à a<sub>i</sub>, trên máy b là
+b<sub>i</sub>.
+
+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
+  a<sub>i</sub>, b<sub>i</sub>.
+
+### 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 t<sub>i</sub>. 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 t<sub>1</sub>, t<sub>2</sub>, ...,
+  t<sub>n</sub>.
+
+### 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ập-lịch.pdf b/others/mkcal/lập-lịch.pdf
deleted file mode 100755
index 48ad249..0000000
--- a/others/mkcal/lập-lịch.pdf
+++ /dev/null
Binary files differ