PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author:
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
You’re given a string S of length 8.
In one move, you can change any character to the next one inn the (cyclic) alphabet.
Find the minimum number of moves needed to make S equal "ADVITIYA".
EXPLANATION:
Note that each position is completely independent.
So, we only need to find the number of moves needed to make the first character 'A', the second character 'D', and so on.
This can be done by simply simulating the process: repeatedly perform the operation on the first character till it reaches 'A', then do the same to the second character, then the third, and so on.
Each index needs at most 25 operations to reach its goal so this will be fast enough.
It’s also possible (but not needed) to solve the problem using math, by looking at the difference in indices (in the alphabet) between the current and target characters.
TIME COMPLEXITY:
\mathcal{O}(1) per testcase.
CODE:
Editorialist's code (PyPy3)
def next_char(c):
if c == 'Z': return 'A'
else: return chr(ord(c) + 1)
for _ in range(int(input())):
s = list(input())
target = 'ADVITIYA'
ans = 0
for i in range(8):
while s[i] != target[i]:
ans += 1
s[i] = next_char(s[i])
print(ans)