Hacker Cup 2012 round 1 : Checkpoint
問題概要
整数S(<10^7)が与えられる。comb(x+y,y)*comb(a+b,b) = Sとなるようなa,b,x,y(a+b>0, x+y>0)で、x+y+a+bのとりうる最小値を求める問題。
解法
comb(x+y,y)がS以下となる組み合わせは多くないので全列挙する。以下のコードは色々怪しい。
acceptされたコード
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long int64; const int MAX_S = 1e7; const int INF = 1<<29; int S; int brute[MAX_S+1]; int mini[MAX_S+1]; int ans[MAX_S+1]; int64 comb[4000][4000]; const int MAX_SIZE = MAX_S+10; bool isPrime[MAX_SIZE]; void seive(){ memset(isPrime, -1, sizeof(isPrime)); bool *ps = isPrime; ps[0] = ps[1] = false; for(int i=2; i*i<MAX_SIZE; i++)if(ps[i]){ for(int j=i<<1; j<MAX_SIZE; j+=i){ ps[j] = false; } } } void init(){ scanf("%d", &S); } int solve(){ int ans = S+1; for(int i=1; i*i<=S; i++)if(S%i == 0){ int x = (isPrime[i] ? i : mini[i]); int y = (isPrime[S/i] ? S/i : mini[S/i]); ans = min(ans, x+y); } return ans; } void pre(){ seive(); fill(mini, mini+MAX_S+1, INF); for(int i=2; i<=MAX_S; i++){ mini[i] = i; } mini[1] = 1; for(int i=0; i<4000; i++){ comb[i][0] = comb[i][i] = 1; for(int j=1; j<i; j++){ comb[i][j] = comb[i-1][j] + comb[i-1][j-1]; if(comb[i][j] >= INF){ comb[i][j] = INF; } if(comb[i][j] <= MAX_S){ mini[comb[i][j]] = min(mini[comb[i][j]], i); } } } } int main(){ pre(); int T; scanf("%d", &T); for(int c=1; c<=T; c++){ init(); printf("Case #%d: %d\n", c, solve()); } return 0; }