Project Euler #236: Luxury Hampers

  • + 0 comments

    include

    include

    include

    include

    include

    include

    using namespace std;

    void Luxury_Hampers(int n, vector a, vector b){ long sum1=0,sum2=0; int sum_of_a_till_now=0; int sum_of_b_till_now=0;

    int till_now_bad_a=0;
    int till_now_bad_b=0;
    
    int flag=0;
    vector <int> Na;
    vector <int> Nb;
    for (int i=0; i<n; i++){
        float r1,r2;
        flag=0;
        sum_of_a_till_now+=a[i];
        sum_of_b_till_now+=b[i];
        for (int j=a[i]-1; j>0; j--){
            r1=(float)j/a[i];
            for (int k=1; k<=b[i]; k++){
                r2=(float)k/b[i];
                if (r2>r1){
                    till_now_bad_a+=j;
                    till_now_bad_b+=k;
                    if (i>0){
                        float prev_a = (float)till_now_bad_a/sum_of_a_till_now;
                        float prev_b = (float)till_now_bad_b/sum_of_b_till_now;
                        if (prev_a>prev_b){
                            Na.push_back(j);
                            Nb.push_back(k);
                            flag=1;
                            break;
                        }
                        else{
                            till_now_bad_a-=j;
                            till_now_bad_b-=k;
                        }
                    }
                    else{
                        Na.push_back(j);
                        Nb.push_back(k);
                        flag=1;
                        break;
                    }
                }
            }
            if (flag==1)
            break;
        }
    }
    for (int i=0; i<n; i++){
        sum1+=a[i];
        sum2+=b[i];
    }
    long suma=0,sumb=0;
    for (int i=0; i<Na.size(); i++){
        suma+=Na[i];
        sumb+=Nb[i];
    }
    
    long num=suma*sum2;
    long den=sumb*sum1;
    
    if (num>den){
        int a=num%den;
        if (num%a==0&&den%a==0){
            num/=a;
            den/=a;
        }
        cout<<num<<"/"<<den;
    }
    else if (den>num){
        int a=den%num;
        if (den%a==0&&num%a==0){
            num/=a;
            den/=a;
        }
        cout<<num<<"/"<<den;
    }  
    

    }

    int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ int n; cin>>n; vector a; vector b; for (int i=0; i>x; a.push_back(x); } for (int i=0; i>x; b.push_back(x); }

    Luxury_Hampers(n,a,b);
    return 0;
    

    }