読者です 読者をやめる 読者になる 読者になる

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を出し続けた