about summary refs log tree commit diff
diff options
context:
space:
mode:
-rw-r--r--README.md22
-rw-r--r--others/dict/README.md53
-rwxr-xr-xothers/dict/dict.py21
-rwxr-xr-xothers/lập-lịch/ctmt.pas (renamed from 10/lập-lịch/ctmt.pas)0
-rwxr-xr-xothers/lập-lịch/llgc2m.pas (renamed from 10/lập-lịch/llgc2m.pas)0
-rwxr-xr-xothers/lập-lịch/lập-lịch.pdf (renamed from 10/lập-lịch/lập-lịch.pdf)bin52261 -> 52261 bytes
-rwxr-xr-xothers/lập-lịch/xepviec.pas (renamed from 10/lập-lịch/xepviec.pas)0
7 files changed, 88 insertions, 8 deletions
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/10/lập-lịch/ctmt.pas b/others/lập-lịch/ctmt.pas
index bdd30f0..bdd30f0 100755
--- a/10/lập-lịch/ctmt.pas
+++ b/others/lập-lịch/ctmt.pas
diff --git a/10/lập-lịch/llgc2m.pas b/others/lập-lịch/llgc2m.pas
index 3fc8ef2..3fc8ef2 100755
--- a/10/lập-lịch/llgc2m.pas
+++ b/others/lập-lịch/llgc2m.pas
diff --git a/10/lập-lịch/lập-lịch.pdf b/others/lập-lịch/lập-lịch.pdf
index 48ad249..48ad249 100755
--- a/10/lập-lịch/lập-lịch.pdf
+++ b/others/lập-lịch/lập-lịch.pdf
Binary files differdiff --git a/10/lập-lịch/xepviec.pas b/others/lập-lịch/xepviec.pas
index cfa39d6..cfa39d6 100755
--- a/10/lập-lịch/xepviec.pas
+++ b/others/lập-lịch/xepviec.pas