The 2011 Southwestern Europe Regional Contest F, UVa-12392 : Guess the Numbers

問題概要

変数をN(<=5)個含む数式が与えられる。5つの変数の値をばらばらにした数列が与えられるので、式を評価してMに等しくなる組み合わせがあるかどうか判定する問題。

考えたこと

• 変数が5つしかないんだから5!全部試せばいい。
• 構文解析の部分は2項演算子が括弧でまとまっているので易しい。
• := '(' ')' | 、 := | op

とか？

• 書く。動かない。このBNF間違ってるじゃん。
• := '(' ')' | | op が正しい。
• 書き直したら無事とおった。やっぱりどんなに簡単そうでもちゃんとBNF書くのは大事。

本番で通ったコード

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
using namespace std;

const int MAX_N = 5;

int N, M;
int vs[MAX_N];
bool used_char[0x100];
int val[0x100];
int p, L;
char line[100001];

void init(){
	for(int i=0; i<N; i++){
		scanf("%d", vs + i);
	}
	scanf("%d ", &M);
	scanf("%[^\n]%*c", line);
	memset(used_char, false, sizeof(used_char));
}

int expr(){
	int ret = 0;
	if(line[p] == '('){
		p++;
		ret = expr();
		p++;
	}
	else if( isalpha(line[p]) ){
		ret = val[line[p++]];
	}


	char op = line[p];
	if(op == '+' || op == '-' || op == '*'){
		p++;
		int b = expr();
		if(op == '+'){
			return ret + b;
		}
		else if(op == '-'){
			return ret - b;
		}
		else{
			return ret * b;
		}
	}

	return ret;
}

bool sub(){
	p = 0;
	for(char c='a'; c<='z'; c++){
		if(used_char[c]){
			val[c] = vs[p++];
		}
	}
	p = 0;

	int e = expr();
	return e == M;
}

bool solve(){
	L = strlen(line);
	sort(vs, vs+N);
	for(int i=0; i<L; i++){
		if(isalpha(line[i])){
			used_char[line[i]] = true;
		}
	}

	do{
		if(sub()){
			return true;
		}
	}while(next_permutation(vs, vs+N));

	return false;
}

int main(){
	while(scanf("%d", &N), N){
		init();
		puts(solve() ? "YES": "NO");
	}

	return 0;
}