3436 - Wind

Enunt

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ţa

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:

• afișează numărul M de moduri în care se pot grupa cele N centrale pentru construcția corectă de orașe;
• 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 şi precizări

• 2 ≤ N ≤ 100000, N număr natural;
• Numerele afișate pe ecranele centralelor sunt numere întregi formate din cel mult nouă cifre;
• Se vor construi minimum 2 orașe;
• În concurs, pentru rezolvarea cerinței 1 s-au acordat 20 de puncte, pentru rezolvarea cerinței 2 s-au acordat 70 de puncte. Pe site se acordă 10 puncte pentru exemple.

Exemplul 1

wind.in

1
12
2 4 -5 12 3 5 -6 4 5 7 -8 2

wind.out

5

Explicație

Cerința este 1. Centralele eoliene se pot grupa câte 1, câte 2, câte 3, câte 4 sau câte 6.

Exemplul 2

wind.in

2
12
2 4 -5 12 3 5 -6 4 5 7 -8 2

wind.out

3 1

Explicație

Cerința este 2. Posibilitățile de grupare:

• câte 1 centrală/oraș (sumele sunt 2, 4, -5, …, 2; P(12)=20=12-(-8));
• câte 2 centrale/oraș (sumele sunt: 6, 7, 8, -2, 12, -6; P(6)=18=12-(-6));
• câte 3 centrale/oraș (sumele sunt: 1, 20, 3, 1; P(4)=19=20-1);
• câte 4 centrale/oraș (sumele sunt: 13, 6, 6; P(3)=7=13-6);
• câte 6 centrale/oraș (sumele sunt: 21 si 4; P(2)=17=21-4).

Astfel, factorul de dezechilibru minim este P(3)=7, deci X=3. Pentru această grupare a centralelor, orașul cu cantitatea maximă de energie (13) corespunde primului grup, care începe cu centrala etichetată cu E=1.

Rezolvare

<syntaxhighlight lang="python" line> def calculate_divisors(n):

   divisors = []
   for i in range(1, int(n**0.5) + 1):
       if n % i == 0:
           divisors.append(i)
           if i != n // i:
               divisors.append(n // i)
   return divisors

def imbalance_factor(groups):

   max_energy = max(sum(group) for group in groups)
   min_energy = min(sum(group) for group in groups)
   return max_energy - min_energy

def main():

   task = int(input())
   N = int(input())
   energies = list(map(int, input().split()))

   if task == 1:
       divisors = calculate_divisors(N)
       print(len(divisors))
   elif task == 2:
       divisors = calculate_divisors(N)
       min_imbalance = float('inf')
       max_cities = 0
       best_start = 0

       for divisor in divisors:
           groups = [energies[i:i + divisor] for i in range(0, N, divisor)]
           imbalance = imbalance_factor(groups)
           if imbalance < min_imbalance:
               min_imbalance = imbalance
               max_cities = len(groups)
               best_start = sum(groups[0])

       print(max_cities, best_start)

if __name__ == "__main__":

   main()

</syntaxhighlight>