2014年10月5日 星期日

2014/10/05 TopCoder SRM 148 Div1 450 MNS

// http://community.topcoder.com/stat?c=problem_statement&pm=1744&rd=4545
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

int amt[10], _amt[10]; int Ans; int sum; int num[4];

void DFS(int O)
{
    if( O == 4 )
    {
        for(int i = 0; i < 10; i++) _amt[i] = amt[i];

        if( sum-num[0]-num[1] < 0 ) return;
        if( _amt[sum-num[0]-num[1] ] == 0 ) return;
        _amt[sum-num[0]-num[1] ]--;

        if( sum-num[0]-num[2] < 0 ) return;
        if( _amt[sum-num[0]-num[2] ] == 0 ) return;
        _amt[sum-num[0]-num[2] ]--;

        if( sum-num[1]-num[3] < 0 ) return;
        if( _amt[sum-num[1]-num[3] ] == 0 ) return;
        _amt[sum-num[1]-num[3] ]--;

        if( sum-num[2]-num[3] < 0 ) return;
        if( _amt[sum-num[2]-num[3] ] == 0 ) return;
        _amt[sum-num[2]-num[3] ]--;

        Ans++; return;
    }

    for(int i = 0; i < 10; i++)
        if( amt[i] )
        {
            amt[i]--;
            num[O] = i;
            DFS(O+1);
            amt[i]++;
        }
}

struct MNS
{
    int combos(vector <int> n)
    {
        fill(amt, amt+10, 0); Ans = sum = 0;

        for(auto i:n) amt[i]++, sum += i;
        if( sum % 3 ) return 0;
        sum /= 3;

        DFS(0);
        return Ans;
    }
};

沒有留言:

張貼留言