UCF Local Programming Contest 2014 J. Factorial Products

 J. Factorial Products

思路:根据对数性质:log(a*b) = log(a) + log(b),使得阶乘相乘转变为前缀和累加,处理了数据过大无法存储的问题。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

const double eps = 1e-7;
const int N = 2600;
double pre[N];

void init(){
    for(int i = 2; i <= 2560; ++i) 
        pre[i] = pre[i - 1] + (log(i*1.0));
}

void solve(){
    init();
    
    int T;
    scanf("%d", &T);
    for(int t = 1; t <= T; ++t){
        int a, b, c, x;
        double aa = 0, bb = 0, cc = 0;
        scanf("%d%d%d", &a, &b, &c);
        for(int i = 1; i <= a; ++i){
            scanf("%d", &x);
            aa += pre[x];
        }
        for(int i = 1; i <= b; ++i){
            scanf("%d", &x);
            bb += pre[x];
        }
        for(int i = 1; i <= c; ++i){
            scanf("%d", &x);
            cc += pre[x];
        }
        printf("Case #%d: ", t);
        if(fabs(aa - bb) <= eps && fabs(aa - cc) <= eps && fabs(cc - bb) <= eps){
            printf("TIE\n");
        }
        else if(fabs(aa - bb) <= eps){
            if(cc - aa > 0) printf("C\n");
            else printf("TIE\n");
        }else if(fabs(aa - cc) <= eps){
            if(bb - aa > 0) printf("B\n");
            else printf("TIE\n");
        }else if(fabs(bb - cc) <= eps){
            if(aa - bb > 0) printf("A\n");
            else printf("TIE\n");
        }else{
            if(aa - bb > 0 && aa - cc > 0) printf("A\n");
            else if(bb - aa > 0 && bb - cc > 0) printf("B\n");
            else if(cc - aa > 0 && cc - bb > 0) printf("C\n");
        }
    }
}

int main(){
    
    solve();    
    
    return 0;
}

 

上一篇:结构化程序设计(structured programming)


下一篇:Java06面向对象02