30/09/2018, 16:33

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

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.

Gió viết 18:37 ngày 30/09/2018

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)

Hung Nguyen Minh viết 18:43 ngày 30/09/2018

@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.

Gió viết 18:46 ngày 30/09/2018

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.

Hung Nguyen Minh viết 18:42 ngày 30/09/2018

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

Gió viết 18:46 ngày 30/09/2018

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

Hung Nguyen Minh viết 18:43 ngày 30/09/2018

Vì ở giữa rồi

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

Gió viết 18:34 ngày 30/09/2018

À ý 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

kongdap viết 18:47 ngày 30/09/2018

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.

Gió viết 18:41 ngày 30/09/2018

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

Bình luận về bài viết này

Chia sẻ tin đăng đến bạn bè

Gửi Messenger

Bài liên quan

Hung Nguyen Minh

0 chủ đề

0 bài viết

Tác giả nổi bật