记录编号	261331	评测结果	AAAAAAAAAA
题目名称	[NOI 2000]算符破译	最终得分	100
用户昵称	lyxin65	是否通过	通过
代码语言	C++	运行时间	5.259 s
提交时间	2016-05-16 21:44:47	内存使用	0.59 MiB

#include <bits/stdc++.h>
 
#define fir first
#define sec second
#define fout stderr
 
const int MAXN = 1005;
 
int n, no = 1;
char e[MAXN][12];
int len[MAXN];
char map[255];
 
void input()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i)
	{
		scanf("%s", e[i] + 1);
		len[i] = strlen(e[i] + 1);
	}
}
 
int OK[255][255];
int equal_pos[MAXN];
 
inline int level(char c)
{
	if(c == '+') return 1;
	else if(c == '*') return 2;
	else return 0;
}
 
long long calc(char *expr, int l, int r)
{
	static char s[12];
	static long long num[12];
	static int op[12];
	int sn = 0, numn = 0, opn = 0;
	for(int i = l; i <= r; ++i)
		s[++sn] = map[(int)expr[i]];
	s[++sn] = '#';
	bool flag = 0;
	num[numn = 1] = 0;
	for(int i = 1; i <= sn; ++i)
	{
		assert(s[sn]);
		if(isdigit(s[i]))
		{
			flag = 1;
			num[numn] = num[numn] * 10 + s[i] - '0';
		}
		else
		{
			if(flag) num[++numn] = 0;
			while(opn && level(s[i]) <= level(op[opn]))
			{
				assert(numn > 2);
				long long a = num[--numn];
				long long b = num[--numn];
				if(op[opn--] == '+')
					num[numn++] = a + b;
				else
					num[numn++] = a * b;
				num[numn] = 0;
			}
			op[++opn] = s[i];
		}
	}
	assert(--numn == 1);
	return num[1];
}

bool check(char *s, int l, int r)
{
	for(int i = l; i <= r; ++i)
		if(map[s[i]] == '0')
			if((i == l || !isdigit(map[s[i - 1]])) && (i != r && isdigit(map[s[i + 1]])))
				return 0;
	return 1;
}

int counter;
int use[255];
int appear[255];

void search_equation(int x, int y)
{
//	fprintf(fout, "now: %d %d\n", x, y);
	if(x == n + 1)
	{
		no = 0;
//		if(map['k'])
//			fprintf(fout, "YES\n");
		for(int i = 'a'; i <= 'm'; ++i)
		{
			if(!map[i]) continue;
			OK[i][map[i]] = 1;
//			if(map['k'])
//				fprintf(fout, "%c %c\n", i, map[i]);
		}
//		if(map['k'])
//			fprintf(fout, "\n");
		return;
	}
	if(y == len[x] + 1)
	{
		if(check(e[x], 1, equal_pos[x] - 1) && check(e[x], equal_pos[x] + 1, len[x]) &&
				calc(e[x], 1, equal_pos[x] - 1) == calc(e[x], equal_pos[x] + 1, len[x]))
			search_equation(x + 1, 1);
		return;
	}
	if(map[e[x][y]])
	{
		search_equation(x, y + 1);
		return;
	}
	for(int t = '0'; t <= '9'; ++t)
	{
		if(!use[t])
		{
			use[map[e[x][y]] = t] = 1;
			search_equation(x, y + 1);
			use[t] = map[e[x][y]] = 0;
		}
	}
}
 
void search_mul()
{
	for(int t = 'a'; t <= 'm'; ++t)
	{
		if(map[t] || !appear[t]) continue;
 
		bool can = 1;
		for(int i = 1; i <= n; ++i)
		{
			if(e[i][1] == t || e[i][len[i]] == t)
			{ can = 0; break; }
			for(int j = 2; j < len[i]; ++j) if(e[i][j] == t)
				if(map[(int)e[i][j + 1]] || map[(int)e[i][j - 1]])
				{ can = 0; break; }
		}
		if(can)
		{
			map[t] = '*';
			search_equation(1, 1);
			map[t] = 0;
		}
	}
	search_equation(1, 1);
}
 
void search_add()
{
	for(int t = 'a'; t <= 'm'; ++t)
	{
		if(map[t] || !appear[t]) continue;
 
		bool can = 1;
		for(int i = 1; i <= n; ++i)
			if(e[i][1] == t
					|| e[i][equal_pos[i] - 1] == t
					|| e[i][equal_pos[i] + 1] == t
					|| e[i][len[i]] == t)
			{ can = 0; break; }
		if(can)
		{
			map[t] = '+';
			search_mul();
			map[t] = 0;
		}
	}
	search_mul();
}
 
void search_equal()
{
	for(int t = 'a'; t <= 'm'; ++t)
	{
		if(!appear[t]) continue;

		bool can = 1;
		for(int i = 1; i <= n; ++i)
		{
			int cnt = 0;
			for(int j = 2; j < len[i]; ++j)
				if(e[i][j] == t)
				{
					cnt++;
					equal_pos[i] = j;
				}
			if(cnt != 1 || e[i][1] == t || e[i][len[i]] == t)
			{
				can = 0;
				break;
			}
		}
		if(can)
		{
			map[t] = '=';
			search_add();
			map[t] = 0;
		}
	}
}
 
int tot, degl[255], degr[255];
std::pair<int, int> out[14];
 
void solve()
{
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= len[i]; ++j)
			appear[e[i][j]] = 1;
	search_equal();
	for(int i = 'a'; i <= 'm'; ++i)
		for(int j = 0; j < 255; ++j)
			if(OK[i][j])
				++degl[i], ++degr[j];
	for(int i = 'a'; i <= 'm'; ++i)
		for(int j = 0; j < 255; ++j)
			if(OK[i][j] && degl[i] == 1)
			{ out[++tot] = std::make_pair(i, j); break; }
	int apt, apcnt = 0, bpt, bpcnt = 0;
	for(int i = 'a'; i <= 'm'; ++i)
		if(!appear[i]) apt = i, apcnt++;
	for(int i = 0; i < 255; ++i)
		if(isdigit(i) || i == '+' || i == '*')
			if(!degr[i])
				bpt = i, bpcnt++;
	if(apcnt == 1 && bpcnt == 1)
		out[++tot] = std::make_pair(apt, bpt);
	sort(out + 1, out + tot + 1);
}
 
void output()
{
	if(no)
		puts("noway");
	else
	{
		for(int i = 1; i <= tot; ++i)
			printf("%c%c\n", out[i].fir, out[i].sec);
	}
}
 
int main()
{
	freopen("equation.in", "r", stdin);
	freopen("equation.out", "w", stdout);
 
	input();
	solve();
	output();
 
	fclose(stdin);
	fclose(stdout);
	return 0;
}