Final Shutdown | MatCom Online Grader

The 2025 ICPC Caribbean Finals (Qualifier) - Real Contest

Ended

Overview
Problems
Standing
Submissions
Submit
Clarifications
Virtual participation

Register

Are you sure you want to participate in this contest ? If you select a team then virtual participation for other team members will be disabled. So, pick one if and only if your teammates are ready to compete with you.

F - Final Shutdown

Languages: C, C++, Java, Python, Kotlin

Time & Memory limits: (details)

<div style="text-align: justify">
Your task is to shut down a series of $n$ power generators, each located at a distinct position along a one-dimensional line. Starting from a specific generator, carefully determine the sequence of shutdowns and movements between generators to minimize the total energy consumed.

**Energy Consumption**

Each generator $i$ has a base energy consumption rate of $e_i$, but its energy rate changes over time. Let $E(i, t)$ be the rate of generator $i$ during the time interval $[t, t+1)$. </div>
* The rate starts at its base value: $E(i, 0) = e_i$.
* The rate increases by **1 unit per second**.
* If a generator's rate reaches 1000, it **resets** to its base rate $e_i$ in the next second. Formally, if $E(i, t) = 1000$, then $E(i, t + 1) = e_i$.

**Shutdown Process**
1. You start at time $t=0$ at a given generator $s$.
2. The starting generator $s$ is shut down **instantly**.
3. You then repeatedly travel to an adjacent active generator (to the immediate left or right of the contiguous block of shut-down generators).
4. Once a generator is shut down, it becomes part of a **teleportation network**. As a result, you may move instantly to any previously shut-down generator without incurring **travel time** or extra **energy cost**.
5. Travel time equals the **distance** between generators. The distance between generators $i$ and $j$ is $|x_i - x_j|$ for all $1 \le i,j \le n$.
6. When you arrive, the generator is shut down **instantly**.
7. During travel, all generators that are still active continue to consume energy.

Your goal is to find a shutdown sequence that **minimizes the total energy consumed**.

Input

Output

Sample test(s)

Input

2 3 2 1 4 6 5 9 7 3 2 1 2 5 10 9 2

--- Showing first 30 lines (click "Copy" to get full content) ---

Output

84 58

--- Showing first 30 lines (click "Copy" to get full content) ---

Notes

In the first case, there are three generators: generator 1 ($x_1=1$ and $e_1=4$), generator 2 ($x_2=6$ and $e_2=5$), and generator 3 ($x_3=9$ and $e_3=7$).

The optimal order to shutdown the generators is: 2 → 3 → 1 (turn off generator 2 at $t=0$, then generator 3 at $t=3$, teleport to generator 2 instantly ($t=3$), and finally turn off generator 1 at $t=8$).

**Move 1:** from $x_2=6$ to $x_3=9$ ($\Delta$ = 3 seconds), starts at $t_0 = 0$.

Active during this move: generator 1 ($E=4$) and generator 3 ($E=7$), while generator 2 is already off.

Per-second table for $t = 0,1,2:$

| second t | gen1 rate $E_1+t$ | gen2 (off) | gen3 rate $E_3+t$ | sum |
|:----------:|:----------------:|:-----------:|:----------------:|:---:|
| 0          | 4+0=4          | ---         | 7+0=7          | 11  |
| 1          | 4+1=5          | ---         | 7+1=8          | 13  |
| 2          | 4+2=6          | ---         | 7+2=9          | 15  |
| **Move 1 total** |              |             |                  | **39** |

Generator 3 is turned off at $t = 3$.

**Move 2:** teleport from $x_3=9$ to $x_2=6$ as they are part of the teleportation network, $t$ remains $3$.

**Move 3:** from $x_2=6$ to $x_1=1$ ($\Delta$ = 5 seconds), starts at $t_0=3$.

Active during this move: only generator 1 ($E=4$) because generator 3 was turned off at $t=3$.

Per-second table for $t = 3,4,5,6,7:$

| second t | gen1 rate $E_1+t$ | gen2 (off) | gen3 (off) | sum |
|:----------:|:----------------:|:-----------:|:----------------:|:---:|
| 3          | 4+3=7          | ---         | ---          | 7  |
| 4          | 4+4=8          | ---         | ---          | 8  |
| 5          | 4+5=9          | ---         | ---          | 9  |
| 6          | 4+6=10          | ---         | ---          | 10  |
| 7          | 4+7=11          | ---         | ---          | 11  |
| **Move 3 total** |              |             |                  | **45** |

Generator 1 is turned off at $t = 8$. At this point, all generators are already turned off.

Therefore, the total energy consumed during the shutdown process is $39 + 45 = 84$.

Matcom Online Grader

The 2025 ICPC Caribbean Finals (Qualifier) - Real Contest

Ended

F - Final Shutdown

Languages: C, C++, Java, Python, Kotlin

Time & Memory limits: (details)

Input

Output

Sample test(s)

Notes