Sau khi đi du lịch từ thành phố Alpha về, Steve vẫn còn dư tiền thưởng và quyết định đi mua bàn phím mới để phục vụ cho công việc gõ mật khẩu. Mật khẩu là một xâu có độ dài là . Mỗi kí tự của xâu này là một trong kí tự đầu tiên trong bảng chữ cái Latin in thường. Bàn phím thế hệ mới là một hoán vị của chữ cái Latin in thường đầu tiên được xếp theo một hàng ngang từ trái sang phải.
Ví dụ, nếu thì có bàn phím khác nhau là: 𝑎𝑏𝑐, 𝑎𝑐𝑏, 𝑏𝑎𝑐, 𝑏𝑐𝑎, 𝑐𝑎𝑏 và 𝑐𝑏𝑎. Vì Steve chỉ gõ mật khẩu với một ngón tay nên cần thời gian để di chuyển từ một kí tự trong mật khẩu sang kí tự tiếp nối nó. Thời gian Steve dùng để di chuyển từ kí tự sang kí tự bằng với khoảng cách của hai kí tự này trên bàn phím. Thời gian tổng cộng mà Steve cần để
gõ mật khẩu với một bàn phím nhất định thì được gọi là độ chậm của bàn phím đó. Steve muốn mua bàn phím có độ chậm nhỏ nhất.
Định nghĩa cụ thể hơn, độ chậm của một bàn phím thì bằng
Với là vị trí của kí tự trên bàn phím.
Ví dụ, nếu là 𝑎𝑎𝑐𝑎𝑏𝑐 và bàn phím là 𝑏𝑎𝑐, thì tổng thời gian để gõ mật khẩu là:
Yêu cầu: Cho trước xâu kí tự là mật khẩu Steve hay phải gõ, hãy giúp Steve chọn mua bàn phím có độ chậm nhỏ nhất.
Dữ liệu:
Dòng đầu tiên chứa hai số nguyên dương ;
Dòng thứ hai chứa một xâu có kí tự. Mỗi kí tự là một trong chữ cái Latin đầu tiên (in thường).
Kết quả:
Đưa ra một số nguyên là độ chậm nhỏ nhất mà một bàn phím có thể có.
