LightOJ1364---Expected Cards(확률 dp+3진수형)

Taha has got a standard deck of cards with him. In addition to the 52 regular ones, there are 2 joker cards. Every regular card has a rank and a suit. The ranks in ascending order are: A, 2, 3, 4, 5, 6, 7, 8, 9, T, J, Q and K. The suit of a card can be clubs, diamonds, hearts or spades. That means there are 13 clubs, 13 diamonds, 13 hearts and 13 spades - which adds up to 52. The joker cards have no ranks or suits.
One day, Sara gave Taha a challenge. First she randomly shuffles the 54 cards and starts placing one card after another, face-up, on a table. What is the expected number of cards Sara has to place so that there are at least C clubs, D diamonds, H hearts and S spades on the table? Whenever a joker card is encountered, Taha has to assign it to some suit so that the expected number of cards to reach the goal is minimized. The decision of assigning the joker card to some suit has to be made instantly (i.e. before Sara puts the next card on the table). Note that the assignments of the two joker cards don’t necessarily need to be the same. Input
Input starts with an integer T (≤ 10), denoting the number of test cases.
Each case starts with a line containing four integers in the order C, D, H and S. Each of these integers will be in the range [0, 15]. Output
For each case, print the case number first. Then output the expected number of cards Sara needs to place on the table to achieve the goal. If it’s impossible to reach the goal, irrespective of what assignments Sara opts for, output ‘-1’ (without the quotes) instead. Errors less than 10-6 will be ignored. Sample Input
Output for Sample Input
4
0 0 0 0
15 13 13 13
1 2 3 4
15 15 15 15
Case 1: 0
Case 2: 54
Case 3: 16.3928186102
Case 4: -1 Notes

For case 1, there is no need to place any card as all required values are 0

For case 2, we must place all the 54 cards to reach the goal

For case 3, note that output isn’t always an integer

For case 4, 60 Cards? No way!! dp[i][j][k][l][m]는 현재 i장 클럽스, j장 다이아몬드, k장 하트, l장 spades,jokers의 사용 상태가 m(3진법 표시)일 때 카드 수의 기대치

가 필요하다고 표시한다

/************************************************************************* > File Name: O.cpp > Author: ALex > Mail: [email protected] > Created Time: 2015 05 17      16 47 15  ************************************************************************/

#include <functional>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <map>
#include <bitset>
#include <set>
#include <vector>

using namespace std;

const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const double eps = 1e-15;
typedef long long LL;
typedef pair <int, int> PLL;

double dp[16][16][16][16][82];
int C, D, H, S;
int bit[6];

bool judge(int a, int b, int c, int d, int e) {
    bit[0] = bit[1] = bit[2] = bit[3] = 0;
    int cnt = 0;
    while (e) {
        bit[cnt++] = e % 3;
        e /= 3;
    }
    a += bit[0];
    b += bit[1];
    c += bit[2];
    d += bit[3];
    if (a >= C && b >= D && c >= H && d >= S) {
        return 1;
    }
    return 0;
}

double dfs(int x, int y, int z, int w, int v) {
    double &res = dp[x][y][z][w][v];
    if (res != -1.0) {
        return res;
    }
    if (judge(x, y, z, w, v)) {
        return res = 0;
    }
    int e = v;
    res = 0;
    int num = 0;
    int cnt = 0;
    int bit[4];
    bit[0] = bit[1] = bit[2] = bit[3] = 0;
    bit[0] = v % 3; v /= 3; num += bit[0];
    bit[1] = v % 3; v /= 3; num += bit[1];
    bit[2] = v % 3; v /= 3; num += bit[2];
    bit[3] = v % 3; v /= 3; num += bit[3];
    int all = 54 - x - y - z - w - num;
    if (x < 13 && all) {
        double p = (13 - x) * 1.0 / all;
        res += (dfs(x + 1, y, z, w, e) + 1) * p;
    }
    if (y < 13 && all) {
        double p = (13 - y) * 1.0 / all;
        res += (dfs(x, y + 1, z, w, e) + 1) * p;
    }
    if (z < 13 && all) {
        double p = (13 - z) * 1.0 / all;
        res += (dfs(x, y, z + 1, w, e) + 1) * p;
    }
    if (w < 13 && all) {
        double p = (13 - w) * 1.0 / all;
        res += (dfs(x, y, z, w + 1, e) + 1) * p;
    }
    if (num < 2 && all) {
        double p = (2 - num) * 1.0 / all;
        v = (bit[0] + 1) + bit[1] * 3 + bit[2] * 9 + bit[3] * 27;
        double choice = dfs(x, y, z, w, v);
        v = bit[0] + (bit[1] + 1) * 3 + bit[2] * 9 + bit[3] * 27;
        choice = min(choice, dfs(x, y, z, w, v));
        v = bit[0] + bit[1] * 3 + (bit[2] + 1) * 9 + bit[3] * 27;
        choice = min(choice, dfs(x, y, z, w, v));
        v = bit[0] + bit[1] * 3 + bit[2] * 9 + (bit[3] + 1) * 27;
        choice = min(choice, dfs(x, y, z, w, v));
        res += (choice + 1) * p;
    }
    return res;
}

int main() {
    int t, icase = 1;
    scanf("%d", &t);
    while (t--) {
        for (int i = 0; i <= 15; ++i) {
            for (int j = 0; j <= 15; ++j) {
                for (int k = 0; k <= 15; ++k) {
                    for (int l = 0; l <= 15; ++l) {
                        for (int p = 0; p <= 81; ++p) {
                            dp[i][j][k][l][p] = -1.0;       
                        }
                    }
                }
            }
        }
        scanf("%d%d%d%d", &C, &D, &H, &S);
        int cnt = 0;
        cnt += (C - 13 > 0 ? C - 13 : 0);
        cnt += (D - 13 > 0 ? D - 13 : 0);
        cnt += (H - 13 > 0 ? H - 13 : 0);
        cnt += (S - 13 > 0 ? S - 13 : 0);
        if (cnt > 2) {
            printf("Case %d: -1
", icase++);
            continue;
        }
        double res = dfs(0, 0, 0, 0, 0);
        printf("Case %d: %.12f
", icase++, res);
    }
    return 0;
}