Codechef CodeWeavers 2012 The Great Escape

ソースコード

何故通らない。

ll n;
int m, a[20];
map<ll, int> dp;

int rec(ll n){
	if(dp.count(n)) return dp[n];
	
	if(n == 1) return dp[n] = 0;
	
	dp[n] = inf;
	rep(i, m) if(n % a[i] == 0){
		dp[n] = min(dp[n], rec(n / a[i]) + 1);
	}
	
	return dp[n];
}

int main()
{
	while(cin >> n >> m){
		rep(i, m) cin >> a[i];
		
		dp.clear();
		
		int ans = rec(n);
		
		if(ans == inf){
			cout << -1 << endl;
			continue;
		}
		
		cout << ans << endl;
		
		ll cur = 1;
		cout << 1;
		
		rep(it, ans){
			ll next = n + 1;
			rep(j, m) if(dp[cur * a[j]] == dp[cur] + 1) next = min(next, cur * a[j]);
			
			cout << " " << next;
			cur = next;
		}
		cout << endl;
	}
	return 0;
}