From 1f06cc322606e86918fefa1f707b54264e9ce0a9 Mon Sep 17 00:00:00 2001 From: Raphael McSinyx Date: Sun, 6 Nov 2016 21:53:13 +0700 Subject: Add others/dict --- 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 +++++++++++++ 6 files changed, 257 insertions(+) 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" (limited to 'others') 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