首页 > ACM题库 > HDU-杭电 > HDU 4459-Homework[解题报告]HOJ
2015
07-16

HDU 4459-Homework[解题报告]HOJ

Homework

问题描述 :

XXX always procrastinate over his homework. This time, he is wondering that if he can finish all his projects before deadline. There are n (2<=n<=5) projects to do. Each projects has a deadline d (1<=d<=1000) which means that this project must be finished no later than d o’clock.
For each project, there is an interval [s1, s2] (1<=s1<=s2<=200) meaning that XXX will spend at least s1 hours and at most s2 hours to finish it.
Let random variable t denotes that it takes t hours to finish the project. (Note that t may take real values).
If s1<s2, variable t obeys a continuous uniform distribution. Its probability density function is:

Shoot the Airplane

If s1=s2, variable t takes constant value s1.
In probability theory, a probability density function (pdf), or density of a continuous random variable, is a function that describes the relative likelihood for this random variable to take on a given value. The probability for the random variable to fall within a particular region is given by the integral of this variable’s density over the region. The probability density function is nonnegative everywhere, and its integral over the entire space is equal to one.
XXX cannot engage in different projects at the same time. He wants to arrange the order of his projects to be done properly, so that the probability that all projects are finished before or just meet the deadline is maximized.

输入:

There are no more than 3000 cases.
For each case, the first line begins with an integer n — the number of projects.
Each of the following n lines describes one project which contains three integers — the above mentioned s1, s2 and d.
The input ends by n=0.

输出:

There are no more than 3000 cases.
For each case, the first line begins with an integer n — the number of projects.
Each of the following n lines describes one project which contains three integers — the above mentioned s1, s2 and d.
The input ends by n=0.

样例输入:

2
1 1 3
1 3 3
2
1 1 3
2 2 2
0

样例输出:

