AOJ 2026 Divisor is the Conqueror
問題
(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2026)
N枚のカードがあったそれを一枚ずつ出していく。出せるのは今までに出した、カードの総和の約数だけ。
解法
DFSで解く。普通に解いても無理だった。逆から解くとできるんだって
コード
int c[14], N; bool dfs(int sum, stack<int> st){ if(st.size() == N){ bool f = true; while(!st.empty()){ if(!f) printf(" "); f = false; printf("%d", st.top()); st.pop(); } puts(""); return true; } rep(i, 14){ if(c[i] == 0)continue; if((sum - i) % i != 0)continue; st.push(i); c[i]--; if(dfs(sum-i, st)) return true;; c[i]++; st.pop(); } return false; } int main(){ while(scanf("%d", &N) && N){ memset(c, 0, sizeof(c)); int sum = 0; rep(i, N){ int in; scanf("%d", &in); sum += in; c[in]++; } stack<int>st; if(!dfs(sum, st)) puts("No"); } }
NoをNOとしてWAを出し続けた