Giả sử chúng ta được cho một đĩa quay chứa tất cả các chữ cái tiếng Anh viết thường. Có một máy in gắn liền với đĩa quay và bất kỳ ký tự nào nằm ở con trỏ của đĩa quay trong 3 giây sẽ được in ra. Đĩa quay ban đầu ở tại chữ 'a' và nó không quay lại vị trí ban đầu mỗi khi in một ký tự. Chúng ta được cho một chuỗi s và phải in chuỗi đó. Mỗi khi di chuyển đĩa quay sang một chữ cái khác, một lượng quay xảy ra. Chúng ta phải tìm tổng số lượng quay cần thiết để in chuỗi 's' cho trước.
Ví dụ, nếu đầu vào là s = "elephant", thì đầu ra sẽ là 63.
Các bước thực hiện
Để giải quyết bài toán này, chúng ta thực hiện theo các bước sau:
t := 'a' res := 0 for khởi tạo i := 0, khi i < kích thước của s, cập nhật (tăng i lên 1), do: res := res + minimum của (|t - s[i]|, 26 - |t - s[i]|) t := s[i] return res
Ví dụ minh họa
Xem triển khai sau để hiểu rõ hơn:
#include <bits/stdc++.h> using namespace std; #define N 100 int solve(string s) { char t = 'a'; int res = 0; for(int i = 0; i < s.size(); i++){ res += min(abs(t - s[i]), 26 - abs(t - s[i])); t = s[i]; } return res; } int main() { string s = "elephant"; cout<< solve(s); return 0; }Đầu vào
"elephant"
Đầu ra
63