Lista de probleme 2

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.

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.

O fotografie alb-negru a surprins imaginea fulgerelor pe cerul întunecat în timpul unei furtuni electrice. Mărită, fotografia arată ca un caroiaj format din mici pătrate identice, albe sau negre, dispuse alăturat pe N rânduri și M coloane, câte M pe fiecare rând. Pătratele albe formează fulgerele din fotografie, iar pătratele negre reprezintă cerul. În fotografie, nu există două pătrate albe dispuse alăturat pe același rând. Un fulger este format din pătrate albe situate pe rânduri consecutive care respectă următoarele condiții: a) pătratele albe situate pe două rânduri consecutive au un vârf comun sau o latură comună; b) un fulger poate avea un singur pătrat alb pe un rând. În fotografie, fulgerele sunt distincte, ele neavând pătrate albe cu laturi sau vârfuri comune. Înălțimea unui fulger este dată de numărul de pătrate albe ale acelui fulger.
Scrieți un program care citește numerele N și M, cele N*M elemente ale tabloului T care codifică fotografia și rezolvă următoarele cerințe:

1. afișează numărul maxim P de pătrate negre dispuse alăturat pe un rând în fotografie;
2. afișează numărul F de fulgere și înălțimea maximă H a unui fulger din fotografie.