UVa 10149 - Yahtzee

10149.cpp

#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define endl '\n'
#define PB push_back

typedef long long ll;
typedef vector<ll> vll;
typedef pair<double, double> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef pair<int, char> ic;

const int oo = ~(1<<31);
const double EPS = 1e-9;

int vals[13][13];
int throws[13][5];

int f(int i, int val) {
    int a = 0;
    for(int j=0; j<5; j++)
        if(throws[i][j] == val)
            a++;
    return a * val;
}

int chance(int i){
    return accumulate(throws[i], throws[i] + 5, 0);
}

int g(int i, int mn) {
    map<int, int> T;
    for(int j=0; j<5; j++)
        T[throws[i][j]]++;

    for(auto p : T){
        if(p.S >= mn) {
            if(mn == 5) return 50;
            return chance(i);
        }
    }

    return 0;
}

int h(int i, int s, int type) {
    map<int, int> T;
    for(int j=0; j<5; j++)
        T[throws[i][j]]++;

    bool cond;
    int l = s == 4 ? 3 : 2;
    for(int b=1; b<=l; b++) {
        cond = true;
        for(int j=b; j<=s+b-1; j++) {
            if(!T[j]) {
                cond = false;
                break;
            }
        }
        if(cond) break;
    }

    if(cond && type) return 25;
    else if(cond) return 35;

    return 0;
}

int full(int i) {
    map<int, int> T;
    for(int j=0; j<5; j++)
        T[throws[i][j]]++;

    if(T.size() == 2) {
        map<int, int>::iterator it;
        ii p = *(T.begin());
        if(p.S == 2 || p.S == 3)
            return 40;

    }

    return 0;
}

void fill() {

    for(int i=0; i<13; i++) {

        for(int j=1; j<=6; j++)
            vals[i][j - 1] = f(i, j);

        vals[i][6] = chance(i);

        vals[i][7] = g(i, 3);
        vals[i][8] = g(i, 4);
        vals[i][9] = g(i, 5);

        vals[i][10] = h(i, 4, 1);
        vals[i][11] = h(i, 5, 0);

        vals[i][12] = full(i);
    }
}

int sol[13];
int dp[14][1 << 13];

int run(int fu, int mask) {
    if(fu < 0) {
        return 0;
    }

    if(~dp[fu][mask])
        return dp[fu][mask];

    int &r = dp[fu][mask];

    for(int i=0; i<13; i++) {

        if(!(mask & (1 << i))) {
            // The player has not be selected
            r = max(r, run(fu - 1, mask | (1 << i)) + vals[i][fu]);
        }

    }

    if(fu == 5 && r >= 63)
        r += 35;

    return r;
}

void recover(int fu, int mask) {
    if(fu == 0) {
        for(int i=0; i<13; i++) {
            if(!(mask & (1 << i))) {
                sol[fu] = vals[i][fu];
                break;
            }
        }
        return;
    }
    for(int i=0; i<13; i++) {

        if(!(mask & (1 << i))) {

            int expected = dp[fu - 1][mask | (1 << i)]+ vals[i][fu];

            if(fu == 5 && expected >= 63)
                expected += 35;

            if(dp[fu][mask] == expected) {
                recover(fu - 1, mask | (1 << i));
                sol[fu] = vals[i][fu];
                return;
            }

        }


    }
    cout << "Sali y no encotre nada" << endl;
    assert(fu == 5);
    return;
}

int main() {

    #ifndef CBDAVIDES
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
    #endif

    while(cin >> throws[0][0]) {

        memset(dp, -1, sizeof dp);
        memset(sol, -1, sizeof sol);

        for(int i=1; i<5; i++)
            cin >> throws[0][i];

        for(int i=1; i<13; i++) {
            for(int j=0; j<5; j++)
                cin >> throws[i][j];
        }

        fill();

        run(12, 0);
        recover(12, 0);

        for(int i=0; i<13; i++)
            cout << sol[i] << ' ';

        int sum = accumulate(sol, sol + 6, 0);
        sum = sum >= 63 ? 35 : 0;

        cout << sum << ' ' << run(12, 0) << endl;
    }


    return 0;
}