Gợi ý từ

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho một từ điển gồm $W$ từ. Với mỗi truy vấn, bạn cần tìm từ thứ $K$ theo thứ tự bảng chữ cái trong số các từ trong từ điển có tiền tố là xâu cho trước. Nếu không tồn tại từ thứ $K$ như vậy, trả về $- 1$ .

Dữ liệu vào

Dòng 1: Hai số nguyên $W$ và $N$ — số từ trong từ điển và số truy vấn.
$W$ dòng tiếp theo: Mỗi dòng là một từ trong từ điển (chỉ gồm chữ thường a–z). Các từ được đánh số từ $1$ đến $W$ theo thứ tự xuất hiện.
$N$ dòng tiếp theo: Mỗi dòng là một truy vấn gồm số nguyên $K_{i}$ và một xâu $p_{i}$ — tìm từ thứ $K_{i}$ theo thứ tự từ điển trong số các từ có tiền tố là $p_{i}$ .

Dữ liệu ra

Với mỗi truy vấn, in ra chỉ số (1-based) trong từ điển của từ cần tìm. Nếu không tồn tại, in ra $- 1$ .

Ràng buộc

$1 \leq W$ ; tổng độ dài tất cả các từ trong từ điển $\leq 10^{6}$
$1 \leq N \leq 10000$ ; độ dài mỗi xâu truy vấn $\leq 1000$
$1 \leq K_{i} \leq 10^{6}$

Ví dụ

Input	Output	Giải thích
10 3 dab ba ab daa aa aaa aab abc ac dadba 4 a 2 da 4 da	3 1 -1	Các từ có tiền tố "a" theo thứ tự từ điển: aa, aaa, aab, ab, abc, ac. Từ thứ 4 là "ab" (chỉ số 3 trong từ điển). Các từ có tiền tố "da": daa, dab, dadba. Từ thứ 2 là "dab" (chỉ số 1). Không có từ thứ 4 nên trả về -1.

Bình luận

Không có bình luận tại thời điểm này.