Clasa a VI-a lecția 28 - 28 mar 2019

From Algopedia
Revision as of 10:35, 19 March 2021 by Cristian (talk | contribs) (→‎Lecție)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

Anunțuri

Concurs duminică înlocuit cu Infotehnium 2019

Deoarece sîmbătă se desfășoară concursul Infotehnium 2019 nu vom avea concurs duminică la varena.

Tema lecției va consta din problemele Infotehnium 2019

Concursul Infotehnium se va desfășura sîmbătă 30 martie la școala 164, ora 9:00AM pentru cei de a șasea, 10:30AM pentru cei de a cincea. Problemele de la clasa a șasea vor constitui tema pentru joia viitoare. Ele vor fi adăugate la temă după concurs, sîmbătă seară sau luni diminteață.

Instructor invitat

Lecția de joi 4 aprilie va fi ținută de Cătălin Frâncu. Vă rog să vă comportați civilizat.

Tema 25 - rezolvări

Problema cutii1

Comentarii generale

  1. Felicitări celor ce au reușit o soluție de excepție: Voicu, Asgari, Ilie, Tatomir.
  2. Mențiuni speciale: Rebengiuc soluție de 100p ce folosește memorie O(1). Togan cu o soluție ingenioasă, deși ineficientă, ce a reușit să treacă 18 teste cu o soluție O(b), evitînd împărțirile.
  3. Mulțumiri celor ce m-au ajutat cu comentarii: Badea, Burac, Calotă, Ștefănescu, Fares.
  4. Unii din voi au dat algoritmi care au în mod evident complexitatea O(b). Era foarte clar că ei vor depăși timpul, nu-i așa? Foarte rău că nu ați încercat mai bine, mai ales la temă!
  5. Unii din voi mi-au trimis și la temă soluția din concurs, o soluție care nu funcționează. Aceasta înseamnă că nu v-ați mai gîndit deloc la ea ulterior. Foarte, foarte urît! Cine: Badea, Calotă, Grecu, Stoian.
  6. Avertismente celor ce nu au trimis nici o soluție la această problemă: Cojocariu, Mușat.

Comentarii individuale

Grupa de dimineață

  • Badea (35p): Mulțumesc pentru comentarii! Ai trimis aceeași sursă ca și în concurs, foarte urît (comentariul 5). Algoritmul tău este O(b), de aceea depășește timpul (comentariul 4). Testele picare cu 'incorect' sînt din cauza inițializării defectuoase a lui j. În loc de j = -1; corect era j = -rest;, pentru a porni cu j de la zero.
  • Benescu (5p): Soluția ta nu este doar lentă (comentariul 4), dar și fără noimă. Vezi codul tău:
    for(i=0; i<b; i++){
      q=(t%(n*2-2)+r);
      if(q<n || q>n*2-2){
        v[q]++;
        r=n-q;
      }
      else{
        v[n+n-q]++;
        r=q-n;
      }
    }

Tu apelezi v[q] atunci cînd q>n*2-2, deși vectorul are maxim 1000 de elemente. Atenție la matematică și la limite! E inadmisibil. Dacă ai fi pus ceva comentarii aș fi încercat să corectez codul.

  • Burac (10p-90p): Mulțumesc pentru comentarii! Ideea de bază e foarte bună. Implementarea este cam încîlcită, este bine că ai pus comentarii. Vezi te rog o soluție mai simplă mai jos.
  • Calotă (5p): Mulțumesc pentru comentarii! Ai trimis aceeași sursă ca și în concurs, foarte urît (comentariul 5). Ideea de pornire e bună, dar nu te-ai descurcat cu faptul că banda se mișcă dus-întors, drept care programul este incorect. Mulțumită comentariilor am înțeles, însă, că ideea este bună.
  • Chivu (5p-42p): Ideea este bună, iar implementarea este rezonabilă. Nu înțeleg de ce ai folosit vectorul de la 1. Însă algoritmul era clar că ieșea din timp, vezi comentariul 4. N-ai găsit nimic mai bun decît O(b)?
  • Cojocariu (0p): nimic? Continui pe linia asta, rezolvi cam o problemă de temă din două.
  • Grecu (15p): Ai trimis aceeași sursă ca și în concurs, foarte urît (comentariul 5). Algoritmul tău este O(b), de aceea depășește timpul (comentariul 4). Ideea de a combina cutiile nu e rea, codul este ordonat și scurt, dar ai greșit la formule. În loc de:
  for ( i = 0; i < b; ++i ) {
    if ( (time / n) % 2 == 1 ) {
      ++v[time % n];
    } else {
      ++v[(n - 1) - time % n];
    }
    time += t;
  }

