SNAIL 이거 어떻게 푼거져 ㅋㅎ;

  • cjkis
    cjkis

    https://algospot.com/judge/problem/read/SNAIL

    #include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <climits>
    
    using namespace std;
    
    double logN[1001];
    double factN[1001];
    
    double fact(int n)
    {
        if(n == 0)
        {
            return 0;
        }
    
        if(factN[n - 1] != 0)
        {
             factN[n] = logN[n] + factN[n - 1];
        }
        else
        {
            factN[n] = logN[n] + fact(n - 1);
        }
    
        return factN[n];
    }
    
    int main()
    {
        int nCase;
        cin >> nCase;
    
        for(int i = 1; i <= 1000; i++)
        {
            logN[i] = log(i);
        }
    
        double log25 = log(0.25);
        double log3 = log(3);
        while(nCase--)
        {
            int n, m;
            cin >> n >> m;
    
            int d = n - m;
            if(d < 0)
            {
                printf("%.10f\n", 1.);
                continue;
            }
    
            double prSum = 0;
            double factM = fact(m);
    
            for(int i = d; i <= m; i++)
            {
                double t = factM - fact(m - i) - fact(i);
                prSum += exp(t + log3 * i + log25 * m);
            }
    
            printf("%.10f\n", prSum);
        }
        return 0;
    }
    

    이거 가장빨리 푼 답안인데여

    log함수가 자연로그 구하는 함수같은데

    ln3 이랑 ln0.25로 어떻게 답을 구할수있죠?

    그리고 저 fact함수가 뭐하는 함수일까요?


    4년 전
2개의 댓글이 있습니다.
  • nosiar
    nosiar

    factN(n) 은 log(n!) 구하는 거 같고요
    그래서 t 는 log(m!/(m-i)!/i!) 이거구요
    근데 m일 중에서 i일동안 비가 올 확률은
    m!/(m-i)!/i! * 0.75^i * 0.25^(m-i) = m!/(m-i)!/i! * 3^i * 0.25^m
    log 붙이면 t + i*log3 + m*0.25네요
    d일 이상 비가 올 확률을 구한거 같네요


    4년 전 link
  • cjkis
    cjkis

    우앙! 어떻게 알았져? ㄳㄳ


    4년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.