Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P143SUMG - ROUND 3G - Sửa lỗi chính tả |
Ngày nay, xu hướng sử dụng smart phone đã trở thành rất phổ biến trên thế giới. Thay vì phải bấm từng phím cứng, người dùng chỉ cần chạm vào màn hình. Tuy nhiên, việc nhập sai nội dung từ xảy ra thường xuyên do không gian cho mỗi phím trên màn hình là hạn chế.
Một phần mềm sửa lỗi chính tả được người dùng khá ưa chuộng có chức năng như sau: khi người dùng nhập một từ trên màn hình, phần mềm này sẽ đưa ra danh sách các từ đúng để người dùng có thể lựa chọn. Tuy nhiên, bạn vẫn có thể cải thiện thêm tính năng cho phần mềm này, bằng cách sắp xếp các từ gợi ý theo độ ưu tiên “gần giống” với từ đã nhập nhất. Khoảng cách giữa 2 chữ cái được tính bằng tổng sai khác theo chiều ngang và chiều dọc của 2 chữ cái trên màn hình. Khoảng cách giữa 2 từ được tính bằng tổng khoảng cách của tất cả các chữ cái.
Bàn phím querty trên màn hình của điện thoại như sau:
qwertyuiop
asdfghjkl
zxcvbnm
Ví dụ, khoảng cách giữa kí tự ‘w’ và kí tự ‘e’ bằng 1, giữa ‘w’ và ‘z’bằng 3.
Input
Dòng đầu tiên là số lượng bộ test T (T <= 20).
Mỗi bộ test bằng đầu bằng một từ (là chuỗi kí tự được nhập trên màn hình) và số nguyên n (n <= 10), là số từ gợi ý của phần mềm kiểm tra lỗi chính tả. n dòng tiếp theo, mỗi dòng là một từ gợi ý. Các từ gợi ý có chiều dài bằng với từ đã nhập ban đầu, và khác nhau đôi một.
Tất cả các chữ cái đều là chữ thường, và các từ có độ dài nhỏ hơn 10 000.
Output
Với mỗi test, in ra danh sách các từ gợi ý theo thứ tự ưu tiên tăng dần (khoảng cách so với từ đã nhập là nhỏ nhất). Nếu có nhiều từ có cùng khoảng cách với từ đã nhập, in ra theo thứ tự từ điển.
Example
Input: 2
qwertyuiopasdfghjklzxcvbnm 3
qwertyuiopsdfghjklzxcvbnma
mnbvcxzlkjhgfdsapoiuytrewq
mnbvcxzlkjhgfdsapoiuytrewa
edc 5
wsx
edc
rfv
plm
qed Output: qwertyuiopsdfghjklzxcvbnma 30
mnbvcxzlkjhgfdsapoiuytrewa 109
mnbvcxzlkjhgfdsapoiuytrewq 110
edc 0
rfv 3
wsx 3
qed 4
plm 17
Được gửi lên bởi: | adm |
Ngày: | 2014-07-08 |
Thời gian chạy: | 1s |
Giới hạn mã nguồn: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
hide comments
2015-05-21 14:02:38 Nguyễn Vĩnh Thịnh
cay quá không kiểm tra kĩ viết j nhầm thành i thế là mất 1 đấm AC @@ |