VD2016BT1 - Robot gõ tắt
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 2.0 giây
Giới hạn bộ nhớ: 512 megabyte
Đăng bởi: phuleethanh

     Để chuẩn bị cho cuộc thi “Ngôi sao lập trình” tại trường cấp 3 Vĩnh Định của mình, Bin và Nhin lập thành đội BiNi để tham dự. Để gây ấn tượng với BGK, đội bini quyết tìm hiểu một vài kiến thức hay để tạo ra sản phẩm hấp dẫn nhất có thể.

     Hai bạn quyết định sản phẩm của mình là RobotTyping – Robot đánh chữ. Chương trình này sẽ giúp cho việc gõ phím trên máy tính được nhanh hơn. Ví dụ: từ ‘Bin’ thay vì gõ vào 3 phím bây giờ hai bạn nghĩ đến làm sao có thể gõ tắt nhanh hơn, có thể một phím chẳng hạn. Để làm điều này hai bạn đã chuẩn bị sẵn danh sách N từ (1<n<10^5) mà người dùng có thể gõ. Với mỗi từ, khi người dùng gõ từ đầu tiên, phần mềm sẽ đoán và chèn thêm vào nhiều nhất các chữ cái có thể.

     Ví dụ: Với N=2, danh sách từ là ‘hello’ và hell. Với từ thứ nhất khi người dùng gõ ‘h’ thì hệ thống tự thêm vào 3 kí tự ‘ell’ (không thể thêm tiếp kí tự nào vì hệ thống chưa thể nhận biết được người dùng sẽ gõ ‘hello’ hay gõ ‘hell’), người dùng gõ tiếp ‘o’ để hoàn thành từ cần gõ. Với từ thứ 2 người dùng chỉ cần gõ ‘h’ là đã hoàn thành từ cần gõ. Vậy với danh sách từ này người dùng muốn gõ 2 từ thì trung bình cần thực hiện (2+1)/2=1.50 thao tác.

     Với một danh sách từ bất kì, bạn được đội Bini thử thách tính số thao tác trung bình để gõ hết các từ có trong danh sách.

Dữ liệu vào: Gồm nhiều test, mỗi test gồm:

- Dòng đầu tiên là số từ N

- N dòng tiếp theo là N từ có trong danh sách (các từ chỉ chứa kí tự chữ cái thường, độ dài từ không quá 80)

Kết quả:

- Gồm nhiều dòng, dòng thứ i là đáp án cho test thứ i. (làm tròn 2 chữ số thập phân)

Ví dụ

  • input
    3
    chao
    chaoban
    chaochu
    4
    coder
    coderntu
    ntucoder
    ntumember
    2
    hello
    hell
    output
    1.67
    1.75
    1.50

Nguồn bài: UVA 12526

Back to Top