CodeChef submission 130948 (C++ 4.0.0-8) plaintext list. Status: TLE, problem J5, contest NOV09. By yashwa7 (Yashwant Vijayakumar), 2009-11-11 14:08:34.
#include<cstdio>
#include<string>
#include<iostream>
#include<map>
#include<cstdlib>
#include<ext/hash_map>
 
using namespace std;
 
namespace __gnu_cxx {
	template<> struct hash< std::string > {
		size_t operator()( const std::string& x ) const {
				return hash< const char* >()( x.c_str() );
		}
	};
}
 
#define MANY_TESTCASES
 
__gnu_cxx::hash_map<string, string> magicStringMap;
 
string computeMagicString(string input, bool oddLesser);
string chooseBest(string &first, string &second, string &third);
string chooseBest(string &first, string &second);
 
int main() {
	#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	#endif
	int i = 0;
	int noOfTestCases;
	
	#ifdef MANY_TESTCASES
	scanf("%d", &noOfTestCases);
	#else
	noOfTestCases = 1;
	#endif
	
	while(i < noOfTestCases) {
		char inputString[2000];
		scanf("%s", inputString);
		string input(inputString);
		string output = computeMagicString(input, true);
		printf("%s\n", output.data());
		//magicStringMap.clear();
		i++;
	}
	
	return 0;
}
 
string computeMagicString(string input, bool oddLesser) {
	int length = input.length();
	char oddLesserChar = (oddLesser == true) ? '1' : '0';
	string magicString;
	
	//cout<<input<<endl;
	
	if(length == 1)
		return input;
	
	if(length == 2) {
		if(oddLesser) {
			if(input[0] < input[1])
				magicString = input;
			else
				magicString = string(1, input[1]);
		}
		else {
			if(input[0] > input[1])
				magicString = input;
			else
				magicString = string(1, input[0]);
		}
	}
 
	else {
		__gnu_cxx::hash_map<string, string> :: iterator iter = magicStringMap.begin();
		iter = magicStringMap.find(input + oddLesserChar);
		if(iter != magicStringMap.end()) {
			//cout<<"reuse"<<endl;
			return magicStringMap[input + oddLesserChar];
		}
		
		
		if(oddLesser && (input[0] < input[length - 1]) || !oddLesser && (input[0] > input[length - 1])) {
			string return0 = computeMagicString(input.substr(1, length - 2), !oddLesser);
			string temp = input[0] + return0 + input[length - 1];
			if(temp != input) {
				string return1 = computeMagicString(input.substr(0, length - 1), oddLesser);
				string return2 = computeMagicString(input.substr(1, length - 1), oddLesser);
				magicString = chooseBest(temp, return1, return2);
			}
			else 
				magicString = input;
		}
		
		else {
			string return1 = computeMagicString(input.substr(0, length - 1), oddLesser);
			string return2 = computeMagicString(input.substr(1, length - 1), oddLesser);
			magicString = chooseBest(return1, return2);
		}
	}
	
	magicStringMap[input + oddLesserChar] = magicString;
	
	return magicString;
		
}
 
string chooseBest(string &first, string &second, string &third) {
	string one = chooseBest(first, second);
	return chooseBest(one, third);
}
 
string chooseBest(string &first, string &second) {
	if(first.length() > second.length())
		return first;
	else if(first.length() < second.length())
		return second;
	
	return first < second? first : second;
}