POJ 1248 Safecracker
問題
やりかた
与えられる文字列の長さはせいぜい12文字なので、全探索でも1ケースあたり程度の計算でOKなので全探索で。
ただvectorやstringを引数に関数の値渡しをすると簡単にTLEしてしまった。参照渡しにしたら簡単に通った。
以下ソース。
vector<ll> c(5); ll calc(string &s){ for(int i = 0; i < 5; i++) c[i] = s[i] - 'A' + 1; return c[0] - c[1] * c[1] + c[2] * c[2] * c[2] - c[3] * c[3] * c[3] * c[3] + c[4] * c[4] * c[4] * c[4] * c[4]; } int main(int argc, char **argv){ ll d; string s; while(cin >> d >> s){ if(d == 0 && s == "END") break; sort(ALL(s)); int L = s.length(); string ans("AAAAA"); string str("AAAAA"); for(int S = 0; S < 1 << L; S++){ if(__builtin_popcount(S) != 5) continue; int idx = 0; for(int i = 0; i < L; i++) if(S >> i & 1) str[idx++] = s[i]; do{ if(calc(str) == d) ans = max(ans, str); }while(next_permutation(ALL(str))); } if(ans == "AAAAA") cout << "no solution" << endl; else cout << ans << endl; } return 0; }
Get up! 明日のSUPER ST@R!