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