Bài tập trên HackerRank: The Love-Letter Mystery

#1

Problem Statement

James found a love letter his friend Harry has written for his girlfriend. James is a prankster, so he decides to meddle with the letter. He changes all the words in the letter into palindromes.

To do this, he follows 2 rules:

(a) He can reduce the value of a letter, e.g. he can change ‘d’ to ‘c’, but he cannot change ‘c’ to ‘d’.
(b) In order to form a palindrome, if he has to repeatedly reduce the value of a letter, he can do it until the letter becomes ‘a’. Once a letter has been changed to ‘a’, it can no longer be changed.

Each reduction in the value of any letter is counted as a single operation. Find the minimum number of operations required to convert a given string into a palindrome.

Input Format
The first line contains an integer T, i.e., the number of test cases.
The next T lines will contain a string each. The strings do not contain any spaces.

Output Format
A single line containing the number of minimum operations corresponding to each test case.

Sample:
INPUT
abc
abcba
abcd
cba
OUTPUT
2
0
4
2
update
Explanation

For the first test case, abc -> abb -> aba.
For the second test case, abcba is already palindromic string.
For the third test case, abcd -> abcc -> abcb -> abca = abca -> abba.
For the fourth test case, cba -> bba -> aba.

1 Like
#2

Bài này chỉ cần lấy tổng giá trị của chênh lệch 2 đầu chuỗi là dc.


import sys

def solve(s):
    t=map(ord,s)
    n=len(t)
    ret=0
    for i in range(n//2):
        ret+=abs(t[i]-t[-i-1])
    return ret

for line in sys.stdin.readlines():
    line=line.strip()
    if len(line):
        print solve(line)
1 Like
#3

@Gio bài này không phải lấy giá trị trênh lệch 2 đầu chuỗi vì Input abc Output là 2 nhưng Input abcd Output là 4 ker.

#4

abc -> aba thì chỉ cần giảm c -> a nên đáp án là 2
abcd -> abba thì c -> b và d->a nên đáp án là 1+3=4

Vì thế khi trừ giá trị mã ascii 2 đầu thì được 1 biến đổi nhỏ nhất thành xâu đối xứng.

#5

tại sao abcba không đổi c-> a.

#6

Vì ở giữa rồi. Không cần biến đổi nữa :smiley:

#7

abcd thì c cũng ở giữa mà

#8

À ý của mình là chính giữa ấy tức là khi n=2k+1 thì vị trí giữa là k+1 không cần biến đổi

1 Like
#9

bác cho em hỏi như theo đề thì Input vào của đề là:
3
aaaa
baada
cccc
vậy làm như thế nào để đọc được dữ liệu vào đề xử lý. Thấy bác dùng python xử lý hơi lạ, bác có thể
giải thích được không. Mà nếu dùng c thì có cách nào không.

#10

Vì đề của bạn trên không cho n. Nên mình dùng stdin.readlines() sẽ đọc tất cả các dòng. Cái line.strip() là loại bỏ kí tự trắng( newline,space …). Khi mà line là xâu rỗng thì không xử lí nữa.
Trong c thì bạn có thể dùng
while(scanf("%s",str)!=EOF) để đọc tất cả dữ liệu.
Nếu có n thì đọc đúng n lần thôi :smile:

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?