about summary refs log tree commit diff
path: root/others/dict
diff options
context:
space:
mode:
Diffstat (limited to 'others/dict')
-rw-r--r--others/dict/README.md53
-rw-r--r--others/dict/dict.c53
-rwxr-xr-xothers/dict/dict.py17
3 files changed, 0 insertions, 123 deletions
diff --git a/others/dict/README.md b/others/dict/README.md
deleted file mode 100644
index 50ff841..0000000
--- a/others/dict/README.md
+++ /dev/null
@@ -1,53 +0,0 @@
-# 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.c b/others/dict/dict.c
deleted file mode 100644
index 9821828..0000000
--- a/others/dict/dict.c
+++ /dev/null
@@ -1,53 +0,0 @@
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-
-int cmpstr(const void *s1, const void *s2)
-{
-	return strcmp((char *) s1, (char *) s2);
-}
-
-short bistr(char (*a)[21], char *x, short hi)
-{
-	short lo = 0, mid;
-
-	while (lo < hi) {
-		mid = (lo + hi) / 2;
-		if (strcmp(a[mid], x) < 0)
-			lo = mid + 1;
-		else
-			hi = mid;
-	}
-
-	return lo;
-}
-
-int main()
-{
-	FILE *fi = fopen("dict.inp", "r"), *fo = fopen("dict.out", "w");
-	short n, q, i, idx, count;
-	char (*words)[21], s[21];
-
-	fscanf(fi, "%hd", &n);
-
-	words = malloc(n * 21);
-	for (i = 0; i < n; i++)
-		fscanf(fi, "%s", words[i]);
-	qsort(words, n, 21, cmpstr);
-
-	fscanf(fi, "%hd", &q);
-
-	for (i = 0; i < q; i++) {
-		fscanf(fi, "%s", s);
-		idx = bistr(words, s, n);
-		count = idx;
-		while (count < n && !strncmp(words[count], s, strlen(s)))
-			count++;
-		fprintf(fo, "%hd\n", count - idx);
-	}
-
-	fclose(fi);
-	fclose(fo);
-
-	return 0;
-}
diff --git a/others/dict/dict.py b/others/dict/dict.py
deleted file mode 100755
index 76b8414..0000000
--- a/others/dict/dict.py
+++ /dev/null
@@ -1,17 +0,0 @@
-#!/usr/bin/env python3
-
-from itertools import islice
-from bisect import bisect_left as bisect
-
-
-with open('dict.inp') as fi, open('dict.out', 'w') as fo:
-    words = list(islice(fi, int(fi.readline())))
-    words.sort()
-
-    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))