Connection Status:
Competition Arena > HeatDeath

HeatDeath

TCO04 Round 4 · 2004-09-07 · by vorthys

TCO04 Round 4 · 2004-09-07 · by vorthys · Greedy
Class Name: HeatDeath
Return Type: int
Method Name: maxTime
Arg Types: (vector<int>)
Problem Statement

Problem Statement

The heat death of the universe occurs when all available energy has moved from "hot" (high energy) locations to "cold" (low energy) locations. Hot and cold are relative concepts--energy can flow from one location to another if and only if the energy level of the first location is at least 2 units greater than the energy level of the second location. Heat death occurs when there are no more locations between which energy can flow. Naturally, we would like to put off heat death for as long as possible.

You will be given a int[] energy that contains the energy levels of all locations in a closed system at time 0. Every microsecond, a random pair of locations whose energy levels differ by at least two units will be chosen, and a single unit of energy will flow from the hotter location to the colder location. Notice that the locations do not have to be adjacent. Depending on the order in which pairs of locations are chosen, heat death could arrive in different amounts of time. Calculate and return the maximum number of microseconds until the system reaches heat death.

Constraints

  • energy contains between 2 and 50 elements, inclusive.
  • Each element of energy is between 1 and 999, inclusive.
Examples
0)
{ 1,5,9 }
Returns: 7
1)
{ 5,5,5,5 }
Returns: 0
2)
{ 2,2,3,3,3,4,4,5,5 }
Returns: 4
3)
{ 1,2,3,4,5,6,7,8,9 }
Returns: 30
4)
{ 5, 7, 9 }
Returns: 3

Heat death could arrive in as little as 2 microseconds, if energy flows twice from the third location to the first location. On the other hand, if energy first flows from the third location to the second location, then from the third location to the first location, and finally from the second location to the first location, heat death can be put off for a total of 3 microseconds. (Other sequences may also achieve the maximum.)

5)
{ 5, 6, 5, 6 }
Returns: 0

No heat can flow. This system has already reached heat death.

Submissions are judged against all 106 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class HeatDeath with a public method int maxTime(vector<int> energy) · 106 test cases · 2 s / 256 MB per case

Submitting as anonymous