Rezolvare PBinfo #3733

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.