Difference between revisions of "Clasa a VII-a lecția 29 - 19 mar 2020"

From Algopedia
Jump to navigationJump to search
(Created page with "= Concurs (de acasă) = [http://varena.ro/runda/2020-03-19-test-7 Concurs clasa a 7<sup>a</sup>] * [http://varena.ro/problema/uniform uniform] * [http://varena.ro/problema/dat...")
 
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
= Concurs (de acasă) =
+
= Tema - rezolvări =
 +
== Foto1 ==
 +
Problema [http://varena.ro/problema/foto1 foto1] a fost dată la OJI 2020 clasa a 7<sup>a</sup>. Este o problemă directă, relativ simplă, poate mai curînd de clasa a 6<sup>a</sup>.
 +
 
 +
=== Soluție forță brută ===
 +
Vom discuta doar cerința doi, deoarece cerința unu este banală, de introducere în clasa a șasea.
 +
 
 +
Partea mai grea a problemei este înțelegerea enunțului. Anume:
 +
 
 +
* Fulgerele sînt continue și merg de sus în jos.
 +
* Fulgerele sînt disjuncte. Ele nu se pot atinge nici măcar pe diagonală.
 +
* Fulgerele nu se pot despărți, ele sînt liniare.
 +
 
 +
Drept pentru care o soluție forță brută este următoarea:
 +
 
 +
<pre>
 +
Parcurgem matricea M pe linii și pe coloane, natural. Pentru fiecare element M[l][c]:
 +
 
 +
    Dacă M[l][c] este 1 și elementele de deasupra lui sînt 0 (M[l-1][c-1], M[l-1][c], M[l-1][c+1])
 +
 
 +
        Adaugă 1 la numărul de fulgere.
 +
 
 +
        Parcurge în jos acel fulger pentru a îi afla lungimea.
 +
</pre>
 +
 
 +
Nu detaliez parcurgerea fulgerului, ea se deplasează în jos pe acel element care este 1, adunînd 1 la lungime.
 +
 
 +
Ce complexitate are această soluție?
 +
 
 +
Parcurgerea matricei este ''O(N'''&middot;'''M)''. Parcurgerea unui fulger este ''O(N)'' și putem avea ''O(M)'' fulgere. Rezultă o complexitate de totală de ''O(N'''&middot;'''M)'' care este și optimă, deoarece trebuie să citim matricea.
 +
 
 +
Dar memoria folosită? Ea este evident ''O(N'''&middot;'''M)'' deoarece vom memora matricea. Mai exact, dacă elementele matricei sînt de tip caracter, memoria necesară este 10000 octeți, adică foarte puțin.
 +
 
 +
==== Simplificare ====
 +
Ca idee de simplificare a implementării forței brute, putem "reseta" elementele unui fulger, pe măsură ce îl parcurgem. Astfel, testul de început de fulger devine mai simplu, dacă elementul curent <tt>M[l][c] == 1</tt>.
 +
 
 +
=== Soluție cu (și) mai puțină memorie ===
 +
Dacă dimensiunile matricei ar fi ceva mai mari ne-am putea pune problema unei soluții care să nu memoreze matricea. Putem memora doar o linie din matrice. Vom parcurge matricea și, pentru fiecare element 1, ne întrebăm dacă este un început de fulger verificînd elementele din linia de mai sus. Putem, de asemenea, memora lungimile în acea linie, nu doar 0 sau 1.
 +
 
 +
Iată un algoritm posibil:
 +
 
 +
<pre>
 +
Citim matricea M pe linii și pe coloane, natural. Pentru fiecare linie l:
 +
 
 +
    Citim linia. Pentru fiecare coloană c citim elementul E și:
 +
 
 +
    Dacă E este 1
 +
 
 +
        Daca elementele de deasupra lui sînt 0 (L[c-1], L[c], L[c+1] - dar atenție, la L[c-1], ne trebuie valoarea veche)
 +
 
 +
            Adaugă unu la numărul de fulgere.
 +
 
 +
            L[c] primește 1 (lungimea actuală a fulgerului.
 +
 
 +
        Altfel înseamnă că doar un element din cele trei este diferit de zero, un fulger se continuă:
 +
 
 +
            L[c] primește 1 + L[i] (unde i poate fi c-1, c sau c+1)
 +
 
 +
        Dacă L[c] depășește lungimea maximă a unui fulger, reține valoarea
 +
 
 +
    Altfel
 +
 
 +
        L[c] = 0
 +
</pre>
 +
 
 +
Acest algoritm are aceeași complexitate în timp ca cel anterior, dar folosește doar ''O(M)'' memorie, adică circa 100 octeti (deoarece elementele matricei pot fi de tip <code>char</code>, lungimile nedepășind 100).
 +
 
 +
==== Considerente de implementare ====
 +
Algoritmul de mai sus se poate implementa mai ușor dacă observăm anumite lucruri:
 +
 
 +
* Nu avem nevoie să menținem două linii din matrice. Putem să memorăm valoarea veche din <tt>L[c-1]</tt>.
 +
* Valoarea de calculat <tt>L[c]</tt> nu are nevoie de teste (condiții). Ea este suma celor patru valori
 +
 
 +
(trei deasupra plus elementul citit) înmulțită cu elementul citit.
 +
 
 +
Iată un program bazat pe acest algoritm (33 de linii de cod efectiv):
 +
 
 +
<syntaxhighlight>#include <stdio.h>
 +
 
 +
#define MAXM 100
 +
 
 +
char linie[MAXM + 1]; // santinela la final
 +
 
 +
int main() {
 +
  FILE *fin, *fout;
 +
  int n, m, p, l, c, pixel, val, fdiag, nrnegru, max, f, h;
 +
 
 +
  fin = fopen( "foto1.in", "r" );
 +
  max = f = h = 0;
 +
  fscanf( fin, "%d%d%d ", &p, &n, &m );
 +
  for ( l = 0; l < n; l++ ) {
 +
    nrnegru = fdiag = 0;
 +
    for ( c = 0; c < m; c++ ) {
 +
      pixel = fgetc( fin ) - '0';
 +
      fgetc( fin );
 +
     
 +
      // cerinta 1
 +
      if ( (nrnegru = (nrnegru + 1 - pixel) * (1 - pixel)) > max )
 +
        max = nrnegru;
 +
     
 +
      // cerinta 2
 +
      val = pixel * (fdiag + linie[c] + linie[c + 1] + pixel);
 +
      fdiag = linie[c];
 +
      linie[c] = val;
 +
 
 +
      if ( (linie[c] = val) > h ) // inaltimea maxima
 +
        h = linie[c];
 +
      f += (linie[c] == 1);      // numarul de fulgere
 +
    }
 +
  }
 +
  fclose( fin );
 +
 
 +
  fout = fopen( "foto1.out", "w" );
 +
  if ( p == 1 )
 +
    fprintf( fout, "%d\n", max );
 +
  else
 +
    fprintf( fout, "%d %d\n", f, h );
 +
  fclose( fout );
 +
 
 +
  return 0;
 +
}</syntaxhighlight>
 +
 
 +
== Wind ==
 +
Problema [http://varena.ro/problema/wind wind] a fost dată la OJI 2020 clasa a 7<sup>a</sup>. Este o problemă medie spre ușoară ca dificultate, partea cea mai grea fiind ordinea și disciplina în rezolvare, algoritmul nepunînd probleme (sper).
 +
 
 +
Comentariu: v-ați gîndit de ce problema se cheamă ''wind'', un titlu în engleză?
 +
 
 +
Indiciu: gîndiți-vă care ar fi fost alternativa și de ce nu e preferabilă :)
 +
 
 +
=== Soluție ===
 +
Vom discuta doar despre cerința 2, deoarece punctul unu cere găsirea numărului de divizori ai unui număr, problemă banală de clasa a cincea.
 +
 
 +
Problema cere găsirea unei împărțiri a unui vector de elemente pozitive și negative în subvectori adiacenți de lungime egală, care să minimizeze diferența între cea mai mare sumă a unui subvector și cea mai mică sumă.
 +
 
 +
'''Observații''':
 +
 
 +
* Putem calcula valoarea de minimizat într-o parcurgere a vectorului, deci în ''O(N)''.
 +
* Nu vom lua în calcul decît parcurgeri în care putem crea subvectori egali - deci pentru divizorii lui ''N''.
 +
* N are maxim 5 cifre.
 +
* Numărul maxim de de divizori ai unui număr cu 5 cifre este 128, conform [http://oeis.org/A066150 numărul maxim de divizori ai numerelor de n cifre].
 +
* Timpul este 0.3s
 +
 
 +
De aici rezultă că o forță brută, care pentru fiecare divizor calculează diferența, se va încadra în timp, ea efectuînd circa 128'''&middot;'''100000 = 12.8 milioane de operații.
 +
 
 +
Problema constă, precum spuneam, în implementare, algoritmul fiind forță brută. La ce trebuie să fim atenți?
 +
 
 +
* La enunț! Nu este imediat clar că trebuie să afișăm cel mai mare indice al primului element din subvectorul de sumă maximă.
 +
* Să nu creăm cazuri particulare.
 +
* Să scriem cît mai clar și mai simplu codul, deoarece avem multe detalii de care trebuie să ținem cont.
 +
* Să facem parsing! Vom citi 100000 de numere de 9 cifre, plus un separator, deci circa 1MB. Putem cîștiga 0.1s doar din o citire atentă. Atunci cînd avem 0.3s cu totul, devine semnificativ. La olimpiadă aș implementa parsing-ul simplu, cu <code>fgetc()</code>. Nu aș risca parsing-ul cel mai eficient, cu <code>fread()</code>, dar dacă vă simțiți confortabil, de ce nu?
 +
 
 +
O implementare eficientă, cu parsing simplu, nu ar trebui să depășească 70 de linii de cod efectiv.
 +
 
 +
Ce complexitate are această soluție?
 +
 
 +
Precum am discutat, timpul va fi ''O(d(N)'''&middot;'''N)'', unde ''d(N)'' este numărul de divizori ai lui ''N'', în cazul nostru maxim 128.
 +
 
 +
Memoria folosită este cea necesară pentru a stoca valorile din vector, adică ''O(N)'', sau, mai exact, 400KB, mult mai puțină decît cea acordată, de 16MB.
 +
 
 +
=== Soluție mai rapidă ===
 +
Precum am discutat în timpul lecției, se poate și mai bine. Mai exact, putem să calculăm sumele energiilor fiecărui oraș în ''O(1)'' folosind sume parțiale ale energiilor, adică ''O(k)'' pentru ''k'' orașe.
 +
 
 +
Ce complexitate are această soluție? Să analizăm: pentru ''k'' orașe construite vom efectua ''O(k)'' calcule. Dar numărul de orașe trebuie să fie divizor al lui ''N''. În total vom calcula, deci, ''&sigma;(N)'' calcule, unde ''&sigma;(N)'' este suma divizorilor lui ''N''. Această sumă este ''O(N log log N)''. Nu vom demonstra, deoarece depășește nivelul acestui curs.
 +
 
 +
Concluzie: timpul de execuție al acestei soluții este ''O(N log log N)''. Din punct de vedere practic, pentru ''N'' maxim din problemă, 100000, ''log log N'' este ca și constant, deci putem considera algoritmul ca fiind liniar, ceea ce duce la circa 400000 de operații (considerînd ''log log'' 100000 ca aproximativ 4).
 +
 
 +
Algoritmul acesta va fi, deci, de cîteva ori mai rapid. Din păcate problema nu permite departajarea între soluții. În general, în probleme de concurs, este greu să distingem între timpi ''O(N)'' și ''O(N log N)'' sau ''O(N log log N)''. Nu este imposibil, însă!
 +
 
 +
Pentru ca timpii să difere măsurabil între un algoritm ''O(N)'' și unul ''O(N log N)'' trebuie ca:
 +
* ''N'' să fie mare (banal :)
 +
* Intrarea să fie mai mică decît ''O(N)'', preferabil mult mai mică, de exemplu ''O(1)'' sau ''O(sqrt(N))''.
 +
 
 +
Descrierea soluției comisiei nu analizează complexitatea algoritmului prezentat. Păcat, e un calcul interesant.
 +
 
 +
Iată o soluție bazată pe ideile de mai sus (66 linii de cod efectiv, din care 54 fără parsing):
 +
 
 +
<syntaxhighlight>#include <stdio.h>
 +
#include <ctype.h>
 +
 
 +
#define MAXN 100000
 +
#define INFINIT (1000000000LL * MAXN)
 +
 
 +
FILE *fin, *fout;
 +
int energie[MAXN + 1];
 +
 
 +
// citire intreg cu semn
 +
int readInt() {
 +
  int ch, res = 0, semn = 1;
 +
 
 +
  while ( isspace( ch = fgetc( fin ) ) );
 +
  if ( ch == '-' ) {
 +
    semn = -1;
 +
    ch = fgetc( fin );
 +
  }
 +
  do
 +
    res = 10 * res + ch - '0';
 +
  while ( isdigit( ch = fgetc( fin ) ) );
 +
 
 +
  return semn * res;
 +
}
 +
 
 +
int main() {
 +
  int n, c, i, k, x, e, emax, d, pas;
 +
  long long s, smin, smax, difmin;
 +
 
 +
  fin = fopen( "wind.in", "r" );
 +
  fout = fopen( "wind.out", "w" );
 +
  c = readInt();
 +
  n = readInt();
 +
  if ( c == 1 ) { // cerinta 1: numarul de divizori ai lui n minus 1
 +
    d = -1;      // 1 nu este divizor acceptat de problema
 +
    for ( k = 1; k * k < n; k++ )
 +
      d += 2 * (n % k == 0); // pentru fiecare pereche de divizori adunam 2
 +
    d += (k * k == n);      // daca e patrat perfect mai avem un divizor
 +
    fprintf( fout, "%d\n", d );
 +
  } else { // cerinta 2: gruparea optima a oraselor
 +
    for ( k = 1; k <= n; k++ )                // citim energiile
 +
      energie[k] = energie[k - 1] + readInt(); // si calculam sumele partiale
 +
 
 +
    difmin = INFINIT;
 +
    x = e = emax = 0; // initializari pentru a calma warning-ul compilatorului
 +
    for ( d = 1; d * d <= n; d++ ) // pentru fiecare potential divizor
 +
      if ( n % d == 0 ) {          // am gasit o pereche de divizori (d, n / d)
 +
        k = d;                    // k este marimea unui oras
 +
        for ( pas = (d == 1); pas < 2; pas++ ) { // doi divizori, doi pasi
 +
          smin = INFINIT;  // suma minima (energia unui oras)
 +
          smax = -INFINIT;  // suma maxima (energia unui oras)
 +
          // pentru fiecare oras variaza i din k in k - marimea unui oras
 +
          for ( i = n; i >= k; i -= k ) {
 +
            s = energie[i] - energie[i - k]; // suma energiei orasului
 +
           
 +
            if ( s < smin )  // retinem suma minima
 +
              smin = s;
 +
            if ( s > smax ) { // retinem suma maxima si indicele ei de inceput
 +
              smax = s;
 +
              emax = i - k;
 +
            }
 +
          }
 +
          // dezechilibrul e mai mic, sau numarul de orase mai mare?
 +
          if ( smax - smin < difmin ||
 +
              (smax - smin == difmin && n / k > x) ) {
 +
            difmin = smax - smin; // retinem noua impartire
 +
            x = n / k;
 +
            e = emax;
 +
          }
 +
          k = n / d;              // trecem la celalalt divizor din pereche
 +
        }
 +
      }
 +
    fprintf( fout, "%d %d\n", x, e + 1 );
 +
  }
 +
  fclose( fin );
 +
  fclose( fout );
 +
 
 +
  return 0;
 +
}</syntaxhighlight>
 +
 
 +
Rezolvări aici [http://solpedia.francu.com/wiki/index.php/Clasa_a_VII-a_lec%C8%9Bia_28_-_12_mar_2020].
 +
 
 +
= Lecție - concurs (de acasă) =
 
[http://varena.ro/runda/2020-03-19-test-7 Concurs clasa a 7<sup>a</sup>]
 
[http://varena.ro/runda/2020-03-19-test-7 Concurs clasa a 7<sup>a</sup>]
 
* [http://varena.ro/problema/uniform uniform]
 
* [http://varena.ro/problema/uniform uniform]

Latest revision as of 18:50, 26 March 2020

Tema - rezolvări

Foto1

Problema foto1 a fost dată la OJI 2020 clasa a 7a. Este o problemă directă, relativ simplă, poate mai curînd de clasa a 6a.

Soluție forță brută

Vom discuta doar cerința doi, deoarece cerința unu este banală, de introducere în clasa a șasea.

Partea mai grea a problemei este înțelegerea enunțului. Anume:

  • Fulgerele sînt continue și merg de sus în jos.
  • Fulgerele sînt disjuncte. Ele nu se pot atinge nici măcar pe diagonală.
  • Fulgerele nu se pot despărți, ele sînt liniare.

Drept pentru care o soluție forță brută este următoarea:

Parcurgem matricea M pe linii și pe coloane, natural. Pentru fiecare element M[l][c]:

    Dacă M[l][c] este 1 și elementele de deasupra lui sînt 0 (M[l-1][c-1], M[l-1][c], M[l-1][c+1])

        Adaugă 1 la numărul de fulgere.

        Parcurge în jos acel fulger pentru a îi afla lungimea.

Nu detaliez parcurgerea fulgerului, ea se deplasează în jos pe acel element care este 1, adunînd 1 la lungime.

Ce complexitate are această soluție?

Parcurgerea matricei este O(N·M). Parcurgerea unui fulger este O(N) și putem avea O(M) fulgere. Rezultă o complexitate de totală de O(N·M) care este și optimă, deoarece trebuie să citim matricea.

Dar memoria folosită? Ea este evident O(N·M) deoarece vom memora matricea. Mai exact, dacă elementele matricei sînt de tip caracter, memoria necesară este 10000 octeți, adică foarte puțin.

Simplificare

Ca idee de simplificare a implementării forței brute, putem "reseta" elementele unui fulger, pe măsură ce îl parcurgem. Astfel, testul de început de fulger devine mai simplu, dacă elementul curent M[l][c] == 1.

Soluție cu (și) mai puțină memorie

Dacă dimensiunile matricei ar fi ceva mai mari ne-am putea pune problema unei soluții care să nu memoreze matricea. Putem memora doar o linie din matrice. Vom parcurge matricea și, pentru fiecare element 1, ne întrebăm dacă este un început de fulger verificînd elementele din linia de mai sus. Putem, de asemenea, memora lungimile în acea linie, nu doar 0 sau 1.

Iată un algoritm posibil:

Citim matricea M pe linii și pe coloane, natural. Pentru fiecare linie l:

    Citim linia. Pentru fiecare coloană c citim elementul E și:

    Dacă E este 1

        Daca elementele de deasupra lui sînt 0 (L[c-1], L[c], L[c+1] - dar atenție, la L[c-1], ne trebuie valoarea veche)

            Adaugă unu la numărul de fulgere.

            L[c] primește 1 (lungimea actuală a fulgerului.

        Altfel înseamnă că doar un element din cele trei este diferit de zero, un fulger se continuă:

            L[c] primește 1 + L[i] (unde i poate fi c-1, c sau c+1)

        Dacă L[c] depășește lungimea maximă a unui fulger, reține valoarea

     Altfel

        L[c] = 0

Acest algoritm are aceeași complexitate în timp ca cel anterior, dar folosește doar O(M) memorie, adică circa 100 octeti (deoarece elementele matricei pot fi de tip char, lungimile nedepășind 100).

Considerente de implementare

Algoritmul de mai sus se poate implementa mai ușor dacă observăm anumite lucruri:

  • Nu avem nevoie să menținem două linii din matrice. Putem să memorăm valoarea veche din L[c-1].
  • Valoarea de calculat L[c] nu are nevoie de teste (condiții). Ea este suma celor patru valori

(trei deasupra plus elementul citit) înmulțită cu elementul citit.

Iată un program bazat pe acest algoritm (33 de linii de cod efectiv):

#include <stdio.h>

#define MAXM 100

char linie[MAXM + 1]; // santinela la final

int main() {
  FILE *fin, *fout;
  int n, m, p, l, c, pixel, val, fdiag, nrnegru, max, f, h;

  fin = fopen( "foto1.in", "r" );
  max = f = h = 0;
  fscanf( fin, "%d%d%d ", &p, &n, &m );
  for ( l = 0; l < n; l++ ) {
    nrnegru = fdiag = 0;
    for ( c = 0; c < m; c++ ) {
      pixel = fgetc( fin ) - '0';
      fgetc( fin );
      
      // cerinta 1
      if ( (nrnegru = (nrnegru + 1 - pixel) * (1 - pixel)) > max )
        max = nrnegru;
      
      // cerinta 2
      val = pixel * (fdiag + linie[c] + linie[c + 1] + pixel);
      fdiag = linie[c];
      linie[c] = val;

      if ( (linie[c] = val) > h ) // inaltimea maxima
        h = linie[c];
      f += (linie[c] == 1);       // numarul de fulgere
    }
  }
  fclose( fin );

  fout = fopen( "foto1.out", "w" );
  if ( p == 1 )
    fprintf( fout, "%d\n", max );
  else
    fprintf( fout, "%d %d\n", f, h );
  fclose( fout );

  return 0;
}

Wind

Problema wind a fost dată la OJI 2020 clasa a 7a. Este o problemă medie spre ușoară ca dificultate, partea cea mai grea fiind ordinea și disciplina în rezolvare, algoritmul nepunînd probleme (sper).

Comentariu: v-ați gîndit de ce problema se cheamă wind, un titlu în engleză?

Indiciu: gîndiți-vă care ar fi fost alternativa și de ce nu e preferabilă :)

Soluție

Vom discuta doar despre cerința 2, deoarece punctul unu cere găsirea numărului de divizori ai unui număr, problemă banală de clasa a cincea.

Problema cere găsirea unei împărțiri a unui vector de elemente pozitive și negative în subvectori adiacenți de lungime egală, care să minimizeze diferența între cea mai mare sumă a unui subvector și cea mai mică sumă.

Observații:

  • Putem calcula valoarea de minimizat într-o parcurgere a vectorului, deci în O(N).
  • Nu vom lua în calcul decît parcurgeri în care putem crea subvectori egali - deci pentru divizorii lui N.
  • N are maxim 5 cifre.
  • Numărul maxim de de divizori ai unui număr cu 5 cifre este 128, conform numărul maxim de divizori ai numerelor de n cifre.
  • Timpul este 0.3s

De aici rezultă că o forță brută, care pentru fiecare divizor calculează diferența, se va încadra în timp, ea efectuînd circa 128·100000 = 12.8 milioane de operații.

Problema constă, precum spuneam, în implementare, algoritmul fiind forță brută. La ce trebuie să fim atenți?

  • La enunț! Nu este imediat clar că trebuie să afișăm cel mai mare indice al primului element din subvectorul de sumă maximă.
  • Să nu creăm cazuri particulare.
  • Să scriem cît mai clar și mai simplu codul, deoarece avem multe detalii de care trebuie să ținem cont.
  • Să facem parsing! Vom citi 100000 de numere de 9 cifre, plus un separator, deci circa 1MB. Putem cîștiga 0.1s doar din o citire atentă. Atunci cînd avem 0.3s cu totul, devine semnificativ. La olimpiadă aș implementa parsing-ul simplu, cu fgetc(). Nu aș risca parsing-ul cel mai eficient, cu fread(), dar dacă vă simțiți confortabil, de ce nu?

O implementare eficientă, cu parsing simplu, nu ar trebui să depășească 70 de linii de cod efectiv.

Ce complexitate are această soluție?

Precum am discutat, timpul va fi O(d(N)·N), unde d(N) este numărul de divizori ai lui N, în cazul nostru maxim 128.

Memoria folosită este cea necesară pentru a stoca valorile din vector, adică O(N), sau, mai exact, 400KB, mult mai puțină decît cea acordată, de 16MB.

Soluție mai rapidă

Precum am discutat în timpul lecției, se poate și mai bine. Mai exact, putem să calculăm sumele energiilor fiecărui oraș în O(1) folosind sume parțiale ale energiilor, adică O(k) pentru k orașe.

Ce complexitate are această soluție? Să analizăm: pentru k orașe construite vom efectua O(k) calcule. Dar numărul de orașe trebuie să fie divizor al lui N. În total vom calcula, deci, σ(N) calcule, unde σ(N) este suma divizorilor lui N. Această sumă este O(N log log N). Nu vom demonstra, deoarece depășește nivelul acestui curs.

Concluzie: timpul de execuție al acestei soluții este O(N log log N). Din punct de vedere practic, pentru N maxim din problemă, 100000, log log N este ca și constant, deci putem considera algoritmul ca fiind liniar, ceea ce duce la circa 400000 de operații (considerînd log log 100000 ca aproximativ 4).

Algoritmul acesta va fi, deci, de cîteva ori mai rapid. Din păcate problema nu permite departajarea între soluții. În general, în probleme de concurs, este greu să distingem între timpi O(N) și O(N log N) sau O(N log log N). Nu este imposibil, însă!

Pentru ca timpii să difere măsurabil între un algoritm O(N) și unul O(N log N) trebuie ca:

  • N să fie mare (banal :)
  • Intrarea să fie mai mică decît O(N), preferabil mult mai mică, de exemplu O(1) sau O(sqrt(N)).

Descrierea soluției comisiei nu analizează complexitatea algoritmului prezentat. Păcat, e un calcul interesant.

Iată o soluție bazată pe ideile de mai sus (66 linii de cod efectiv, din care 54 fără parsing):

#include <stdio.h>
#include <ctype.h>

#define MAXN 100000
#define INFINIT (1000000000LL * MAXN)

FILE *fin, *fout;
int energie[MAXN + 1];

// citire intreg cu semn
int readInt() {
  int ch, res = 0, semn = 1;

  while ( isspace( ch = fgetc( fin ) ) );
  if ( ch == '-' ) {
    semn = -1;
    ch = fgetc( fin );
  }
  do
    res = 10 * res + ch - '0';
  while ( isdigit( ch = fgetc( fin ) ) );

  return semn * res;
}

int main() {
  int n, c, i, k, x, e, emax, d, pas;
  long long s, smin, smax, difmin;

  fin = fopen( "wind.in", "r" );
  fout = fopen( "wind.out", "w" );
  c = readInt();
  n = readInt();
  if ( c == 1 ) { // cerinta 1: numarul de divizori ai lui n minus 1
    d = -1;       // 1 nu este divizor acceptat de problema
    for ( k = 1; k * k < n; k++ )
      d += 2 * (n % k == 0); // pentru fiecare pereche de divizori adunam 2
    d += (k * k == n);       // daca e patrat perfect mai avem un divizor
    fprintf( fout, "%d\n", d );
  } else { // cerinta 2: gruparea optima a oraselor
    for ( k = 1; k <= n; k++ )                 // citim energiile
      energie[k] = energie[k - 1] + readInt(); // si calculam sumele partiale

    difmin = INFINIT;
    x = e = emax = 0; // initializari pentru a calma warning-ul compilatorului
    for ( d = 1; d * d <= n; d++ ) // pentru fiecare potential divizor
      if ( n % d == 0 ) {          // am gasit o pereche de divizori (d, n / d)
        k = d;                     // k este marimea unui oras
        for ( pas = (d == 1); pas < 2; pas++ ) { // doi divizori, doi pasi
          smin = INFINIT;   // suma minima (energia unui oras)
          smax = -INFINIT;  // suma maxima (energia unui oras)
          // pentru fiecare oras variaza i din k in k - marimea unui oras
          for ( i = n; i >= k; i -= k ) { 
            s = energie[i] - energie[i - k]; // suma energiei orasului
            
            if ( s < smin )   // retinem suma minima
              smin = s;
            if ( s > smax ) { // retinem suma maxima si indicele ei de inceput
              smax = s;
              emax = i - k;
            }
          }
          // dezechilibrul e mai mic, sau numarul de orase mai mare?
          if ( smax - smin < difmin || 
               (smax - smin == difmin && n / k > x) ) { 
            difmin = smax - smin; // retinem noua impartire
            x = n / k;
            e = emax;
          }
          k = n / d;              // trecem la celalalt divizor din pereche
        }
      }
    fprintf( fout, "%d %d\n", x, e + 1 );
  }
  fclose( fin );
  fclose( fout );

  return 0;
}

Rezolvări aici [1].

Lecție - concurs (de acasă)

Concurs clasa a 7a

Temă

Problemele au fost adăugate la tema 29.

Rezolvări aici [2].