UVa 1268 Clues

問題

ある素数k0を次のように分解する。
数の（要素の重複を許す）集合をCとする。
rを決める。
Cにrを入れる。
k0以下のr-1個の素数k1, k2, ..., kr-1を決める。
kiに対して、kiをそのままCに入れるか、ki = a0 + a1 + … + am（ただしaは任意の自然数列）
に分解して、全てのaをCに入れる。

こうして出来たCを、要素が小さい順に並べる。
逆にCが与えられたとき、k0の最大値を求めよ。
そのようなk0が存在しないときはnot a valid clueを出力せよ。

制約条件

n≦14
c[i]≦10000

方針

再帰で探索 + 自明な枝刈りで通る。

ソースコード

const int MX = 200000;
int n, m, c[20], sum[20], ans;
bool p[MX];

void rec(int bit, int cur){
	if(cur == m - 1){
		rep(i, n) if(bit & 1 << i) sum[cur] += c[i];
		if(!p[sum[cur]] && (cur == 0 || sum[cur] <= sum[cur - 1]))
			ans = max(ans, sum[0]);
		sum[cur] = 0;
		return;
	}
	if(__builtin_popcount(bit) < m - cur) return;
	for(int i = bit; i; i = (i - 1) & bit){
		rep(j, n) if(i & 1 << j){
			if(j && c[j] == c[j-1] && (bit & 1 << (j - 1)) && !(i & 1 << (j - 1))) goto NEXT;
			sum[cur] += c[j];
		}
		if(!p[sum[cur]] && (cur == 0 || sum[cur] <= sum[cur - 1]))
			rec(bit - i, cur + 1);
		NEXT:
		sum[cur] = 0;
	}
}

int main(){
	p[0] = p[1] = 1;
	for(int i = 2; i * i < MX; i++) if(!p[i])
		for(int j = i * i; j < MX; j += i) p[j] = 1;
	int cs = 0;
	while(cin >> n, ~n){
		rep(i, n) cin >> c[i];
		sort(c, c + n);
		ans = -1;
		rep(i, n) if(c[i] < n){
			m = c[i];
			if(i && c[i] == c[i - 1]) continue;
			rec((1 << n) - 1 - (1 << i), 0);
		}
		printf("Case %d: ", ++cs);
		if(ans < 0) puts("not a valid clue");
		else printf("%d\n", ans);
	}
	return 0;
}