P1984 [SDOI2008] Boiling Water Problem

A total mass of $1\ \rm kg$ of water is divided into $n$ cups, each containing $(1/n)\ \rm kg$ of water, all initially at $0$ degrees. We need to bring every cup of water to a boil. We may heat any cup. The energy required to raise one cup’s temperature by $t$ degrees is $(4200\times t/n)\rm J$, where $\rm J$ is the energy unit "joule". Once a cup’s temperature reaches $100$ degrees, it cannot be heated further; at that point we consider this cup to have been boiled. Clearly, if we simply boil the cups one by one directly, the total energy required is $(4200\times 100)\rm J$. During the process, we may perform heat transfer between any two cups at different temperatures at any time. Heat can only flow from the hotter cup to the cooler cup. Since the two cups have equal mass, after a heat transfer operation, the temperature decrease of the originally hotter cup always equals the temperature increase of the originally cooler cup. Heat transfer stops immediately once the two cups reach the same temperature. To simplify the problem, assume: 1. When neither heating nor heat transfer is being performed, water temperature does not change. 2. All energy spent on heating is absorbed by the water; the cup absorbs no energy. 3. Heat transfer always occurs through the cup walls; the $n$ cups of water never mix. 4. Heat transfer conserves energy and has no loss. In this problem, it is only required that each cup be brought to a boil at least once; it is not required that every cup ends at $100$ degrees. For example, we can boil two cups as follows: first heat one cup to $100$ degrees, costing $(4200\times 100/2)\rm J$, then perform heat transfer between the two cups until both are at $50$ degrees, and finally heat the cup that was not previously brought to $100$ degrees up to $100$ degrees, costing $(4200\times 50/2)\rm J$. At this point, both cups have been boiled; the current temperatures are one at $100$ degrees and one at $50$ degrees. The total energy spent is $(4200\times 75)\rm J$, which is $25\%$ less than the $(4200\times 100)\rm J$ required by direct boiling. Your task is to design an optimal sequence of operations that minimizes the total energy required to ensure that all $n$ cups are each boiled at least once.

One line containing an integer $n$.

Output the minimal total energy required to boil all $n$ cups at least once, in $\rm J$, rounded to two decimal places.

### Constraints For all testdata, $1 \le n \le 3000000$. Translated by ChatGPT 5