Igor Perić

Problem

You are part of the executive committee of the Database Design Day festivities. You are in charge of promotions and want to print three D’s to create a logo of the contest. You can choose any color you want to print them, but all three have to be printed in the same color.

You were given three printers and will use each one to print one of the D’s. All printers use ink from 4 individual cartridges of different colors (cyan, magenta, yellow, and black) to form any color. For these printers, a color is uniquely defined by 4 non-negative integers c, m, y, and k, which indicate the number of ink units of cyan, magenta, yellow, and black ink (respectively) needed to make the color.

The total amount of ink needed to print a single D is exactly 10e6 units. For example, printing a D in pure yellow would use 10e6 units of yellow ink and 0 from all others. Printing a D in the Code Jam red uses 0 units of cyan ink, 500000 units of magenta ink, 450000 units of yellow ink, and 50000 units of black ink.

To print a color, a printer must have at least the required amount of ink for each of its 4 color cartridges. Given the number of units of ink each printer has in each cartridge, output any color, defined as 4 non-negative integers that add up to 10e6, such that all three printers have enough ink to print it.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of 3 lines. The i-th line of a test case contains 4 integers Ci, Mi, Yi, and Ki, representing the number of ink units in the i-th printer’s cartridge for the colors cyan, magenta, yellow, and black, respectively.

Output

For each test case, output one line containing Case #x: r, where x is the test case number (starting from 1) and r is IMPOSSIBLE if there is no color that can be printed by all 3 printers. Otherwise, r must be equal to “c m y k” where c, m, y, and k are non-negative integers that add up to 10e6 and c≤Ci, m≤Mi, y≤Yi, and k≤Ki, for all i.

If there are multiple solutions, you may output any one of them. (See “What if a test case has multiple correct solutions?” in the Competing section of the FAQ.) This information about multiple solutions will not be explicitly stated in the remainder of the 2022 contest.

Limits

Time limit: 5 seconds.
Memory limit: 1 GB.

Test Set 1 (Visible Verdict)

1≤T≤100
0≤Ci≤10e6, for all i
0≤Mi≤10e6, for all i
0≤Yi≤10e6, for all i
0≤Ki≤10e6, for all i

Sample input

3
3
300000 200000 300000 500000
300000 200000 500000 300000
300000 500000 300000 200000
1000000 1000000 0 0
0 1000000 1000000 1000000
999999 999999 999999 999999
768763 148041 178147 984173
699508 515362 534729 714381
949704 625054 946212 951187

Sample output

Case #1: 300000 200000 300000 200000
Case #2: IMPOSSIBLE
Case #3: 400001 100002 100003 399994

Sample Case #1 is the image provided above. The proposed color is using up all of the ink in the cyan, magenta, and yellow cartridges of the first printer and all of the ink in the black cartridge of the last printer. This means that no additional unit of ink could be used from any of the 4 ink colors, so the given sample output is the only possible output for this case.

In Sample Case #2, magenta is the only color that both the first and second printers have, so our only chance would be to use 10e6 units of magenta. Unfortunately, the third printer does not have quite enough, making this case impossible.

In Sample Case #3, other correct outputs are: “400000 100000 100000 400000“, “300000 0 0 700000“, and “350000 140000 160000 350000“, among lots of others. Notice that “300000 140000 160000 700000” would not be a valid answer because, even though there is enough ink in all printers to do that, the total number of ink units must be exactly 10e6.

Solution

We can apply a greedy approach.

The first observation is the solution is not unique, so the actual amount of color we pick doesn’t really matter, as long as they add up to exactly 10e6. This effectively means we can take colors one by one, each time taking as much as possible until we overshoot 10e6. Once we do, we remove the difference between 10e6 and accumulated amount to satisfy the total color constraint – this means we take zero units of the rest of the colors.

If we try taking as much as possible of all four colors and we still don’t reach 10e6 we print out “IMPOSSIBLE”.

And lastly, “as much as possible” means simply finding the minimum ink amount for each color among all three printers, since that bottleneck represents the maximum units we can take.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int t, q=0;
    cin >> t;
    while (q++ < t) {
        cout << "Case #" << q << ": "; 

        int i, j, a;
        int s[4] = { -1, -1, -1 , -1};
        for (i=0;i<3;i++) {
            for (j=0;j<4;j++) {
                cin >> a;
                // find minimum for each color accross all printers
                if (s[j] == -1 || s[j] > a) s[j] = a;
            }
        }
        long S = 0;
        long sol[4] = { 0, 0, 0, 0 };
        for (i=0;i<4;i++) {
            // keep adding up the minimums for each color...
            S += s[i];
            sol[i] = s[i];
            // ... until we hit something higher than 10e6
            if (S >= 1e6) {
                // remove the overhead from the formed solution...
                sol[i] -= S - 1e6;
                // ... and stop the search (pick zeroes for the rest of the colors)
                break;
            }
        }

        if (S < 1e6) cout << "IMPOSSIBLE";
        else {
            for (j=0;j<4;j++) cout << sol[j] << " ";
        }
        cout << endl;
    }
    return 0;
}