trebuia

  for ( i = 0; i < b; ++i ) {
    if ( (time / (n - 1) ) % 2 == 1 ) { // n-1 in loc de n
      ++v[time % (n - 1)]; // n-1 in loc de n
    } else {
      ++v[(n - 1) - time % (n - 1)]; // n-1 in loc de n
    }
    time += t;
  }
  • Hossu (15p-38p): Ideea este bună, poate fi făcută să meargă. Implementarea e încîlcită. N-am putut să mă prind care e problema, căci nu ai pus comentarii. Hossu, ai lasat fprintf de debug în cod, care deschide un fișier "fout1.out". Atenție!
  • Mocanu (40p): Mocanu, din ultimele două teme ai rezolvat două probleme (din șapte). Și acelea, una din ele de 40p. Ce se întîmplă? Ai inițializat z=-1; în loc de z=-t;, de aceea ai cîțeva teste ratate cu 'incorect'.
  • Mușat (0p): nimic? N-a fost nici pe de parte cea mai grea problemă, dar e singura pe care nu ai atins-o.
  • Nicola (0p): Nimic.
  • Petcu (20p): Programul este ordonat și clar, bravo. Algoritmul tău este O(b), de aceea depășește timpul (comentariul 4). Nu înțeleg de ce ai folosit vectorul de la unu, ți-a fost lene să renumerotezi cutiile de la zero? Ratezi teste pentru că modifici variabila cutie pentru a actualiza vectorul de cutii. Ea nu trebuie schimbată, ea merge circular modulo 2*n-1, ci pe baza ei trebuie să calculezi cutia propriu-zisă. Mai exact, în loc de:
    for( ; b > 0; b-- ) {
        bomboane[cutie]++;
        cutie = ( cutie + t ) % ( 2 * n - 2 );
        if( cutie == 0 )
          cutie = n;
        if( cutie > n )
          cutie = 2 * n - cutie;
    }

trebuia:

    for( ; b > 0; b-- ) {
        if ( cutie <= n )
          bomboane[cutie]++;
        else
          bomboane[2 * n - cutie]++;
        cutie = ( cutie + t ) % ( 2 * n - 2 );
        if( cutie == 0 )
          cutie = 2 * n - 2;
    }

Ideea bună, dar atenție la matematică!

  • Rebengiuc (100p): o soluție matematică interesantă. Ai folosit memorie O(1), foarte interesant. Nu am înțeles bine formula din spatele algoritmului, dacă avem timp poate o prezinți la oră. Cod foarte frumos scris.
  • Rughiniș (15p): Algoritmul tău este O(b), de aceea depășește timpul (comentariul 4). Programul este destul de clar și ordonat. Folosești corect vectorul, dar te-ai încurcat la formulele de dus și de întors și de aceea ratezi teste. Mai exact, în loc de:
  a=0;
  v[n-1]++;
  for(i=0;i<b;i++){
    a+=t;
    if(a/(n-1)%2==0)
      v[n-1-a%(n-1)]++;
    else
      v[a%(n-1)]++;
  }

trebuia

  a=-t;
  for(i=0;i<b;i++){
    a+=t;
    if(a/(n-1)%2==0)
      v[n-1-a%(n-1)]++;
    else
      v[a%(n-1)]++;
  }
  • Stoian (10p): Ai trimis aceeași sursă ca și în concurs, foarte urît (comentariul 5). Mai ales că tu nu ai trimis o rezolvare, ci o aiureală, e o sursă de 0p, tu ai luat 10p cu noroc. Daria, tu poți mai mult. E o problemă de simulare, ai mai rezolvat așa ceva.
  • Ștefănescu (10p): Mulțumesc pentru comentarii! Algoritmul tău este O(t·b), adică forța cea mai brută posibil. De aceea pică 15 teste. În plus, ai fost neatentă la cum ai variat indicele cutiei. Mai exact, în loc de:
    nrb = 0;
    i = 0;
    sens = 1;
    timp = 0;
    c = n;
    m = 0;
    while (nrb < b) {
        /// schimb sensul
        if (i == n && sens == 1) {
            sens = -1;
        } else if (i == 0 && sens == -1) {
            sens = 1;
        }
    
        i += sens;
        // ...
    }

