Clasa a VI-a lecția 29 - 4 apr 2019

From Algopedia
Jump to: navigation, search

Anunțuri

Reluăm concursul de duminică

Duminică 7 aprilie la ora 15:00 vom avea un concurs de pregătire olimpiadă ce va dura patru ore. Problemele de concurs se vor transfera la temă.

Tema 28 - rezolvări

Problema atlantis

Problema atlantis a fost dată la Infotehnium 2019 clasa a 6a avansați.

Ea poate părea la prima vedere o problemă de simulare, însă o rezolvare clasică, ce simulează scufundarea, va depăși timpul pe teste mari. Să vedem rezolvările la cele trei puncte.

Rezolvare cerința unu

Sper că este simplă: deoarece insula se scufundă cu 1m/minut rezultă că după k minute vom avea sub apă toți munții cu înălțime strict mai mică decât k. Vom număra, deci, înălțimile mai mici decât k.

Rezolvare cerința doi

Dacă traducem cerința în limbaj informatic se cere să afișăm indicii înălțimilor în ordinea crescătoare a înălțimilor. Pentru aceasta putem construi din vectorul înălțimilor citite la intrare un vector de frecvență al lor, în care stocăm indicii (ordinea lor de apariție la intrare). Putem face acest lucru deoarece înălțimile munților sunt distincte. Apoi parcurgem acest vector de frecvență și, unde avem elemente nenule, afișăm conținutul vectorului, adică numărul de apariție la intrare al acelei înălțimi.

O soluție alternativă este să sortăm perechile (înălțime, indice) după înălțimi, iar apoi să parcurgem perechile afișând indicii. Pentru a ne încadra în timp și a trece toate testele va trebui folosită o sortare rapidă (quicksort, heapshort, etc.) ceea ce face această rezolvare de nivel mai mare decât clasa a 6a. O soluție cu sortare prin selecție (în lipsă de inspirație) va lua puncte pentru teste mici și medii.

Rezolvare cerința trei

Dacă traducem cerința în limbaj informatic se cere să afișăm pentru fiecare înălțime de la intrare a cîta este ea în ordinea înălțimilor.

Deoarece avem calculat vectorul de frecvență de la punctul 2 putem parcurge vectorul înlocuind valorile nenule (ce reprezintă înălțimi existente la intrare) cu valori crescătoare, reprezentînd chiar ordinea acelor înălțimi. Apoi parcurgem vectorul înălțimilor (memorat la citire) afișând pentru fiecare înălțime valoarea memorată în vectorul de frecvență.

Într-o soluție prin sortare rapidă (peste nivelul clasei a șasea) trebuie ca după punctul 2 să parcurgem perechile sortate după înălțimi și pentru fiecare pereche (înălțime, indice) vom merge la poziția indice în vectorul de rezultate și vom stoca valori crescătoare. Deoarece nu mai avem nevoie de înălțimi putem refolosi acel vector. Apoi afișam vectorul rezultat (al înălțimilor, dacă refolosim acel vector).

O posibilitate mai ineficientă, dar care va lua și ea punctaj maxim, este să memorăm pentru fiecare înălțime ordinea sa în vectorul sortat, apoi să resortăm tripleții (înălțime, indice, ordine) după indice, apoi să afișăm valoarea de ordine în vectorul resortat.

Iată o soluție ce implementează prima idee, folosind un vector de frecvență:

// Rezolvare O(n+maxnr) (100p)
// - cerintele 2 si 3 cu vectori de frecventa
#define HMAX 100000

int hv[HMAX];    // vectorul de inaltimi ale muntilor
int f[HMAX + 1]; // vectorul de frecventa al inaltimii muntilor

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  int n, c, k, i, h, scufundati;

  fin = fopen( "atlantis.in", "r" );
  fscanf( fin, "%d%d%d", &c, &n, &k );
  scufundati = 0;
  for ( i = 0; i < n; i++ ) {
    fscanf( fin, "%d", &hv[i] );
    f[hv[i]] = i+1;
    if ( hv[i] < k )
      scufundati++;
  }
  fclose( fin );

  fout = fopen( "atlantis.out", "w" );
  if ( c == 1 )
    fprintf( fout, "%d\n", scufundati );
  else if ( c == 2 ){
    for ( h = 1; h <= HMAX; h++ )
      if ( f[h] > 0 )
        fprintf( fout, "%d ", f[h] );
    fprintf( fout, "\n" );
  } else {
    i = 1;
    for ( h = 1; h <= HMAX; h++ )
      if ( f[h] > 0 )
        f[h] = i++;
    for ( i = 0; i < n; i++ )
      fprintf( fout, "%d ", f[hv[i]] );
    fprintf( fout, "\n" );
  }
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție?

