Fișierul intrare/ieșire	wind.in, wind.out	Sursă	OJI 2020 clasa a 7-a
Autor	Flavius Boian	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	0.6 sec	Limită de memorie	16384 KB
Scorul tău	N/A	Dificultate	2

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Wind (clasa a 7-a)

Domnul Vânt a pus pe marginea unei șosele N centrale eoliene, dintre care unele produc energie electrică, iar altele, deocamdată, doar consumă energie. El a etichetat centralele cu numerele naturale distincte de la 1 la N, în ordinea poziționării lor pe șosea. Fiecare centrală eoliană are la bază un ecran pe care este afișat un număr întreg, reprezentând cantitatea de energie pe care o produce (dacă numărul este pozitiv) sau pe care o consumă (dacă numărul este negativ).

Pentru a construi corect k orașe de-a lungul acestei șosele, un arhitect trebuie să aibă în vedere că:

• fiecărui oraș îi va fi atribuit câte un grup format din centrale eoliene vecine pe șosea, toate grupurile având același număr de centrale;
• cantitatea de energie repartizată unui oraș este egală cu suma numerelor afișate pe ecranele centralelor eoliene din grupul atribuit; uneori este posibil ca, deocamdată, suma obținută să fie negativă;
• fiecare dintre cele N centrale eoliene trebuie să fie atribuită unui oraș;
• factorul de dezechilibru, notat cu P(k), este valoarea maximă a diferenței dintre energiile repartizate oricăror două orașe diferite, dintre cele k.

Cerință

Scrieți un program care citește numărul N, valorile afișate pe cele N ecrane ale centralelor eoliene și rezolvă următoarele două cerințe:

1. afișează numărul M de moduri în care se pot grupa cele N centrale pentru construcția corectă de orașe;
2. afișează numărul maxim X de orașe ce pot fi construite corect, dintre cele care au factorul de dezechilibru minim, precum și eticheta E a primei centrale eoliene atribuită orașului cu cea mai mare cantitate de energie repartizată, dintre cele X orașe; dacă sunt mai multe astfel de orașe, se ia în considerare cel care are atribuite centrale etichetate cu numere mai mari.

Date de intrare

Fișierul de intrare wind.in conține pe prima linie un număr natural C reprezentând cerința care trebuie rezolvată (1 sau 2). A doua linie a fișierului conține un număr natural N, cu semnificația din enunț. A treia linie din fișier conține N numere întregi, separate prin câte un spațiu, reprezentând valorile afișate pe cele N ecrane ale centralelor eoliene, în ordinea poziționării acestora pe șosea.

Date de ieșire

Fișierul de ieșire wind.out va conține pe prima linie:

• dacă C=1, numărul natural M, reprezentând răspunsul la cerința 1;
• dacă C=2, cele două numere naturale X și E, în această ordine, separate printr-un singur spațiu, reprezentând răspunsul la cerința 2.

Restricții

• 2 ≤ N ≤ 100000, N număr natural;
• Numerele afișate pe ecranele centralelor sunt numere întregi formate din cel mult 9 cifre;
• Se vor construi minimum 2 orașe;
• Pentru rezolvarea cerinței 1 se acordă 20 de puncte, pentru rezolvarea cerinței 2 se acordă 70 de puncte (35 de puncte pentru X și 35 de puncte pentru E).

Exemple