Log inSign up
Problems / B076

Maximizing the temperature shock

200 ptsCases 15Set by dongbinna
Added October 30.
1 solved1 attempted1 submissionssolvers took 1.0 tries on average

Statement

There are N freezer warehouses, numbered from 1 to N. Each warehouse has a set temperature. A set temperature can go below zero, so it can be negative.

An inspector visits all N warehouses, each one exactly once. The inspector is free to choose the order of the visits. When the inspector moves from one warehouse to the next, the thermometer the inspector carries takes a shock equal to the absolute value of the difference between the set temperatures of the two warehouses. The total shock for one order of visits is the sum of the absolute temperature differences over every pair of warehouses visited one after the other. There is no shock when the inspector enters the first warehouse or leaves the last one.

The thermometer is being tested to see how much it can take, so the inspector wants to visit in the order that makes the total shock largest. Write a program that takes the set temperatures of the N warehouses and computes the largest total shock that can be taken.

For example, suppose the set temperatures of the N=3 warehouses are the ones in the table below.

Warehouse123
Set temperature-1-49-18

The shock taken when two warehouses are visited one after the other is as follows.

Two warehouses visited one after the other1 and 21 and 32 and 3
Shock481731

There are six orders in all for visiting the three warehouses. The total shock for each order is as follows.

Visit orderCalculationSum
1, 2, 348 + 3179
1, 3, 217 + 3148
2, 1, 348 + 1765
2, 3, 131 + 1748
3, 1, 217 + 4865
3, 2, 131 + 4879

The largest sum is 79. Warehouse 2, which has the lowest temperature, has to sit in the middle so that a large difference is used twice, once on each side. The answer for this example is therefore 79.

Input and Output Examples

Example 1

Input

3
-1 -49 -18

Output

79

Example 2

Input

4
85 92 79 86

Output

27

Example 3

Input

6
20 1 15 8 4 10

Output

62

Input

  • First the number of warehouses N is given as a natural number. N is a natural number from 3 to 8.

  • Then the set temperatures of warehouses 1 through N are given in order on one line, separated by spaces. Each set temperature is an integer from -100 to 100, and a warehouse below zero is given as a negative number. Warehouses may share the same set temperature, and every warehouse may have the same set temperature.

Output

  • Print the largest total shock that can be taken as a single number on one line. If every warehouse has the same set temperature, this value is 0.

Requirements

  • Visit all N warehouses, each one exactly once
  • The total shock is the sum of the absolute differences between the set temperatures of every two warehouses visited one after the other
  • Do not count any shock when entering the first warehouse or leaving the last one
  • Consider every visit order and print only the single largest total shock
  • You must write a program that reads from standard input and writes to standard output
  • Trailing spaces at the end of a line and blank lines at the end of the output are ignored when grading
  • The languages you can use are Python and JavaScript
  • The memory limit is 256MB. The browser does not measure it, it only states it
  • The time limit is set by measuring the setter's reference solution on the same runtime
  • On this problem you submit code, not a prompt. That code runs in the browser on this device, and all that goes to the server is a fingerprint of the output and the time it took. Whether it is correct is decided by the server. The run time is a number each device reports, so the code and the device details are posted next to it on the leaderboard.
  • The output has to match the expected value down to the character. A space inside a line counts the same as any other character.
  • There are 15 cases, and 3 of them show the input together with the expected output. The rest are used only when you submit and are not shown on this page.
  • You have to pass all 15 cases to solve this.
Read the requirements carefully before solving. Tampering with the grading to make a submission look like a pass can get you sanctioned if caught. The code you submit is published on the leaderboard along with the result.

Examples

3 public cases. Judging also uses hidden cases. You have to pass all 15 cases to solve this.

Input
Expected output
3
-1 -49 -18
79
4
85 92 79 86
27
6
20 1 15 8 4 10
62

Solution

Your code runs on this device. Only the fingerprint of the output and the elapsed time go to the server. The server decides whether it is correct.

0 chars1 lineMemory 256MB (recorded only)Reference 11ms

Submitting requires you to log in. Running against the public cases works without one.

You can test with 3 public cases. Submitting runs the hidden cases too.

People who solved this problem

The time shown is the time spent solving. Input reading time is outside the solver's control, so it is excluded. And since each device reports this value itself, we record which device measured it.

1bampal2531ms284 charsPythonWindows NT 10.0 / Chrome/156.0.0.0 / 8코어 / 16GB

Log in and you can see the code once you solve this problem.