Add others/dict

6 files changed, 257 insertions, 0 deletions

diff --git a/others/dict/README.md b/others/dict/README.md
new file mode 100644
index 0000000..50ff841
--- /dev/null
+++ b/others/dict/README.md
@@ -0,0 +1,53 @@
+# Từ điển
+
+Cho một từ điển, là một danh sách gồm `n` từ `w`. Cho `q` truy vấn, mỗi truy vấn đưa ra
+một xâu `s`, yêu cầu đếm xem có bao nhiêu từ có tiền tố là `s`.
+
+## Input
+
+`dict.inp` gồm `n` + `q` + 2 dòng:
+
+* Dòng 1: Gồm một số nguyên là số `n`, số lượng từ của từ điển.
+* Dòng 2 đến `n` + 1: Mỗi dòng gồm một xâu kí tự `w` là một từ thuộc từ điển.
+* Dòng `n` + 2: Gồm một số nguyên là số `q`, số lượng truy vấn.
+* Dòng `n` + 3 đến `n` + `q` + 2: Mỗi dòng gồm một xâu kí tự `s` mô tả một tiền
+  tố cần đếm.
+
+## Output
+
+`dict.out` gồm `q` dòng, mỗi dòng gồm một số nguyên là câu trả lời cho
+truy vấn tương ứng.
+
+## Giới hạn
+
+* 1 ≤ `n`, `q` ≤ 20000.
+* 1 ≤ Độ dài `w`, `s` ≤ 20.
+* Các xâu `w`, `s` gồm các chữ cái in thường (từ `a` đến `z`).
+
+## Ví dụ
+
+`dict.inp`:
+
+    4
+    banana
+    ban
+    baconsoi
+    alibaba
+    4
+    ban
+    ba
+    ali
+    baba
+
+`dict.out`:
+
+    2
+    3
+    1
+    0
+
+Giải thích:
+
+* 2 từ có tiền tố `ban` là: `banana`, `ban`.
+* 3 từ có tiền tố `ba` là: `banana`, `ban`, `baconsoi`.
+* 2 từ có tiền tố `ali` là: `alibaba`.
diff --git a/others/dict/dict.py b/others/dict/dict.py
new file mode 100755
index 0000000..59724cd
--- /dev/null
+++ b/others/dict/dict.py
@@ -0,0 +1,21 @@
+#!/usr/bin/env python3
+
+from bisect import bisect_left as bisect
+
+words = []
+
+
+with open('dict.inp') as fi, open('dict.out', 'w') as fo:
+    for _ in range(int(fi.readline())):
+        w = fi.readline().strip()
+        i = bisect(words, w)
+        if i == len(words) or w != words[i]:
+            words.insert(i, w)
+
+    for _ in range(int(fi.readline())):
+        s = fi.readline().strip()
+        i = bisect(words, s)
+        count = 0
+        while i + count < len(words) and words[i + count].startswith(s):
+            count += 1
+        fo.write("{}\n".format(count))
diff --git a/others/lập-lịch/ctmt.pas b/others/lập-lịch/ctmt.pas
new file mode 100755
index 0000000..bdd30f0
--- /dev/null
+++ b/others/lập-lịch/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/lập-lịch/llgc2m.pas b/others/lập-lịch/llgc2m.pas
new file mode 100755
index 0000000..3fc8ef2
--- /dev/null
+++ b/others/lập-lịch/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/lập-lịch/lập-lịch.pdf b/others/lập-lịch/lập-lịch.pdf
new file mode 100755
index 0000000..48ad249
--- /dev/null
+++ b/others/lập-lịch/lập-lịch.pdf
Binary files differdiff --git a/others/lập-lịch/xepviec.pas b/others/lập-lịch/xepviec.pas
new file mode 100755
index 0000000..cfa39d6
--- /dev/null
+++ b/others/lập-lịch/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.