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

Explicație

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

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema impartire:

#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;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2646 impartire

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2646 impartire de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2646 impartire