Punctul 1 este O(n), iar punctele 2 și 3 sînt O(n + hmax).

Memoria folosită este O(n + hmax), iar din calcule rezultă circa 800KB.

Problema pomi

Problema pomi a fost dată la Infotehnium 2019 clasa a 6a avansați.

Să vedem rezolvarea, pe puncte.

Considerente generale

Ca aproape întotdeauna este mai simplu să lucrăm cu numere de linie și de coloană numerotate începînd de la zero, nu cu unu. Tot ce avem de făcut pentru aceasta este să scădem unu din L și C, coordonatele citite ale pomului P.

Rezolvare cerința unu

Se cere să calculăm lungimea diagonalelor care trec prin pomul P.

O rezolvare ineficientă, dar care va lua punctaj maxim, este să parcurgem toți pomii și să testăm dacă ei se află pe aceeași diagonală cu pomul P. Un pom X de coordonate Lx și Cx se află pe aceeași diagonală cu pomul P de coordonate Lp și Cp dacă |Lx-Lp|=|Cx-Cp| unde am notat cu bare verticale valoarea absolută, sau modulul expresiei. Ce complexitate are această soluție?

Desigur O(M·N), ceea ce este suficient pentru a se încadra în timp.

O optimizare a acestei soluții ar fi să ne deplasăm doar de-a lungul diagonalelor, pînă la ieșirea din matrice, adunînd unu pentru fiecare pom parcurs. Această soluție este O(M + N).

Însă folosind matematică vom obține o soluție O(1): putem împărți diagonalele în patru segmente: stânga-sus, dreapta-sus, stânga-jos și dreapta-jos. Pentru a calcula segmentul stânga-sus observăm că dacă ne-am deplasa de-a lungul acestui segment atât linia cât și coloana scad. Ele vor scădea pâna ce fie linia, fie coloana, devin zero. Vom avea, deci, un număr de pomi egal cu minimul dintre L și C.

Similar, pentru segmentul dreapta-sus, la fiecare deplasare pe diagonală coloana crește cu unu, iar linia scade cu unu. Numărul de pomi va fi minimul dintre L, numărul liniei și numărul de coloane rămase pâna la final, adică N-C-1. În mod similar vom calcula toate cele patru segmente. Suma lor este rezultatul cerinței unu.

Rezolvare cerința doi

Se cere să aflăm câți pomi se află la distanță cel mult K de pomul P, unde distanța se măsoară în numărul de deplasări pe orizontală sau verticală. Să observăm că distanța de la pomul X de coordonate Lx și Cx la pomul P de coordonate Lp și Cp este

|Lx-Lp|+|Cx-Cp|

O soluție simplă care ia punctajul maxim este să parcurgem toți pomii livezii și să testăm dacă distanța pomului curent este mai mică sau egală cu K, caz în care adunăm unu la rezultat.

Ce complexitate are această soluție?

Desigur O(M·N), ceea ce este suficient pentru a se încadra în timp.

Se poate mai bine? Da, ca de obicei folosind matematică. O las ca temă de gândire.

Rezolvare cerința trei

Se cere să calculăm numărul de pomi vizibili. Un pom este vizibil atunci când are linie directă de vizibilitate către colțul din stânga-sus. Observăm că dacă un pom de linie L și coloană C este vizibil, atunci pomul de la linia 2⋅L și coloana 2⋅C nu va fi vizibil, deoarece linia de la colț către el va trece prin pomul vizibil. Similar, orice pom de linie k⋅L și coloană k⋅C nu va fi vizibil. Deducem de aici regula de ascundere a unui pom: dacă exista un divizor comun k>1 al liniei și coloanei unui pom, atunci pomul este ascuns, altfel este vizibil. Cu alte cuvinte pomii vizibili sunt cei ai căror coordonate sunt numere prime între ele.

