## Algorithm

Problem Name: 2 AD-HOC - beecrowd | 1750

# Help Cupid

By Pablo Ariel Heiber, Universidad de Buenos Aires Argentina

Timelimit: 1

Cupid’s job is getting harder, so he is adopting new technologies to help him with his difficult task of matching people into happy couples. He appointed the best programmers in his staff to a new project called Advanced Couples Matching (ACM). For this project, the programmers need to produce an algorithm that takes a set of an even number of N lonely persons and matches them into N/2 couples, such that each person is in exactly one couple.

Sadly, the data available about each person is limited. In this modern world, using gender, ethnicity, age or nationality as criteria to form couples is not a sensible option, so the programmers can only use data about the internet connection of each candidate. They decided to focus this stage on time zones. People living in closer time zones are more likely to find time to interact with each other. Thus, the programmers decided to create couples so as to minimize the total time difference.

Each time zone is identified by an integer between −11 and 12, inclusive, representing its difference in hours from a particular time zone called Coordinated Universal Time (or UTC). The time difference of two people living in time zones represented by integers i and j is the minimum between |ij| and 24 − |ij|. Given a partition of a set of an even number N of candidates into N/2 couples, its total time difference is the sum of the time difference of each couple.

You are asked to write a program that receives as input the time zones of a set of N candidates. The output of the program must be the minimum total time difference among all possible partitions of the set into couples.

## Input

The first line contains an even integer N (2 ≤ N ≤ 1000) representing the number of candidates to be coupled. The second line contains N integers T1 , T2 , . . . , TN (−11 ≤ Ti ≤ 12 for i = 1, 2, . . . , N ) indicating the time zones of the candidates.

## Output

Output a line with an integer representing the minimum total time difference among all possible partitions of the set of candidates into couples.

 Input Samples Output Samples 6 -3 -10 -5 11 4 4 5

 2 -6 6 12

 8 0 0 0 0 0 0 0 0 0

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <deque>
using namespace std;
deque cupidos;
inline int calcula(int a, int b) {
int delta = abs(a - b);
return min(delta, 24 - delta);
}
int func() {
int soma = 0;
for (int i = 0; i + 1 < cupidos.size(); i += 2) {
soma += calcula(cupidos[i], cupidos[i + 1]);
}
return soma;
}
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int davez;
scanf("%d", &davez);
cupidos.push_back(davez);
}
sort(cupidos.begin(), cupidos.end());
int referencia = func();
for (int vez = 1; vez <= n; vez++) {
cupidos.push_back(cupidos.front());
cupidos.pop_front();
referencia = min(referencia, func());
}
printf("%d\n", referencia);
return 0;
}
``````
Copy The Code &

Input

cmd
6
-3 -10 -5 11 4 4

Output

cmd
5