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; }