corect era:

    nrb = 0;
    i = -1; // in loc de 0                                           
    sens = 1;                                                      
    timp = 0;
    c = n;
    m = 0;
    while (nrb < b) {
        i += sens; // mutat sus, înainte de if

        /// schimb sensul                                                       
        if (i == n-1 && sens == 1) { // n - 1 nu n                                
            sens = -1;
        } else if (i == 0 && sens == -1) {
            sens = 1;
        }
        // ...
}

Cu aceste modificări vei trece 5 teste (20p).

  • Togan: (5p-85p): Un program interesant. Deși este O(b) reușește să treacă multe teste pentru că eviți împărțirile. Desigur că asta nu face soluția bună, ci doar ingenioasă. Nu mi-e clar de ce folosești vectorul de la unu. Cod destul de greu de înțeles, dar se vede o îmbunătățire. Continuă să simplifici încîlcelile.
  • Voicu (100p): Un program bun, bravo! Cel mai eficient din grupa de dimineață. Ca observații, deși lucrezi cu indici circulari, lucrezi cu ei de la 1, în loc de 0. Tu scrii i=(i+t-1)%(2*n-2)+1; cînd ai putea scrie mai simplu i=(i+t)%(2*n-2);. Un nărav care îți complică viața. Ai lăsat un printf de debug, mai multă atenție, te poate costa problema, TLE!

Grupa de după-amiază

  • Asgari (100p): Un program bun, bravo! Clar și simplu, folosești matematică, bun! Ca observație, ca și Voicu , deși lucrezi cu indici circulari, lucrezi cu ei de la 1, în loc de 0, ceea ce îți complica viața. În loc de curp = (curp - 1 + t) % (2 * (n - 1)) + 1; puteai să scrii curp = (curp + t) % (2 * (n - 1)) ;.
  • Cadîr (25p): O simulare foarte corectă și frumos scrisă, cu excepția faptului că folosești vectorul de la 1. Păcat că algoritmul tău este O(t·b), adică forța cea mai brută posibil. De aceea pică 15 teste cu TLE. Ai trimis aceeași sursă ca și în concurs, foarte urît (comentariul 5).
  • Dobre (15p-22p): Algoritmul tău este complex. Programul este bine scris și îngrijit, dar nu pot să-mi dau seama ce face, deoarece ai structuri de date gen o matrice cu trei linii, al căror rost nu îl cunosc. Din cîte îmi dau seama, complexitatea algoritmului este O(t·b), adică forța cea mai brută posibil. Dacă îl repari vei lua 5 teste. Am remarcat bordarea vectorului de cutii, drăguț.
  • Fares (40p-95p): Mulțumesc pentru comentarii! Motivul pentru care am înțeles, în mare, ceea ce faci, sînt aceste comentarii. Yusuf, tu ai luat toate testele, felicitări! Dar gîndirea ta este prea încîlcită. Ai atît de multe cazuri încît sînt greu de urmărit! Acele cazuri nu există în realitate, tu le-ai introdus. Trebuie să încerci să îți simplifici gîndirea. Pentru asta este nevoie să te gîndești mai mult la algoritm, cu o hîrtie și un pix în față, înainte să te apuci să scrii la calculator. Codul tău este scris ca și cum ai vorbi liber. Iată un exemplu care nu are sens: c = 1ll * b / rep;. Sau altul:
    if (c == 0 && f1[i] == 0)
      sol1++;
    else if (c > 0 && f[i] == 0)
      sol1++;