O rezolvare posibilă este să parcurgem toți pomii, variind linia și coloana, și pentru fiecare pom de coordonate L și C să ne întrebăm dacă este vizibil sau ascuns. Pentru aceasta trebuie să cautăm existența unui divizor strict mai mare ca unu între L și C. Aici avem mai multe posibilități. Să considerăm că L < C. Atunci:

  • O metodă lentă de găsire a divizorilor este să luăm toate numerele de la 1 la L/2 și să testăm dacă atât L cât și C se împart la acele numere (testând separat L ca divizor al lui C). Ce complexitate are această soluție?

    Ea este O(N3) și va depăși timpul pe teste mari.
  • O metodă mai rapidă este generarea tuturor divizorilor lui L, testând pentru fiecare dintre ei dacă divid C. Generarea divizorilor se face căutând numerele d pâna la {\sqrt  {L}}, iar atunci când găsim un divizor d testând dacă atât d cât și L/d divid C. Ce complexitate are această soluție?

    Ea este O(N^{2}{\sqrt  {N}}) și va depăși în continuare timpul pe teste mari. Ca alternativă ceva mai eficientă putem descompune L în factori primi, testând dacă vreunul din factori divide C.
  • O metodă mai rapidă este să calculăm cmmdc între L și C cu algoritmul lui Euclid. Ce complexitate are această soluție?

    Ea este O(N2log N) și va trece majoritatea testelor.
  • Ca optimizare la oricare din metodele anterioare putem evita repetiția calculelor avînd grijă ca dacă avem de calculat vizibilitatea unui pom de coordonate L și C să nu mai calculăm și vizibilitatea pomului de coordonate C și L. Ea reduce calculele pe testele mari la jumătate. În acest caz metoda anterioară, cu cmmdc, va trece toate testele.
  • Cea mai rapidă metodă este similară cu ciurul lui Eratostene. Vom folosi o matrice de vizibilitate care va memora pentru fiecare pom valoarea 1 dacă el nu este vizibil, sau 0 în caz contrar. Inițial considerăm toți pomii vizibili. Apoi parcurgem matricea pe linii, iar atunci cînd întâlnim un pom vizibil la coordonatele L și C vom marca pomii pe care el îi ascunde (fiind în spatele lui) setând în matrice valoarea 1 la pozițiile (2⋅L 2⋅C), (3⋅L 3⋅C), (4⋅L 4⋅C), ... (k⋅L, k⋅C), până ce una din coordonate iese din matrice. Ce complexitate are această soluție?

    Ea este tot O(N2log N) (de ce?), dar nu efectuează împărțiri. Evident, va trece toate testele.
/*
  Solutie O(n^2 log n) (100p)
  - Numarul de pomi pe aceeasi diagonala se calculeaza prin formula
  - Numarul de pomi la distanta cel mult k se calculeaza luind fiecare pom
    si calculind abs(l - l0) + abs(c - c0) <= k
  - Pomii vizibili se calculeaza similar cu ciurul lui Eratostene. Parcurgem
    o matrice de vizibilitate viz[]. Daca elementul curent este zero (vizibil)
    atunci marcam in matrice toti pomii pe care ii marcheaza pomul curent ca
    nevizibili (valoare 1).
*/
#include <stdio.h>
#include <stdlib.h>

char viz[3000][3000];

int main() {
  FILE *fin, *fout;
  int t, k, m, n, lin, col, l, c, dl, dc, rez, lsus, ljos, cst, cdr;

  fin = fopen( "pomi.in", "r" );
  fscanf( fin, "%d%d%d%d%d%d", &t, &m, &n, &lin, &col, &k );
  fclose( fin );

  if ( t == 1 ) { // primul punct, numarul de pomi pe aceeasi diagonala
    lin--; // normalizam coordonatele sa inceapa de la zero
    col--;
    lsus = lin;        // numarul de linii de deasupra pomului
    ljos = m - lin -1; // numarul de linii de sub pom
    cst = col;         // numarul de coloane la stinga pomului
    cdr = n - col - 1; // numarul de coloane la dreapta pomului
    rez = 0;         // pornim cu zero pomi pe diagonale
    rez += lsus < cst ? lsus : cst; // adunam diagonala stinga-sus
    rez += ljos < cdr ? ljos : cdr; // adunam diagonala dreapta-jos
    rez += lsus < cdr ? lsus : cdr; // adunam diagonala dreapta-sus
    rez += ljos < cst ? ljos : cst; // adunam diagonala stinga-jos
  } else if ( t == 2 ) { // al doilea punct, pomi accesibili in k mutari
    rez = 0;
    for ( l = 1; l <= m; l++ )
      for ( c = 1; c <= n; c++ )
        if ( abs( lin - l ) + abs( col - c ) <= k )
          rez++;
  } else { // al treilea punct, numarul de pomi vizibili
    rez = 3; // coltul e vizibil, prima linie coloana au cite un pom vizibil
    for ( l = 1; l < m; l++ )
      for ( c = 1; c < n; c++ )
        if ( viz[l][c] == 0 ) { // vizibil
          rez++;
          dl = 2 * l;
          dc = 2 * c;
          while ( dl < m && dc < n ) {
            viz[dl][dc] = 1;
            dl += l;
            dc += c;
          }
        }
  }
  
  fout = fopen( "pomi.out", "w" );
  fprintf( fout, "%d\n", rez );
  fclose( fout );

  return 0;
}

Rezolvări aici: [1]

Lecție

Aceasta este filmarea lecției de dimineață:

Aceasta este filmarea lecției de după-amiază:

