Submission #323772


Source Code Expand

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int BUF = 105;

int N;

void read() {
    cin >> N;
}


int calcNumWinner(int nG, int nC, int nP) {
    // 出された手が一種類
    if (nG == 0 && nC == 0) return nP;
    if (nG == 0 && nP == 0) return nC;
    if (nC == 0 && nP == 0) return nG;
    
    // 出された手が一種類以上
    int minHand = 1<<30;
    if (nG) minHand = min(nG, minHand);
    if (nC) minHand = min(nC, minHand);
    if (nP) minHand = min(nP, minHand);
    
    // 出された手が最も少ないものの数
    int nMinHand = 0;
    if (nG == minHand) ++nMinHand;
    if (nC == minHand) ++nMinHand;
    if (nP == minHand) ++nMinHand;
    
    if (nMinHand == 1 || nMinHand == 2) {
        return minHand;
    }
    else {
        return nG + nC + nP;
    }
}


double comb(int a, int b, int c) {
    double ret = 1;
    for (int i = 1; i <= a + b + c; ++i) ret *= i;
    for (int i = 1; i <= a; ++i) ret /= i;
    for (int i = 1; i <= b; ++i) ret /= i;
    for (int i = 1; i <= c; ++i) ret /= i;
    return ret;
}


double rec(int n, double dp[BUF]) {
    if (n == 1) return 0;
    double &ret = dp[n];
    if (ret > -0.5) return ret;
    
    double sum = 0;
    double cntN = 0;
    double cntTotal = 0;
    for (int nG = 0; nG <= n; ++nG)
        for (int nC = 0; nC + nG <= n; ++nC) {
            int numWinner = calcNumWinner(nG, nC, n - nG - nC);
            double nComb = comb(nG, nC, n - nG - nC);
            if (numWinner == n)
                cntN += nComb;
            else {
                sum += nComb * rec(numWinner, dp);
            }
            cntTotal += nComb;
        }
    
    return ret = (sum  + cntTotal) / (cntTotal - cntN);
}


void work() {
    double dp[BUF];
    for (int i = 0; i < BUF; ++i) dp[i] = -1;
    printf("%.10lf\n", rec(N, dp));
}


int main() {
    read();
    work();
    return 0;
}

Submission Info

