Problem 2026 : Divisor is the Conqueror

Problem D: Divisor is the Conqueror
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2026

• 問題概要

カードが５２枚以下、１３までの数がかいてある。
カードを全部取れればそのとり方、取れなければNoをだせ。

取るルールは
１　最初はなんでも取っていい。
２　次からは、今までとったカードの合計を割ることのできるカードのみ取ってよい。

• 解法

DFS。
ただし、状態がすんごいおおい(52!/(13!*4）くらい？）ので普通にやると終わらない。
逆からやると終わる。
多分候補が少なくなるから？
多分そうだと思うけど、証明できない。
でも逆からやると終わります。

• ソース

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<sstream>
#include<cassert>
#include<queue>
#include<stack>

#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define ALL(C)     (C).begin(),(C).end()
#define pb         push_back
#define mp         make_pair
#define vint       vector<int>
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)
#define lli	    long long int
#define ld	    long double

using namespace std;

int c[14],  n;
bool end;

void saiki(int sum, stack<int> st){
  if(st.size() == n){
    end = true;
    bool first = true;
    while(!st.empty()){
      if(!first)cout << ' ';
      first = false;
      cout << st.top();
      st.pop();
    }
    cout << endl;
    return;
  }
  rep(i, 14){
    if(c[i] == 0)continue;
    if((sum - i) % i != 0)continue;
    st.push(i);
    c[i]--;
    saiki(sum-i, st);
    if(end)return;
    c[i]++;
    st.pop();
  }
}


main(){
  while(cin >> n){
    if(n == 0)break;
    rep(i, 14){
      c[i] = 0;
    }
    int sum = 0;
    rep(i, n){
      int tmp;
      cin >> tmp;
      sum += tmp;
      c[tmp]++;
    }
    end = false;
    rep(i, 14){
      if(c[i] == 0)continue;
      if((sum - i) % i != 0)continue;
      c[i]--;
      stack<int> st;
      st.push(i);
      saiki(sum-i, st);
      if(end)break;
      c[i]++;
    }
    if(!end)cout << "No" << endl;
  }
}