Editing 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
<br>

== 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
<br>

== 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>