Calcul radical din long long

Știm deja funcția sqrt() pe care o putem folosi pentru a calcula radicalul unui număr întreg. Similar, dacă dorim să calculăm radicalul unui număr de tip long long sau unsigned long long avem funcția sqrtl(). Este posibil să aveți nevoie de ea la temă.

În continuare lecția constă din discuții ale problemelor de la temă, precum și a problemei cifru1 rămasă de la lecția trecută.

Problema cifru1

Problema cifru1 a fost dată la ONI 2007 clasa a 6a. Este o problemă a cărei greutate nu este de natură algoritmică. Greutatea ei constă în implementarea instrucțiunilor din enunț.

Problema poate avea multe abordări. Dar o soluție care nu repetă cod va folosi parcurgerea ramelor bazată pe vectori de direcție. Problema se reduce astfel la calculul maximului laturii unei rame și rotația acelei rame. Pentru aceasta putem copia rama într-un vector auxiliar, pe măsură ce o parcurgem. Cînd memorăm ce latură este maximă memorăm și începutul acelei laturi în vectorul auxiliar. Apoi copiem vectorul auxiliar suprascriind rama. Vom parcurge rama normal, în paralel cu vectorul pe care îl vom parcurge circular începînd cu latura maximală.

Iată o soluție (65 linii):

#include <stdio.h>

int dlin[4] = { 0, 1, 0, -1 }; // diferenta pe linie in functie de directie
int dcol[4] = { 1, 0, -1, 0 }; // diferenta pe coloana in functie de directie
int tablou[100][100];          // matricea tabloului de butoane
int aux[400];                  // vector auxiliar pentru copierea unei rame

int main() {
  FILE *fin, *fout;
  int n, i, j, l, c, rama, mij, dir, suma, smax, jmax, sumatotala;

  fin = fopen( "cifru1.in", "r" );
  fscanf( fin, "%d", &n );
  for ( l = 0; l < n; l++ )
    for ( c = 0; c < n; c++ )
      fscanf( fin, "%d", &tablou[l][c] );
  fclose( fin );

  sumatotala = 0;
  mij = n / 2;                           // cite rame avem
  for ( rama = 0; rama < mij; rama++ ) { // parcurgem fiecare rama
    smax = -1;              // suma maxima din cele patru laturi ale ramei
    l = c = rama;           // primul element al ramei
    j = 0;                  // am stocat 0 elemente din rama curenta in aux[]
    for ( dir = 0; dir < 4; dir++ ) { // parcurgem cele patru laturi ale ramei
      suma = tablou[l][c]; // suma laturii curente, initializare cu primul elem
      for ( i = 1; i < n - 2 * rama; i++ ) { // pentru celelalte elemente
        l += dlin[dir];        // avansam pe elementul curent
        c += dcol[dir]; 
        suma += tablou[l][c];  // il adunam la suma
        aux[j] = tablou[l][c]; // si il copiem in vectorul auxiliar
        j++;
      }
      if ( suma > smax ) {  // daca laturii este mai mare
        smax = suma;        // o pastram
        jmax = j - n + 2 * rama + 1; // si tinem minte inceputul laturii
      }
    }
    
    sumatotala += smax; // adunam suma maxima la suma totala
    // copiem aux inapoi in matrice, rotit; parcurgem rama copiind de la jmax
    l = c = rama;
    j = jmax; // indicele primului punct din latura maxima copiata in aux[]
    for ( dir = 0; dir < 4; dir++ ) { // parcurgem cele patru laturi ale ramei
      for ( i = 1; i < n - 2 * rama; i++ ) { // pentru celelalte elemente
        l += dlin[dir];   // avansam pe elementul urmator in rama
        c += dcol[dir];
        tablou[l][c] = aux[j];
        j++;
      }
      j %= (4 * n - 8 * rama - 4); // deplasare circulara in  vectorul aux[]
    }
  }

  fout = fopen( "cifru1.out", "w" );
  fprintf( fout, "%d\n", sumatotala );
  for ( l = 0; l < n; l++ ) {
    for ( c = 0; c < n; c++ )
      fprintf( fout, "%d ", tablou[l][c] );
    fprintf( fout, "\n" );
  }
  fclose( fout );

  return 0;
}

Temă

Tema 29 clasa a 6a

  • agent 007 dată la Olimpiada locală 2015, clasa a 6a
  • debarcare dată la ONI 2003 clasa a 7a
  • numere9 dată (într-o formă simplificată) la OJI 2017 clasa clasa a 5a
  • flori6 a fost dată la OJI 2006 clasa a 9a

Atenție! La această temă se vor adăuga problemele de la concursul ce va urma duminică:

Concurs clasa a 6a

Rezolvări aici: [2]