Rezolvare completă PbInfo #3436 Wind

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:

  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 ș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.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Wind:

#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream f("wind.in");
ofstream g("wind.out");

long long d,smin,smax,divx,poz,pozmax,minimm=99999999,C,n,i,k,s[200001],v[10001],x,j,dif,minim=99999999,numar,gasit;
int main()
{
    f>>C;
    if(C==1)
    {
        f>>n;
        for(i=1; i*i<=n; i++)
            if(n%i==0)
            {
                k++;
                if(i!=n/i)
                    k++;
            }
        g<<k-1;
    }
    else
    {
        f>>n;
        for(i=1; i<=n; i++)
        {
            f>>x;
            s[i]=s[i-1]+x;
        }
        for(i=1; i*i<=n; i++)
            if(n%i==0)
            {
                k++;
                v[k]=i;
                if(i!=n/i and n/i!=n)
                {
                    k++;
                    v[k]=n/i;
                }
            }

        for(i=1; i<=k; i++)
        {
            x=v[i];
            smin=99999999999;
            smax=-99999999999;

            for(j=x; j<=n; j=j+x)
            {
                if ( s[j]-s[j-x]< smin)
                    smin=s[j]-s[j-x];
                if (s[j]-s[j-x] >= smax)
                {
                    smax=s[j]-s[j-x];
                    poz=j-x+1;
                }
            }
            dif=smax-smin;
            if(dif<minimm)
            {
                minimm=dif;
                divx=x;
                pozmax=poz;
            }
            else if(dif==minimm && x<divx)
            {
                divx=x;
                pozmax=poz;
            }
        }
        g<<n/divx<<" "<<pozmax;
    }

    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #3436 Wind

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3436 Wind de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!