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