Submission Time
Task C - ゲーマーじゃんけん
User Hachimori
Language C++ (G++ 4.6.4)
Score 100
Code Size 1996 Byte
Status AC
Exec Time 43 ms
Memory 924 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 99
Set Name Test Cases
All input-002.txt, input-003.txt, input-004.txt, input-005.txt, input-006.txt, input-007.txt, input-008.txt, input-009.txt, input-010.txt, input-011.txt, input-012.txt, input-013.txt, input-014.txt, input-015.txt, input-016.txt, input-017.txt, input-018.txt, input-019.txt, input-020.txt, input-021.txt, input-022.txt, input-023.txt, input-024.txt, input-025.txt, input-026.txt, input-027.txt, input-028.txt, input-029.txt, input-030.txt, input-031.txt, input-032.txt, input-033.txt, input-034.txt, input-035.txt, input-036.txt, input-037.txt, input-038.txt, input-039.txt, input-040.txt, input-041.txt, input-042.txt, input-043.txt, input-044.txt, input-045.txt, input-046.txt, input-047.txt, input-048.txt, input-049.txt, input-050.txt, input-051.txt, input-052.txt, input-053.txt, input-054.txt, input-055.txt, input-056.txt, input-057.txt, input-058.txt, input-059.txt, input-060.txt, input-061.txt, input-062.txt, input-063.txt, input-064.txt, input-065.txt, input-066.txt, input-067.txt, input-068.txt, input-069.txt, input-070.txt, input-071.txt, input-072.txt, input-073.txt, input-074.txt, input-075.txt, input-076.txt, input-077.txt, input-078.txt, input-079.txt, input-080.txt, input-081.txt, input-082.txt, input-083.txt, input-084.txt, input-085.txt, input-086.txt, input-087.txt, input-088.txt, input-089.txt, input-090.txt, input-091.txt, input-092.txt, input-093.txt, input-094.txt, input-095.txt, input-096.txt, input-097.txt, input-098.txt, input-099.txt, input-100.txt
Case Name Status Exec Time Memory
input-002.txt AC 27 ms 672 KB
input-003.txt AC 23 ms 800 KB
input-004.txt AC 24 ms 668 KB
input-005.txt AC 22 ms 672 KB
input-006.txt AC 25 ms 796 KB
input-007.txt AC 23 ms 804 KB
input-008.txt AC 26 ms 924 KB
input-009.txt AC 24 ms 804 KB
input-010.txt AC 29 ms 732 KB
input-011.txt AC 26 ms 672 KB
input-012.txt AC 26 ms 924 KB
input-013.txt AC 25 ms 672 KB
input-014.txt AC 28 ms 800 KB
input-015.txt AC 25 ms 924 KB
input-016.txt AC 26 ms 800 KB
input-017.txt AC 24 ms 796 KB
input-018.txt AC 24 ms 916 KB
input-019.txt AC 24 ms 668 KB
input-020.txt AC 24 ms 676 KB
input-021.txt AC 24 ms 672 KB
input-022.txt AC 26 ms 800 KB
input-023.txt AC 26 ms 672 KB
input-024.txt AC 25 ms 796 KB
input-025.txt AC 24 ms 800 KB
input-026.txt AC 24 ms 800 KB
input-027.txt AC 26 ms 796 KB
input-028.txt AC 25 ms 796 KB
input-029.txt AC 26 ms 804 KB
input-030.txt AC 26 ms 800 KB
input-031.txt AC 26 ms 800 KB
input-032.txt AC 26 ms 800 KB
input-033.txt AC 26 ms 796 KB
input-034.txt AC 24 ms 796 KB
input-035.txt AC 25 ms 792 KB
input-036.txt AC 26 ms 800 KB
input-037.txt AC 26 ms 668 KB
input-038.txt AC 27 ms 716 KB
input-039.txt AC 25 ms 796 KB
input-040.txt AC 26 ms 672 KB
input-041.txt AC 26 ms 800 KB
input-042.txt AC 27 ms 796 KB
input-043.txt AC 25 ms 668 KB
input-044.txt AC 26 ms 764 KB
input-045.txt AC 27 ms 800 KB
input-046.txt AC 26 ms 924 KB
input-047.txt AC 27 ms 800 KB
input-048.txt AC 27 ms 800 KB
input-049.txt AC 27 ms 800 KB
input-050.txt AC 27 ms 672 KB
input-051.txt AC 27 ms 796 KB
input-052.txt AC 26 ms 672 KB
input-053.txt AC 27 ms 804 KB
input-054.txt AC 27 ms 800 KB
input-055.txt AC 26 ms 800 KB
input-056.txt AC 25 ms 804 KB
input-057.txt AC 25 ms 676 KB
input-058.txt AC 27 ms 800 KB
input-059.txt AC 26 ms 796 KB
input-060.txt AC 27 ms 800 KB
input-061.txt AC 27 ms 924 KB
input-062.txt AC 27 ms 800 KB
input-063.txt AC 27 ms 796 KB
input-064.txt AC 28 ms 676 KB
input-065.txt AC 28 ms 800 KB
input-066.txt AC 29 ms 800 KB
input-067.txt AC 26 ms 672 KB
input-068.txt AC 28 ms 672 KB
input-069.txt AC 31 ms 800 KB
input-070.txt AC 31 ms 672 KB
input-071.txt AC 31 ms 672 KB
input-072.txt AC 31 ms 672 KB
input-073.txt AC 31 ms 672 KB
input-074.txt AC 32 ms 804 KB
input-075.txt AC 31 ms 796 KB
input-076.txt AC 31 ms 800 KB
input-077.txt AC 31 ms 796 KB
input-078.txt AC 33 ms 800 KB
input-079.txt AC 33 ms 800 KB
input-080.txt AC 34 ms 796 KB
input-081.txt AC 34 ms 800 KB
input-082.txt AC 34 ms 796 KB
input-083.txt AC 35 ms 804 KB
input-084.txt AC 36 ms 792 KB
input-085.txt AC 36 ms 792 KB
input-086.txt AC 36 ms 800 KB
input-087.txt AC 40 ms 800 KB
input-088.txt AC 36 ms 796 KB
input-089.txt AC 38 ms 800 KB
input-090.txt AC 38 ms 800 KB
input-091.txt AC 39 ms 800 KB
input-092.txt AC 39 ms 720 KB
input-093.txt AC 40 ms 672 KB
input-094.txt AC 40 ms 672 KB
input-095.txt AC 41 ms 680 KB
input-096.txt AC 42 ms 672 KB
input-097.txt AC 41 ms 796 KB
input-098.txt AC 40 ms 800 KB
input-099.txt AC 41 ms 792 KB
input-100.txt AC 43 ms 804 KB