Search This Blog

Saturday, 16 May 2015

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 two rules:
  1. He can reduce the value of a letter, e.g. he can change d to c, but he cannot change c to d.
  2. 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.
Constraints
1T10
1 length of string 104
All characters are lower case English letters.
Output Format
A single line containing the number of minimum operations corresponding to each test case.
Sample Input
4
abc
abcba
abcd
cba
Sample Output
2
0
4
2
Explanation
  1. For the first test case, abc -> abb -> aba.
  2. For the second test case, abcba is already a palindromic string.
  3. For the third test case, abcd -> abcc -> abcb -> abca = abca -> abba.
  4. For the fourth test case, cba -> bba -> aba.




My code for this program is :


#include<iostream>
#include<cmath>
using namespace std;
int main()
{
string st;
float t,c;
int result=0,i,a,d,e,f;
cin>>t;
while(t--)
{ result=0;
cin>>st;
a=st.size();

if(a%2!=0)
{ c=floor(a/2);
for(i=0;i<=c;i++)
{
if(st[c-i]>=st[c+i])
{
result=result+(st[c-i]-st[c+i]);
}
if(st[c+i]>st[c-i])
{
result=result+(st[c+i]-st[c-i]);
}

}
      }
   
if(a%2==0)
      {    d=a/2; e=d-1; f=e+1;
           for(i=0;i<d;i++)
             {
                  if(st[e-i]>=st[f+i])
             {
                result=result+(st[e-i]-st[f+i]);
        }
          if(st[e-i]<st[f+i])
        {
          result=result+(st[f+i]-st[e-i]);
        }
      }
  }
       cout<<result<<endl;
   }
return 0;
}

No comments:

Post a Comment