2511.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/* This Code is Submitted by wywcgs for Problem 2511 on 2007-06-22 at 16:59:55 */
#include <iostream>
#include <cstring>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

const char DICT[][25] = { "a","am","and","are","at","bailey","be","binary","dislike","do","factoring",
"fishcanfly","hard","hate","hit","hoj","in","is","key","kid","l","large","let","like","linux","love",
"meet","midnight","mostleg","n","neutron","not","of","one","owen","people","pineapple","pknuth","primes",
"product","seeman","sjb","song","that","the","then","there","those","three","two","types","understand",
"we","will","windows","wolfshow","world","ww","wywcgs","xy","zero","zhouguyue","zn","" };
const int L = 1024;

vector<string> vx;
char line[L];
bool can[L];
int len;

bool find(char*);
bool search(int, int);

int main()
{
	vector<string> vw;
	while(scanf("%s", line) != EOF && line[0] != '0') {
		vw.clear();
		int m = -1;
		len = strlen(line);
		for(int i = 0; i < 26; i++) {
			vx.clear();
			memset(can, false, sizeof(can));
			if(!search(0, i)) continue;
			if(m == -1 || (vw.size() > vx.size()))
				{ m = i; vw = vx; }
		}
		if(m == -1) printf("NO SOLUTION");
		else {
			printf("k=%d:", m);
			for(int i = vw.size()-1; i >= 0; i--) printf(" %s", vw[i].c_str());
		}
		printf("\n");
	}
	return 0;
}

bool find(char str[])
{
	for(int i = 0; DICT[i][0] != 0; i++)
		if(!strcmp(DICT[i], str)) return true;
	return false;
}
bool search(int id, int k)
{
	if(can[id]) return false;
	if(id == len) return true;
	can[id] = true;
	char str[L] = "";
	strcpy(str, line+id);
	for(int i = 0; str[i] != 0; i++) str[i] = (str[i]-'a'+26-k)%26+'a';
	for(int i = len-1; i >= id; i--) {
		if(find(str) && search(i+1, k))
			{ vx.push_back(str); return true; }
		str[i-id] = 0;
	}
	return false;
}