care se putea scrie:

    if (f1[i] == 0)
      sol1++;
  • Ilie (100p): Un program ordonat și clar. Singurul lucru neclar era la ce îți trebuie vectorul rep[]. M-am lămurit, pentru a îți da seama cînd se termină primul ciclu de găleți. Pentru aceasta nu e nevoie de vector, ciclul se va încheia întotdeauna la prima găleată. Este similar cu problema celor doi băieți care săreau în cerc în direcții diferite și se opreau atunci cînd săreau acolo unde mai săriseră o dată. Per total o sursă bună, bravo!
  • Ipate (10p-18p): Elisa, două probleme cu algoritmul tău: 1. Algoritmul tău este O(b), de aceea depășește timpul (comentariul 4). 2. Metoda matematică este incorectă. Ambele sînt destul de grave, pentru că (1) înseamnă că nu ai calculat faptul că îți va depăși timpul, iar (2) înseamnă că ai slăbiciuni la matematică, ceea ce în cazul unei matematiciene e un pic îngrijorător.
  • Marcu (10p): Mulțumesc pentru comentarii! Am înțeles intenția mulțumită lor, deoarece tu nu faci ceea ce vrei să faci:
c=(c+t)%n;//folosim un vector cu 2n-1 elemente deorece la poz 2n-1 se repeta modul de parcurgere

Un calculator face ceea ce îi spui să facă, nu ceea ce vrei să facă! Păcat că nu a citit și compilatorul comentariul. Dacă vrei să folosești 2n-1 elemente atunci trebuia să scrii modulo 2n-1, nu modulo n :-). O altă problemă este că simularea ta este O(b), de aceea depășește timpul (comentariul 4).

  • Nicu (100p): Nicu, tu chiar ți-ai dorit cele 100 de puncte! Felicitări! Programul tău este unul stufos, ai lucrat, ai tastat, ai creat multe cazuri particulare acolo unde nu existau! Ai muncit împotriva încîlcelii tale. Alex, dacă vrei să te îmbunătățești trebuie să gîndești înainte să te arunci în programare la calculator. Ia o hîrtie și un creion și fă-ți cîteva teste, încearcă să înțelegi cum ai face tu. Programul tău arată ca și cînd vorbești liber: te repeți, te mai bîlbîi, etc. Precum vezi multe din sursele tale sînt pescuite. Lenea de a face teste te ține din a progresa ca informatician. Măcar dacă puneai comentarii. Așa, nu am nici cea mai vagă idee ce ai vrut să să scrii sau ce ai gîndit.
  • Stancu (25p): Mulțumesc pentru comentarii! Programul e mai ușor de citit și înțeles. Programul tău este ordonat, bravo. Soluția ta este, din păcate, ineficientă, fiind 'O(t·b), adică forța cea mai brută posibil. De aceea pică 15 teste. Ca observație, înțeleg că folosești vectorul de la 1, dar nu avea rost să îl declari de 2001 elemente, 1000 erau deajuns.
  • Tatomir (100p): O soluție bună, simplă și bine scrisă! Bravo!
  • Teodorescu (80p): O soluție foarte bună și eficientă, bravo! Se mai poate simplifica. Nu aveai nevoie neapărat de vectorul de resturi, de exemplu. Folosești indici de la 1, în loc să-i folosești de la 0, deși ai nevoie de mișcări circulare în vector. Simularea cu steguleț e greu de urmărit, chiar dacă așa v-am predat, acela este un caz general. Dacă poți simplica, simplifică. Motivul pentru care ratezi testele mici cred că este că în prima buclă te oprești doar cînd faci un ciclu complet. Dar poate se termină bomboanele mai devreme? Trebuie să mai adaugi o condiție de ieșire.

Rezolvări aici: [1]

Tema 27 - rezolvări

Rezolvări aici: [2]

Lecție

<html5media height="720" width="1280">https://www.algopedia.ro/video/2018-2019/2019-03-28-clasa-6-lectie-info-28-720p.mp4</html5media>

Lecția a constat din discuții despre problemele de la ultimele două teme, ale lecțiilor 25 și 27, respectiv problemele șenila, pește, cutii1, factoriale.

Temă

Tema 28 clasa a 6a

  • atlantis dată la Infotehnium 2019 clasa a 6a avansați
  • pomi dată la Infotehnium 2019 clasa a 6a avansați

Atenție! Această temă va consta din cele două probleme date la concursrul Infotehnium 2019, la clasa a șasea avansati. De aceea tema începe duminică 31 martie 2019. Este posibil să înceapă și sîmbătă noapte.

Rezolvări aici: [3]