Assign each item to one of two buckets so the running totals stay as balanced as possible.
You are given a sequence of egg painting times. Two painters work in parallel, and each egg must be assigned to exactly one painter. The goal is to keep the total time spent by the two painters as balanced as possible while processing the eggs in order of the input.
For each egg, choose the painter whose current total time is smaller; if both totals are equal, either choice is acceptable. After all eggs are assigned, report the final total time for each painter and the smaller of the two totals as the amount of time the faster painter spent.
This is a standard greedy balancing task: at each step, always give the next egg to the painter who is currently less loaded.
Input Format
Input
- The first line contains an integer — the number of eggs.
- The second line contains integers representing the painting time of each egg.
Interpretation
- Process eggs from left to right.
- Assign each egg to one of two painters according to the balancing rule described above.
Output Format
Output
- Print the final total time of the first painter and the second painter.
- Optionally, print the minimum of the two totals if required by the variant you are practicing.
Constraints
- Egg painting times are positive integers.
- Use a linear-time greedy simulation.
Example 1
Input
5 1 2 3 4 5
Output
9 6
Explanation
Assign 1 to painter A, 2 to painter B, 3 to painter A, 4 to painter B, and 5 to painter B. Final totals are 9 and 6.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.