/*The algorithm described at http://boardgamegeek.com/article/2906986#2906986
coded in C by Daniel B. Cristofani, 14 December 2008.
Uses the GMP bignum library, so compile with -lgmp.
Expects a card list via stdin, format "blah abilitycode how-many blah,\n".
You can give it a starting condition via arguments, same format. So if you
want it to assume we've already drawn Alpha Centauri and go from there, type
    $ race 8 1 <summary_abils.txt
or for concision you can type
    $ race 8 <summary_abils.txt
and it will do the same thing. To assume we've drawn 90 cards without seeing
a development power, type
    $ race 47 90 <summary_abils.txt
and of course typing
    $ race <summary_abils.txt
will just start from the beginning, drawing from a complete deck.*/

#include <stdlib.h>
#include <stdio.h>
#include <gmp.h>

int cards[64];      /*for each combo, how many cards have exactly that combo.*/
int a[64][64];      /*a[x][y] = number with all abilities in x and none in y.*/
mpz_t p[64][200];   /*p[s][m] = # of ways to have s after drawing m cards...*/
mpz_t d[200];       /*and d[m] is the denominator to make that a probability.*/
mpq_t t, e;
int k=63, m, n, r, s, x, y, f=-1;
double g;
int initpull, initcombo; /*Card # and abilities stipulated as already drawn.*/

int main(int argc,char **argv){
    while (scanf("%*[^0123456789]%d%d%*[^\n]\n",&x,&y)==2)
        cards[x]+=y,n+=y;
    initpull=argc>2?atoi(argv[2]):argc-1;
    initcombo=argc>1?atoi(argv[1]):0;
    for(s=0;s<=k;s++)
        for(y=0;y<=k;y++)
            if(!(y&s))
                for(x=0;x<=k;x++)
                    if(!(x&~s))
                        a[x][y]+=cards[s];
    for(s=0;s<=k;s++)
        mpz_init(p[s][initpull]);
    mpz_set_si(p[initcombo][initpull],1);
    mpz_init_set_si(d[initpull],1);
    mpq_init(t);
    mpq_init(e);
    mpq_set_si(e,n-initpull,1);
    for(m=initpull;m<n;m++){
        for(s=0;s<=k;s++)
            for(mpz_init(p[s][m+1]),r=0;r<=k;r++)
                if(!(r&~s))
                    mpz_addmul_ui(p[s][m+1],p[r][m],a[s&~r][k&~s]-(s==r?m:0));
        mpz_init(d[m+1]);
        mpz_mul_si(d[m+1],d[m],n-m);
        mpz_set(mpq_numref(t),p[63][m]);
        mpz_set(mpq_denref(t),d[m]);
        mpq_canonicalize(t);
        mpq_sub(e,e,t);
        if (f==-1&&mpq_cmp_si(t,1,2)>=0)
            f=m-initpull, g=mpq_get_d(t)*100;
    }
    printf("The expected number of cards is ");
    mpq_out_str(stdout,10,e);
    printf(", or about %g,\nbut the probability of finishing",mpq_get_d(e));
    printf(" the set within %d card%s is around %g%%.\n",f,f==1?"":"s",g);
    exit(0);
}