Zonal Computing Olympiad 2013, 10 Nov 2012
10:00 am-1:00 pm IST
Problem 1 : Tournament
N teams participate in a league cricket tournament on Mars, where each pair of distinct teams plays each other exactly once. Thus, there are a total of (N × (N-1))/2 matches. An expert has assigned a strength to each team, a positive integer. Strangely, the Martian crowds love one-sided matches and the advertising revenue earned from a match is the absolute value of the difference between the strengths of the two matches. Given the strengths of the N teams, find the total advertising revenue earned from all the matches.
For example, suppose N is 4 and the team strengths for teams 1, 2, 3, and 4 are 3, 10, 3, and 5 respectively. Then the advertising revenues from the 6 matches are as follows:
| Match | Team A | Team B | Ad revenue |
|---|---|---|---|
| 1 | 1 | 2 | 7 |
| 2 | 1 | 3 | 0 |
| 3 | 1 | 4 | 2 |
| 4 | 2 | 3 | 7 |
| 5 | 2 | 4 | 5 |
| 6 | 3 | 4 | 2 |
Thus the total advertising revenue is 23.
Input format
Line 1 : A single integer, N.
Line 2 : N space-separated integers, the strengths of the N teams.
Output format
A single integer, the total advertising revenue from the tournament.
Sample input
4 3 10 3 5
Sample output
23
Test data
In all subtasks, the strength of each team is an integer between 1 and 1,000 inclusive.
Subtask 1 (30 marks) : 2 ≤ N ≤ 1,000.
Subtask 2 (70 marks) : 2 ≤ N ≤ 200,000.
Limits
Time limit : 3s
Memory limit: 64 MB
Note
The answer might not fit in a variable of type int. We recommend that type long long be used for computing all advertising revenues. If you use printf and scanf, you can use %lld for long long.
Copyright (c) IARCS 2003-2024; Last Updated: 24 Nov 2013