Evil Straw Warts Live

From Progteam

Revision as of 21:07, 12 March 2008 by Kerry (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Checkmark.jpg This problem has been solved by kerry.



Evil Straw Warts Live
Problem Number 1854
Sorter: kerry
Source: Unknown
Link: 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;
}
Personal tools