Clubul Sportiv SEPI are și o secție de patinaj artistic. Conducerea clubului și-a propus să participe la proba de perechi a următoarei olimpiade și are de luat unele decizii privind echipele pe care le poate înscrie.
Fiecare echipă participantă la olimpiadă trebuie să fie formată dintr-o pereche de patinatori (o fată și un băiat) și un antrenor. În plus, valorile membrilor unei echipe trebuie să fie cât mai apropiate. Valoarea unui sportiv și respectiv a unui antrenor este calculată pe baza rezultatelor obținute la competițiile anterioare. Acestea sunt codificate sub forma unui singur număr cu cel mult 9
cifre. Fiecare cifră a numărului reprezintă un rezultat anterior, iar \textbf{suma cifrelor reprezintă valoarea sportivului, respectiv antrenorului}. De exemplu, numărul 18305
codifică rezultatele 1
, 8
, 3
, 0
, 5
, obținute la ultimele 5
concursuri, ceea ce corespunde valorii 17 (= 1 + 8 + 3 + 0 + 5)
.
La olimpiadă fiecare sportiv și fiecare antrenor poate să facă parte din cel mult o echipă înscrisă. În plus, pentru fiecare echipă, dacă notăm cu VM
maximul dintre valorile antrenorului, fetei și băiatului și cu Vm
minimul dintre valorile antrenorului, fetei și băiatului, înscrierea în concurs este permisă doar dacă VM - Vm ≤ 1
.
Cerința
Cunoscând numerele care codifică rezultatele antrenorilor, fetelor și băieților, scrieți un program care să determine:
1) Numărul maxim de echipe, NP
, pe care le poate înscrie Clubul Sportiv SEPI la olimpiadă astfel încât acestea să respecte regulile de mai sus.
2) Valoarea maximă, V
, a unui antrenor al clubului care poate antrena o pereche de patinatori (fată, băiat), ce poate fi înscrisă la olimpiadă conform regulilor de mai sus și numărul de variante NV
în care se poate alege o echipă care poate fi pregătită de un antrenor de valoare V
.
Date de intrare
Fișierul de intrare patinaj.in
conține:
- pe prima linie numărul natural
C
care reprezintă numărul cerinței și poate avea una dintre valorile1
sau2
; - pe cea de-a doua linie, un număr natural
N
, care reprezintă atât numărul antrenorilor angajați, cât și al fetelor și al băieților legitimați la club; - pe fiecare dintre următoarele trei linii câte
N
valori, despărțite prin câte un spațiu. Pe cea de-a treia linie, acestea reprezintă codificările rezultatelor anterioare ale celorN
antrenori, pe cea de-a patra linie ele reprezintă codificările rezultatelor anterioare ale celorN
fete, iar valorile de pe cea de-a cincea linie reprezintă codificările rezultatelor anterioare ale celorN
băieți.
Date de ieșire
În fișierul text patinaj.out
se va afișa:
- pentru cerința
1
: numărul maxim de echipeNP
care pot fi înscrise la olimpiadă conform regulilor precizate mai sus; - pentru cerința
2
: două numere naturale,V
șiNV
, separate printr-un spațiu, reprezentând valoarea maximă a unui antrenor al clubului pentru care există cel puțin o pereche pe care o poate antrena și respectiv numărul variantelor în care clubul poate alege o echipă care poate fi pregătită de un antrenor cu valoareaV
, dacă se rezolvă cerința2
. În cazul în care clubul nu poate înscrie nicio pereche, se va afișa un singur număr:-1
.
Restricții și precizări
1 ≤ N ≤ 100.000
- fiecare dintre numerele citite de pe a treia, a patra și a cincea linie a fișierului este un număr natural cu cel mult 9 cifre.
- Pentru 51 de puncte,
C = 1
- Pentru 49 de puncte,
C = 2
Exemplul 1:
patinaj.in
1 4 8093 18305 20009 188 1803 3303331 909 91995 8017 20009 0 8017
patinaj.out
2
Explicație
Se pot forma cel mult 2
echipe. Prima ar putea fi formată din fata cu codificarea 1803
și băiatul cu codificarea 20009
și pregătită de antrenorul cu codificarea 20009
. A doua poate fi formată din fata 3303331
, băiatul 8017
și pregătită de antrenorul 18305
.
Exemplul 2:
patinaj.in
2 4 8093 18305 20009 188 1803 3303331 909 91995 8017 20009 0 8017
patinaj.out
17 4
Explicație
Clubul are 4
antrenori cu valorile 20=8+0+9+3
, 17=1+8+3+0+5
, 11=2+0+0+0+9
și 17=1+8+8
. Valoarea maximă este 20
, dar nu există o pereche pe care să o poată pregăti antrenorul cu valoarea 20
conform regulilor impuse. În schimb, un antrenor cu valoarea 17
ar putea pregăti o pereche înscrisă la olimpiadă. Sunt 4
variante de alegere a unei echipe pregătite de un antrenor cu valoarea 17
. Acestea ar putea avea în componență fata 3303331
și unul dintre cei doi băieți cu codificarea rezultatelor anterioare 8017
. O astfel de pereche ar putea fi pregătită de antrenorul 18305
sau de 188
.