# PBinfo #2646 – impartire – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Cerința
Se dau n numere naturale, unde n este un număr par. Se grupează cele n numere în perechi şi pentru fiecare pereche de numere se află restul împărţirii unui număr din pereche la celălalt. Se cere să se afle valoarea minimă a sumei acestor resturi.

Date de intrare
Programul citește de la tastatură numărul n, iar apoi cele n numere naturale, separate prin spații.

Date de ieșire
Programul va afișa pe ecran suma minimă a resturilor.

Restricții și precizări

2 ≤ n ≤ 18
cele n numere citite vor fi mai mici decât 1.000

Exemplu:
Intrare

4
6 5 3 4
Ieșire

1
Explicație
Grupând numerele 6 cu 3 și 4 cu 5 se obțin resturile 0, respectiv 1. Suma lor este 1.

## Cod sursă C++

```cpp
#include <iostream>
using namespace std;
int m, n, i, minim, a[21], viz[21] ;
void backtrack( int niv, int suma )
{
    int mini, b, c, j, i ;
    if( niv == m )
    {
        i = m ;
        while( viz[i] != 0 ) i++ ;
        b = a[i] ;
        viz[i] = 1 ;
        j = i ;
        while( viz[j] != 0 ) j++ ;
        c = a[j] ;
        mini = b % c ;
        if( c % b < mini ) mini = c % b ;
        if( suma + mini < minim ) minim = suma + mini ;
        viz[i] = 0 ;
    }
    else
    {
        i = niv ;
        while( viz[i] != 0 ) i++ ;
        b = a[i] ;
        viz[i] = 1 ;
        for( j = i + 1 ; j <= n ; j++ )
            if( viz[j] == 0 )
        {
            c = a[j] ;
            viz[j] = 1 ;
            mini = b % c ;
            if( c % b < mini ) mini = c % b ;
            backtrack( niv + 1 , suma + mini ) ;
            viz[j] = 0 ;
        }
        viz[i] = 0 ;
    }
}
int main()
{
    cin >> n ;
    for( i = 1 ; i <= n ; i++ )
        cin >> a[i] ;
    m = n / 2 ;
    minim = 1000000 ;
    backtrack(1,0) ;
    cout << minim ;
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/2646)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/2646/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-2646/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)