# PBinfo #3733 – Cosuri – Rezolvare C++

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

## Enunț

Enunț
Se consideră N coșuri numerotate cu numerele distincte de la 1 la 2•N.
Coșul 1 conține C1 mere, coșul 2 conține C2 mere,…, coșul 2•N conține C2•N mere.

Cele 2•N coșuri vor fi grupate două câte două, rezultând N perechi de coșuri. Fiecare coș poate face parte dintr-o singură pereche. Numărul de mere dintr-o pereche de coșuri este egal cu suma numerelor de mere din cele două coșuri. Pentru fiecare pereche, valoarea absolută a diferenței numerelor de mere din cele două coșuri ale perechii reprezintă excedentul perechii.

Ionuț, având o fire curioasă, vrea să afle mai multe despre aceste perechi.

Mai întâi vrea să afle numărul minim posibil, respectiv maxim posibil, de mere dintr-o pereche, indiferent de gruparea coșurilor în perechi de câte două.

Apoi, Ionuț vă întreabă dacă este posibil să grupeze cele 2•N coșuri în perechi de câte două, astfel încât cele N perechi rezultate să aibă același număr de mere. Dacă este posibil, atunci Ionuț vrea să afle și care este valoarea minimă a excedentelor perechilor din noua grupare.

Voi va trebui să îl ajutați pe Ionuț să afle răspunsurile la întrebările lui.

Cerința
Scrieți un program care să citească numărul N și cele 2•N numere naturale C1,  C2,…, C2•N, iar apoi să determine:

1. Numărul minim de mere și numărul maxim de mere pe care le pot avea perechile de coșuri.

2. Răspunsul DA sau NU la întrebarea lui Ionuț; dacă răspunsul este DA, se va determina și care este valoarea minimă a excedentelor perechilor din noua grupare.

Date de intrare
Fișierul de intrare cosuri.in conține pe prima linie două numere naturale T și N separate printr-un spațiu. A doua linie a fișierului conține cele 2•N numere naturale C1,  C2,…, C2•N, separate prin câte un spațiu.

Date de ieșire
Fișierul de ieșire cosuri.out va conține:


Dacă T=1, pe prima linie, două numere naturale separate printr-un singur spațiu reprezentând numărul minim, respectiv maxim de mere pe care le pot avea perechile (răspunsul la cerinţa 1);
Dacă T=2, pe prima linie, un șir de două caractere care poate fi DA sau NU, reprezentând răspunsul la întrebarea lui Ionuț; dacă răspunsul este DA, atunci a doua linie a fișierului va conține un număr natural reprezentând valoarea minimă a excedentelor perechilor din noua grupare (răspunsul la cerința 2).

Restricții și precizări

1 ≤ N ≤ 500 000
1 ≤ Ci ≤ 1 000 000, pentru oricare 1 ≤ i ≤ 2·N
Pentru teste în valoare de 30 de puncte, T = 1
Pentru restul de 70 de puncte, T= 2
Pentru teste în valoare de 20 de puncte, N ≤ 5
Pentru alte teste în valoare de 40 de puncte, N ≤ 70000

Exemplul 1:
cosuri.in

1 3
1 7 4 10 2 9
cosuri.out

3 19
Explicație
Se rezolvă cerința 1. Perechea formată din coșurile 1 și 5 are 3 mere, iar perechea formată din coșurile 4 și 6 are 19 mere. Se observă că aceste valori sunt minimul, respectiv maximul posibil.

Exemplul 2:
cosuri.in

2 3
1 7 4 10 2 9
cosuri.out

DA
3
Explicație
Se rezolvă cerința 2. Grupând coșurile 1 cu 4, 2 cu 3 și 5 cu 6, obținem 3 perechi cu câte 11 mere fiecare (1 + 10, 7 + 4, 2 + 9) și cu excedentele: 9 (=|1-10|), 3 (=|7-4|), 7 (=|2-9|). Valoarea minimă a excedentelor perechilor din noua grupare este 3.

Exemplul 3:
cosuri.in

2 3
1 7 5 12 2 9
cosuri.out

NU
Explicație
Se rezolvă cerința 2. Este imposibil să formăm perechile de coșuri, deci răspunsul este NU.

## Cod sursă C++

```cpp
/// Ioan Cristian Pop
#include <cstdio> 
#include <algorithm> 
using namespace std; 
const int NMAX = 1000000; 
int f[NMAX + 1]; 
int main() 
{ 
    freopen("cosuri.in", "r", stdin); 
    freopen("cosuri.out", "w", stdout); 
    int n, s, x, y, t, mn, mx, mn2, mx2, diff; 
    bool ok = 1; 
    scanf("%d%d", &t, &n); 
    if (t == 1) { 
        scanf("%d %d", &x, &y); 
        mn = mx2 = min(x, y); 
        mx = mn2 = max(x, y); 
        for (int i = 3; i <= 2 * n; ++i) { 
            scanf("%d", &x); 
            if (x < mn) { 
                mn2 = mn; 
                mn = x; 
            } else if (x < mn2) { 
                mn2 = x; 
            } 
            if (x > mx) { 
                mx2 = mx; 
                mx = x; 
            } else if (x > mx2) { 
                mx2 = x; 
            } 
        } 
        printf("%d %d\n", mn + mn2, mx + mx2); 
        return 0; 
    } 
    scanf("%d", &x); 
    mn = mx = x; 
    ++f[x]; 
    for (int i = 2; i <= 2 * n; ++i) { 
        scanf("%d", &x); 
        ++f[x]; 
        if (mn > x) { 
            mn = x; 
        } 
        if (mx < x) { 
            mx = x; 
        } 
    } 
    s = mn + mx; 
    for (int i = 1; i <= (s + 1) / 2; ++i) { 
        if (f[i] != f[s - i]) { 
            ok = 0; 
            break; 
        } 
        if (f[i] > 0) { 
            diff = (s - i) - i; 
        } 
    } 
    if (ok == 0) { 
        printf("NU\n"); 
    } else { 
        printf("DA\n%d\n", diff); 
    } 
    return 0; 
}
```

## Resurse

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