1/2
Congratulations!

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
struct fac
{
    LL fz,fm;
    fac(){}
    fac (LL a,LL b):fz(a),fm(b) {}
    fac fix()
    {
        LL d=__gcd(fz,fm);
        return fac(fz/d,fm/d);
    }
    fac operator + (const fac & b) const { return fac(fz*b.fm+fm*b.fz,fm*b.fm).fix(); }
    fac operator * (const fac & b) const { return fac(fz*b.fz,fm*b.fm).fix(); }
    fac operator / (const fac & b) const { return fac(fz*b.fm,fm*b.fz).fix(); }
    fac operator - (const fac & b) const { return fac(fz*b.fm-fm*b.fz,fm*b.fm).fix() ;}
};
struct node
{
    fac xs;
    int d[5],x[5];
    node () { 
        xs=fac(1,1);
        for(int i=0;i<5;i++) { d[i]=x[i]=0;}
    }
    node operator * (const node & b) const {
        node ans;
        ans.xs=xs*b.xs;
        for(int i=0;i<5;i++) {
            ans.d[i]=d[i]+b.d[i];
            ans.x[i]=x[i]+b.x[i];
        }
        return ans;
    }
    bool operator < (const node & b) const
    {
        for(int i=0;i<5;i++) {
            if(d[i]!=b.d[i]) return d[i]<b.d[i];
        }
        return 0;
    }
    bool operator == (const node & b)
    {
        for(int i=0;i<5;i++) if(d[i]!=b.d[i]) return false;
        return true;
    }
    void output()
    {
        cout << xs.fz << "/" << xs.fm << " ";
        for(int i=0;i<5;i++){
            cout << d[i] << " ";
        }
        for(int i=0;i<5;i++){
            cout << x[i] << " ";
        }
        cout << endl;
    }
};
vector <node> dep[10],ans;
vector <node> v_mult(vector <node> & a,vector <node> & b)
{
    vector<node> ans;
    int s1=a.size(),s2=b.size();
    for(int i=0;i<s1;i++){
        for(int j=0;j<s2;j++){
            ans.push_back(a[i]*b[j]);
        }
    }
    return ans;
}
vector <node> v_exp(vector <node> & a,int b)
{
    vector <node> c=a;
    while(--b){
        c=v_mult(c,a);
    }
    return c;
}
void init()
{
    node a;
    dep[5].push_back(a);
    for(int i=4;i>=0;i--){
        int s=dep[i+1].size();
        vector <node > tmp;
        node b;
        b.d[i]=1;
        tmp.push_back(b);
        for(int j=0;j<i;j++){
            node b;
            b.xs=fac(-1,1);
            b.x[j]=1;
            tmp.push_back(b);
        }
        for(int j=0;j<s;j++){
            vector<node> q=v_exp(tmp,dep[i+1][j].x[i]+1);
            int s1=q.size();
            for(int k=0;k<s1;k++){
                node tt=dep[i+1][j]*q[k];
                tt.xs=tt.xs*fac(1,dep[i+1][j].x[i]+1);
                dep[i].push_back(tt);
            }
        }
//        if(i==3){
//            for(size_t j=0;j<dep[i].size();j++){
//                dep[i][j].output();
//            }
//        }
    }
    sort(dep[0].begin(),dep[0].end());
    int ss=dep[0].size();
    node pre=dep[0][0];
    for(int i=1;i<ss;i++){
        if(dep[0][i]==pre){
            pre.xs=pre.xs+dep[0][i].xs;
        }
        else {
            if(pre.xs.fz) ans.push_back(pre);
            pre=dep[0][i];
        }
    }
    if(pre.xs.fz) ans.push_back(pre);
//    cout << ans.size() << endl;
//    for(size_t i=0;i<ans.size();i++){
//        ans[i].output();
//    }
}
struct work
{
    int s1,s2,d;
    bool operator < (const work & b) const{
        return d<b.d;
    }
}tt[10];
int n;
int a[5],d[5];
fac cal()
{
    fac res=fac(0,1);
    for(size_t i=0;i<ans.size();i++){
        fac tmp=ans[i].xs;
        for(int j=0;j<5;j++){
            for(int k=0;k<ans[i].d[j];k++){
                tmp.fz=tmp.fz*d[j];
            }
        }
        tmp=tmp.fix();
        res=res+tmp;
    }
    return res;
}        
void dfs(fac & ans,int s,int t)
{
    if(s==5){
        for(int i=0;i<5;i++) d[i]=tt[i].d;
        for(int i=0;i<5;i++){
            if(a[i]){
                for(int j=i;j<5;j++) d[j]-=tt[i].s2;
            }
        }
        for(int i=3;i>=0;i--) {
            d[i]=min(d[i],d[i+1]);
            if(d[i]<0) return;
        }
        fac p=cal();
//        for(int i=0;i<5;i++) cout << d[i] << " ";
//        cout << endl;
//        cout << p.fz << " " << p.fm << endl;
        if(t) ans=ans+p;
        else ans=ans-p;
        return;
    }
    a[s]=1;
    dfs(ans,s+1,1-t);
    a[s]=0;
    dfs(ans,s+1,t);
}
fac solve()
{
    while(n<5){
        tt[n].s2=1;
        tt[n++].d=2000;
    }
//    for(int i=0;i<n;i++) {
//        printf("%d %d\n",tt[i].s2,tt[i].d);
//    }
    fac ans=fac(0,1);
    dfs(ans,0,1);    
    for(int i=0;i<5;i++) ans.fm=ans.fm*tt[i].s2;
//    cout << ans.fz << " " << ans.fm << endl;
    return ans.fix();
}
int main()
{
    init();
    while(scanf("%d",&n)&&n){
        for(int i=0;i<n;i++) scanf("%d%d%d",&tt[i].s1,&tt[i].s2,&tt[i].d);
        sort(tt,tt+n);
        int flag=1;
        for(int i=0;i<n;i++){
            if(tt[i].s1==tt[i].s2){
                for(int j=i+1;j<n;j++) tt[j].d-=tt[i].s1;
                if(i==0) {
                    if(tt[i].s1>tt[i].d) { flag=0;break;}
                }
                else {
                    tt[i-1].d=min(tt[i-1].d,tt[i].d-tt[i].s1);
                }
                for(int j=i;j<n-1;j++){
                    tt[j]=tt[j+1];
                }
                i-- , n--;
            }
        }
        for(int i=0;i<n;i++) {
            for(int j=i;j<n;j++) tt[j].d-=tt[i].s1;
            tt[i].s2-=tt[i].s1;
            if(tt[i].d<0) { flag=0;break;}
        }
        if(!flag) puts("Poor boy!");
        else if(n==0) puts("Congratulations!");
        else {
            fac ans=solve();
            if(ans.fm<0) { ans.fz=-ans.fz , ans.fm=-ans.fm;}
            if(ans.fz<=0) puts("Poor boy!");
            else if(ans.fz>=ans.fm) puts("Congratulations!");
            else printf("%I64d/%I64d\n",ans.fz,ans.fm);
        }
            
    } 
}