# Evil Straw Warts Live

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
 This problem has been solved by kerry.

 Sorter: kerry Unknown http://acm.pku.edu.cn/JudgeOnline/problem?id=1854

Evil Straw Warts Live is problem number 1854 on the Peking University ACM site.

Nice string problem. Code below, accpeted using PKU C compiler.

- Kerry

```#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int get_input(char[], int *);
long  make_pallindrome(char[], int);
long  swap(char *, char *);

int main() {
int n, length=0;
long count = 0;
char string[8005];  // A little big just for peace of mind.

scanf("%d\n", &n);

while (n) {
if (!get_input(string, &length)) {
printf("Impossible\n");
n--;
}
else {
count = make_pallindrome(string, length);
printf("%ld\n", count);
n--;
}
}
}

int get_input(char string[], int *length) {    // Just negate the entry for each letter to check for an even or odd count for each letter.
char letters[26]={0}, a, tot=0;
int i=0;

while((a=getchar())!='\n') {
letters[a-97] = (!letters[a-97]);
string[i]=a;
i++;
}
*length = i;
for(i=0;i<26;i++)
tot+=letters[i];
if ((tot==1) || (tot==0))    // One letter (and only one) can be odd and still have a pallindrome
return 1;
else
return 0;
}

long make_pallindrome(char string[], int length) {
int  i=0, j, k, sublength=0;
char *substring, *front, *back, *fronttmp, *backtmp;
long count = 0;

front=string;
back=string+(length-1);
sublength=length;

if (length < 2)                                // Make sure we have a string
return 0;

while ((*front == *back) && (i<length/2)) {    // If first and last elements are the same, chop them off
*back = '\0';
back--;
front++;
i++;
}
sublength-=(2*i);                              // Adjust length taking into account chopping above

fronttmp=front;
backtmp=back;

while ((front<back) && sublength>1) {           // Walk pointers from the front and back of the string towards the opposite end. They look for
if(*backtmp==*front) {                  // characters that match the end characters, then swap them via a series of neighbor exchanges.
count+=swap(backtmp, back);
break;
}
else {
if(*fronttmp==*back)  {
count+=swap(fronttmp, front);
break;
}
}
fronttmp++;
backtmp--;
}

i=0;

count+=make_pallindrome(front, sublength);                // Recurse after they reach teh end, amking the front and back equal. Next iteration
return count;                                             // will chop them off and adjust length.
}

long swap(char *middle, char *end) {
char tmp;
long num=0;

if (middle==end)                            //Check for equality (center of sequence means no adjsutment needed). If not equal, swap.
return 0;
while (middle>end) {
tmp = *middle;
*middle=*(middle-1);
*(middle-1) = tmp;
middle--;
num++;
}
while (middle<end) {
tmp = *middle;
*middle=*(middle+1);
*(middle+1) = tmp;
middle++;
num++;
}
return num;
}
```