ORANGE JUICE - SEPT001 - EDITORIAL

editorial
,
1

ORANGE JUICE - SEPT001 - EDITORIAL

PROBLEM LINK

Practice
Contest

Author: codechefsrm
Editorialist : codechefsrm

DIFFICULTY

EASY-MEDIUM

PREREQUISITES

Arrays,Greedy,Math,Algorithm

PROBLEM

To make an orange juice solution of the highest posssible density
by mixing the powder along with water in a glass, following the prerequisites.

EXPLANATION

We can pour exactly x grams of water if there exist non-negative integers i,j
such that x = 100Ai + 100Bj. Similarly, we can pour exactly y grams of orange powder
if there exists non-negative integers i,j such that y = Ci + Dj.
Since x; y<=F, we can generate all possible values of x,y in O(F^2) time.
Finally, for each possible pair (x,y) (There are O(F^2) such pairs), consider
the case where we put x grams of water and y grams of orange powder, check whether it
satisies the conditions, and compute the maximum density.

If all the powder dissolved in the water when you put x g of water and y g of powder in the glass?
If you check it, take the one with the highest concentration for the melted one and output it
It’s good.

Example Text Case
Input:
1 2 10 20 15 200

Output:
110 10

Note :Water and orange powder make juice. In this environment, 15 grams of orange powder can dissolve into 100 grams of water,
and the glass can contain at most 200 grams of substances. We can make 110 grams of orange juice by performing Operation 1 once and
Operation 3 once. It is not possible to make orange juice with higher density

SOLUTION :

Setter's Solution 
/* CODE STARTS HERE */
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <cmath>
#include <ctime>
using namespace std;

int a,b,c,d,e,f; 
void input()
{
    cin >> a >> b >> c >> d >> e >> f;
}

void solve()
{
    vector<int> water(31,0),oj(3001,0);
    water[a] = 1, water[b] = 1;
    oj[0] = 1;
    for (int i = 0; i < 31; ++i) {
        if(water[i] == 1){
            if(i+a<31) water[i+a] = 1;
            if(i+b<31) water[i+b] = 1;
        }
    }
    for (int i = 0; i < 3001; ++i) {
        if(oj[i] == 1){
            if(i+c<3001) oj[i+c] = 1;
            if(i+d<3001) oj[i+d] = 1;
        }
    }

    int ans[2]; 
    ans[0] = a*100, ans[1] = 0;
    for (int i = 1; i < 31; ++i) {
        if (water[i] == 0) continue;
        for (int j = 0; j < 3001; ++j) {
            if (oj[j] == 0) continue;
            if (i * e < j) continue;
            if (i * 100 + j > f) continue;

            if ((i * 100 + j) * ans[1] < j * ans[0]){
                ans[0] = i * 100 + j, ans[1] = j;
            }
        }
    }
    cout << ans[0] << " " << ans[1] << endl;
}

int main()
{
    cin.tie();
    ios::sync_with_stdio(false);
    // int ti = clock();
    input();
    solve();
    // printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
    return 0;
}
/*CODE ENDS HERE*/