diff options
-rw-r--r-- | README.md | 22 | ||||
-rw-r--r-- | others/dict/README.md | 53 | ||||
-rwxr-xr-x | others/dict/dict.py | 21 | ||||
-rwxr-xr-x | others/lập-lịch/ctmt.pas (renamed from 10/lập-lịch/ctmt.pas) | 0 | ||||
-rwxr-xr-x | others/lập-lịch/llgc2m.pas (renamed from 10/lập-lịch/llgc2m.pas) | 0 | ||||
-rwxr-xr-x | others/lập-lịch/lập-lịch.pdf (renamed from 10/lập-lịch/lập-lịch.pdf) | bin | 52261 -> 52261 bytes | |||
-rwxr-xr-x | others/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 |