From 1f06cc322606e86918fefa1f707b54264e9ce0a9 Mon Sep 17 00:00:00 2001
From: Raphael McSinyx <vn.mcsinyx@gmail.com>
Date: Sun, 6 Nov 2016 21:53:13 +0700
Subject: Add others/dict

---
 "10/l\341\272\255p-l\341\273\213ch/ctmt.pas"       |  86 ---------------------
 "10/l\341\272\255p-l\341\273\213ch/llgc2m.pas"     |  44 -----------
 .../l\341\272\255p-l\341\273\213ch.pdf"            | Bin 52261 -> 0 bytes
 "10/l\341\272\255p-l\341\273\213ch/xepviec.pas"    |  53 -------------
 README.md                                          |  22 ++++--
 others/dict/README.md                              |  53 +++++++++++++
 others/dict/dict.py                                |  21 +++++
 "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 0 -> 52261 bytes
 .../l\341\272\255p-l\341\273\213ch/xepviec.pas"    |  53 +++++++++++++
 11 files changed, 271 insertions(+), 191 deletions(-)
 delete mode 100755 "10/l\341\272\255p-l\341\273\213ch/ctmt.pas"
 delete mode 100755 "10/l\341\272\255p-l\341\273\213ch/llgc2m.pas"
 delete mode 100755 "10/l\341\272\255p-l\341\273\213ch/l\341\272\255p-l\341\273\213ch.pdf"
 delete mode 100755 "10/l\341\272\255p-l\341\273\213ch/xepviec.pas"
 create mode 100644 others/dict/README.md
 create mode 100755 others/dict/dict.py
 create mode 100755 "others/l\341\272\255p-l\341\273\213ch/ctmt.pas"
 create mode 100755 "others/l\341\272\255p-l\341\273\213ch/llgc2m.pas"
 create mode 100755 "others/l\341\272\255p-l\341\273\213ch/l\341\272\255p-l\341\273\213ch.pdf"
 create mode 100755 "others/l\341\272\255p-l\341\273\213ch/xepviec.pas"

diff --git "a/10/l\341\272\255p-l\341\273\213ch/ctmt.pas" "b/10/l\341\272\255p-l\341\273\213ch/ctmt.pas"
deleted file mode 100755
index bdd30f0..0000000
--- "a/10/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/10/l\341\272\255p-l\341\273\213ch/llgc2m.pas" "b/10/l\341\272\255p-l\341\273\213ch/llgc2m.pas"
deleted file mode 100755
index 3fc8ef2..0000000
--- "a/10/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/10/l\341\272\255p-l\341\273\213ch/l\341\272\255p-l\341\273\213ch.pdf" "b/10/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/10/l\341\272\255p-l\341\273\213ch/l\341\272\255p-l\341\273\213ch.pdf" and /dev/null differ
diff --git "a/10/l\341\272\255p-l\341\273\213ch/xepviec.pas" "b/10/l\341\272\255p-l\341\273\213ch/xepviec.pas"
deleted file mode 100755
index cfa39d6..0000000
--- "a/10/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/README.md b/README.md
index 6ab07b1..6fcb262 100644
--- a/README.md
+++ b/README.md
@@ -2,14 +2,20 @@
 
 Bài tập luyện tập thi Olympic, học sinh giỏi Tin học, trong đó:
 
-|        Thư mục        |                          Nguồn đề bài                          |
-| --------------------- | -------------------------------------------------------------- |
-| `9`, `10`, `11`, `12` | Bài tập, đề thi *chính quy* phân theo lớp                      |
-| `COCI`                | [Giải Tin học Croatia mở rộng](http://www. hsin.hr/coci/)      |
-| `NTU`                 | [Đại học Nha Trang](http://laptrinh.ntu.ed u.vn/)              |
-| `THT`                 | Hội thi Tin học trẻ                                            |
-| `codeforces`          | [Codeforces](http://codeforces.com/)                           |
-| `daily`               | [/r/dailyprogrammer](https://www.reddit.com/r/dailyprogrammer) |
+|        Thư mục        |           Nguồn đề bài            |
+| --------------------- | --------------------------------- |
+| `9`, `10`, `11`, `12` | Đề thi, kiểm tra phân theo lớp    |
+| `COCI`                | [Giải Tin học Croatia mở rộng][0] |
+| `NTU`                 | [Đại học Nha Trang][1]            |
+| `THT`                 | Hội thi Tin học trẻ               |
+| `codeforces`          | [Codeforces][2]                   |
+| `daily`               | [/r/dailyprogrammer][3]           |
+| `others`              | Các đề bài không rõ nguồn         |
+
+[0]: http://www.hsin.hr/coci/
+[1]: http://laptrinh.ntu.edu.vn/
+[2]: http://codeforces.com/
+[3]: https://www.reddit.com/r/dailyprogrammer
 
 Ở mỗi thư mục con sẽ có tệp `README.md` ghi lại đề bài. Riêng `COCI`, `NTU` và
 `codeforces` sẽ chỉ có danh sách đường dẫn tới các đề bài. Đề bài sẽ được cập
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\341\272\255p-l\341\273\213ch/ctmt.pas" "b/others/l\341\272\255p-l\341\273\213ch/ctmt.pas"
new file mode 100755
index 0000000..bdd30f0
--- /dev/null
+++ "b/others/l\341\272\255p-l\341\273\213ch/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\341\272\255p-l\341\273\213ch/llgc2m.pas" "b/others/l\341\272\255p-l\341\273\213ch/llgc2m.pas"
new file mode 100755
index 0000000..3fc8ef2
--- /dev/null
+++ "b/others/l\341\272\255p-l\341\273\213ch/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\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"
new file mode 100755
index 0000000..48ad249
Binary files /dev/null and "b/others/l\341\272\255p-l\341\273\213ch/l\341\272\255p-l\341\273\213ch.pdf" 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"
new file mode 100755
index 0000000..cfa39d6
--- /dev/null
+++ "b/others/l\341\272\255p-l\341\273\213ch/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