Clasa a VI-a lecția 20 - 21 feb 2019

From Algopedia
Jump to: navigation, search

Anunț

Concursuri săptămînale

Deoarece se apropie OJI și ONI am hotărît să organizez cîte un concurs în fiecare duminică la ora 15. El va încerca să fie o simulare de OJI sau ONI, constînd fie în două probleme de rezolvat trei ore, fie în trei probleme de rezolvat în patru ore.

Organizarea acestor concursuri necesită un efort considerabil. Drept care vă rog să faceți și voi efortul de a participa. Scuze de genul "am avut teză", sau "am fost plecat la casa mea de la Breaza", sau "am fost prea obosit din cauza concursului de pian" nu sînt elegante și nici acceptabile.

Tema - rezolvări

Problema creioane

Problema creioane a fost dată la ONI 2008 clasa a 6a. Rezolvarea forță brută este relativ ușor de scris, dar nu se va încadra în timp pentru teste mari deoarece are complexitate O(n2). O putem însă modifica ca atunci cînd calculăm înălțimea unei grămezi de creioane să calculăm înălțimea fiecărui creion din grămadă. În acest fel vom avea O(1) calcule per element, ceea ce duce la o soluție optimală liniară, O(n). Cînd găsim un creion a cărui înălțime nu este calculată vom parcurge toate creioanele de sub el pînă ce găsim un creion cu înălțime calculată. Vom memora calea de creioane parcurse, pentru ca după ce găsim creionul cu înălțimea calculată să putem actualiza toate creioanele de deasupra lui.

Iată un program bazat pe memoizare:

#include <stdio.h>

int sub[9001], // sub[i] este creionul care se afla sub creionul i
  h[9001],     // h[i] este inaltimea la care se afla creionul i
  stiva[9001]; // stiva memoreaza creioanele prin care trecem

int main() {
  FILE *fin, *fout;
  int n, i, p, hc, sp, max, aux;

  fin = fopen( "creioane.in", "r" );
  fscanf( fin, "%d", &n );
  for ( i = 1; i <= n; i++ )
    fscanf( fin, "%d%d", &sub[i], &aux ); // ignoram creionul 2, este inutil
  fclose( fin );

  max = 0;
  for ( i = 1; i <= n; i++ ) { // calculam inaltimea fiecarui creion i
    p = i;
    sp = 0;
    // mergem din creion in creion in jos pina ajungem la un creion care
    // sta pe masa; in acelasi timp memoram creioanele prin care trecem
    while ( h[p] == 0 )   // cita vreme inaltimea nu este calculata
      if ( sub[p] > 0 ) { // avem un creion dedesubt?
        stiva[sp] = p;    // tinem minte creionul actual in calea de creioane
        sp++;
        p = sub[p];       // avansam la creionul de sub el
      } else              // altfel am ajuns la nivelul mesei, inaltimea este 1
        h[p] = 1;

    hc = h[p];            // pornim cu inaltimea curenta
    while ( sp > 0 ) {    // pentru fiecare element din calea memorata
      sp--;
      hc++;
      h[stiva[sp]] = hc;  // ii calculam inaltimea
    }

    if ( max < h[i] )     // la final verificam daca este maxima
      max = h[i];
  }

  fout = fopen( "creioane.out", "w" );
  fprintf( fout, "%d", max );
  fclose( fout );

  return 0;
}

Problema bila1

Comentarii generale

  1. Felicitări celor ce au reușit o soluție de excepție: Hossu, Voicu, Ilie.
  2. Mențiuni speciale: Nicola, Dobre, care au înjumatățit memoria folosind matrice de tip unsigned short.
  3. Mulți dintre voi denumiți vectorii neinspirat, gen drum1[15625] și drum2[15625]. Ei stochează drumul bilei, deci linii și coloane. Denumiți-i cu semnificație atunci, de exemplu drumlin[15625] și drumcol[15625]. Sau ldrum[] și cdrum[]. Orice care să conțină drum și linie/coloană. La fel și matricele de înălțimi, respectiv lungime a drumului, unii le-ați spus m1[][] și m2[][], sau similar. Puteați să le denumiți h[][] și d[][], de la înălțime și drum.
  4. Mulți dintre voi folosiți i și j în loc de l și c. Aceasta face codul mai greu de citit. Cînd văd în program variabila i nu știu dacă este linia sau coloana. Folosiți cu încredere l și c!
  5. Mulți dintre voi ați refăcut calea bilei în mod ciudat. Actualizați primul element al căii cu lungimea ei, apoi îi adunați primul turn calculat găsit și apoi mergeți pe cale în jos scăzînd unu. Funcționează, dar este foarte nenatural și încîlcit. Era mai normal să porniți de la elementul găsit și să parcurgeți calea în sens invers, adunînd unu.
  6. Majoritatea dintre voi nu ați folosit vectori de direcție pentru calculul minimului dintre vecini. Bine că n-ați avut opt vecini! Copy/paste-ul este regele vostru.
  7. Unii din voi nu au înțeles memoizarea. Este o noțiune grea, dar v-aș încuraja să o reluați, sau să îmi puneți întrebări pentru a o lămuri: Calotă, Cojocariu, Iordache, Mocanu, Mușat, Nicola, Ștefănescu, Togan, Asgari, Cadîr, Nicu, Stancu.
  8. Mulți dintre voi mă ajută cu comentarii. Vă mulțumesc!
  9. Avertismente celor ce nu au trimis nici o soluție la această problemă: Chivu, Grecu.

Comentarii individuale

Grupa de dimineață

  • Badea (0p-85p): Ideea este bună, soluția corectă. Folosești frumos bordare, cu coloane de înălțime maximală. În continuare nu folosești vectori de direcție, de aceea mare parte din codul tău se repetă pentru a găsi minimul.
  • Benescu (100p): O souție bună, bravo! Folosești atît bordare cît și vectori de direcție. Din păcate ai probleme: matricea de bordare necesită două elemente în plus față de 125, deci 127, nu 128. Vreau calcule exacte, te rog. Declari trei linii în vdrum[][], dar folosești doar primele două. A treia e inutilă. Folosești corect vectorii de direcție pentru a calcula minimul vecinilor. Dar nu păstrezi și coordonata vecinului minim, astfel încît repeți apoi cod pentru a găsi vecinul, ceea ce anulează vectorii de direcție, puteai să nu îi folosești.
  • Burac (50p-85p): Soluție bună, bravo! Folosești corect bordarea cu înălțimi maximale. Nu folosești vectori de direcție drept care repeți cod la aflarea vecinului minim. Modul în care calculezi vecinul minim este foarte risipitor, cu de trei ori mai multe teste decît necesar. Burac! Dacă nu știi să calculezi minimul dintre patru elemente, întoarce-te la lecția de clasa a cincea te rog, elementul maxim dintr-o secvență, nu scrie bălării! Citește comentariile generale 3, 4 și 5.
  • Calotă (30p) : Soluția ta nu folosește memoizarea completă. Nu stochezi calea parcursă de bilă și nu calculezi toate elementele aflate pe acea cale, ci doar pe primul. Ar trebui să nu se încadreze în timp, dar testele nu sînt bune. Mi-a plăcut "boradarea" inteligentă (cum ai scris tu) :-) Matrice denumite a[][] și b[][], vezi comentariul 3. Declari vectori de direcție dar nu îi folosești complet, repeți cod pentru a găsi minimul dintre vecini (comentariul 6). Motivele pentru care nu iei 100p:
    • La linia 82 scrii condiția nrmax < nr. Tu calculezi cel mai înalt turn, se cerea cel mai mic. Trebuia pe dos, nrmax > nr.
    • Declari matricea de bordare corect, dimensiune 127, dar pe cea de înălțimi o declari de 125, generînd o depășire de matrice (zîna indicilor).
  • Chivu (0p): nimic? Soluția la creioane este bună ca formă, trebuia doar să o depanezi. Apoi aplicai același principiu la bila1.
  • Cojocariu (50p): Soluție interesantă și corectă, dar nu folosești memoizare, de aceea depășești timpul. Ceea ce denumești tu memoizare este, de fapt, memorarea direcției în care merge bila din fiecare element. Nu, memoizarea înseamnă să calculezi lungimile drumurilor pentru toate turnurile din calea bilei. Tu calculezi doar pentru turnul curent. Ai scris o bucată de cod care nu are sens:
        d=dl[t[l2][c2][1]]+10*dc[t[l2][c2][1]];//asta merge deoarece atunci cand una dintre valri este != de 0 cealalata este 0.
        l2+=d%10;
        c2+=d/10;

Era mai simplu:

        l2+=dl[t[l2][c2][1]];
        c2+=dc[t[l2][c2][1]];

Atenție mare la printf-urile de depanare! Ai lăsat o întreagă tipărire de matrice în program! Am senzația că te-ai grăbit la tema asta.

  • Grecu (0p): Nimic? La creioane te-ai descurcat, aici nu?
  • Hossu (30p-90p): O soluție foarte bună, bravo! Folosești corect atît bordarea cît și vectorii de direcție. Programul are mici încîlceli și folosește un steguleț nenecesar, dar avînd în vedere greutatea problemei și cunoștințele noi consider că ai dat o soluție foarte bună!
  • Iordache (30p): Nu folosești memoizare. De ce am predat-o? Fără memoizare vei lua maxim 50p. Nu folosești vectori de direcție, drept care repeți cod pentru calculul vecinilor, vezi comentariul 6. Folosești bordare cu 0. Era mai simplu dacă bordai cu ceva foarte înalt, scăpai de cîteva teste. În concluzie nu folosești nimic din ce am învățat. De ce mai vii la IQ Academy?
  • Mocanu (30p): Nu folosești memoizare, poți lua maxim 50p cu un program corect (vezi comentariul 7). Bordare corectă cu înălțimi maximale, bravo. Declari vectori de direcție dar nu îi folosești la calculul minimului. Vezi comentariile 3 și 4, programul este mai greu de înțeles din cauza variabilelor denumite neinspirat. Tu scrii:
        mi=65001;
        if(mi>v[i][j]){
          mi=v[i][j];
        }

Dar este clar că acea condiție va fi mereu adevărată. Deci de ce nu scrii direct: mi=v[i][j];?

  • Mușat (30p-45p): Folosești corect bordare, cu înălțimi maximale, bravo! Nu folosești vectori de direcție, drept care repeți și scrii mult cod pentru calculul vecinului minim, vezi comentariul 6. Nu folosești memoizare, vezi comentariul 7, acesta era scopul problemei. De aceea iei TLE. Nu inițializa variabile la declarare (fișierele)!.
  • Nicola (50p): Bună intenția de a înjumătăți memoria folosită declarînd matricea de înălțimi unsigned short, bravo! Atenție mare la bordare, dimensiunile pe linie și coloană sînt diferite, trebuiau două bucle for! Ideea de înălțime maximală la bordare e foarte bună, dar valoarea aleasă e cumva arbitrară. Puteai să alegi cu 1 mai mult față de înălțimea maximă, adică 65001. Vectori de direcție foarte bine folosiți, bravo! Din păcate nu folosești memoizare. Tu marchezi elementele din matrice care nu pot fi maximale, ceea ce nu e rău. Dar nu te ajută atunci cînd pornești dintr-un element care poate fi maximal. Vei merge pînă la capăt. Mai bine era să le calculezi lungimea drumului pentru căile "bătute", astfel încît să nu trebuiască să recalculezi de fiecare dată. Vezi comentariul 7.
  • Petcu (100p): Bordare corectă cu înălțimi maximale, bravo! Nu ai folosit vectori de direcție pentru vecini, de aceea duplici mult cod la calculul minimului vecinilor. Vezi comentariul 6. Pentru calcularea elementelor drumului ai duplicat destul de mult cod, programul aproape se dublează. Copy/paste nu este prietenul tău, reține! Vezi greși la modificări. O rezolvare aproape perfectă, bravo.
  • Rebengiuc (50p): Un program drăguț și ordonat! Folosești corect atît bordarea cu înălțimi maximale, cît și vectorii de direcție pentru calculul rapid al vecinilor, bravo! Nu memorezi calea, dar o recalculezi, ceea ce duce le o ușoară duplicare de cod, pe care o accept. Însă motivul pentru care nu iei 100p este unul de gîgă: refolosești din greșeală variabila de ciclu i de la linia 70 la linia 74. Dacă înlocuiești i de la linia 70 cu j, precum și la linia 71, vei lua 100p.
  • Rughiniș (100p): Un program foarte bun. Ca obiecții: nu folosești nici bordare, nici vectori de direcție, ceea ce duce la cod lung și repetat. Dar folosești corect memoizare și memorarea căii, bravo! Variabila stegulet nu este de fapt un steguleț, ci o direcție. Induci cititorul în eroare cu astfel de denumiri.
  • Stoian (50p): Bravo, bordare corectă cu înălțimi maximale și ai folosit corect vectorii de direcție pentru calculul minimului dintre vecini! Folosești două stegulețe inutile, gas și ok, dar programul este în regulă. Nu stochezi calea, ci o refaci, de sus în jos, nu cum scrii tu în comentariu, că parcurgi invers traseu. Nu, îl parcurgi în sensul direct, nu invers. Comentariile care mă induc în eroare nu sînt bune :). Mi-a luat ceva timp să îmi dau seama de ce ai TLE. Motivul este o eroare subtilă, pe care era mai simplu să nu o faci decît să o depanezi: tu ai o lungime a căii ce trebuie calculate în s. Acea cale ar trebui reparcursă și calculată, ceea ce ar fi foarte bine. Problema este că tu o modifici, o faci să fie lungimea căii pe care cade bila. În acel moment tu vei reface întreaga cale a bilei, nu doar cea necalculată! E ca și cum nu faci memoizare. Dacă nu modifici s și ai grijă ca fiecare element al căii să fie cel din-naintea lui minus unu, programul se va încadra în timp și vei lua 100p. Atenție la bordare! Tu scrii 65001 în toată matricea! Este o risipă, trebuia să scrii doar pe margine, de aceea se cheamă "bordare".
  • Ștefănescu (0p-47p): Soluția ta este corectă, dar nu folosești memoizare, vezi comentariul 7. Bravo, folosești corect bordarea cu înălțimi maximale! Nu folosești vectori de direcție și de aceea codul de calcul al vecinului minim este lung și repetitiv. Vezi comentariul 6. De asemenea folosești două matrice inutile, minl și minc. Nu ai nevoie să memorezi direcția. Odată folosită, nu o mai folosești din nou, deci de ce să triplăm memoria folosită?
  • Togan: (100p): Soluție corectă, dar fără bordare și fără vectori de direcție. I-am predat pentru ca tu să-i ignori. Soluția ta nu folosește memoizarea completă. Nu stochezi calea parcursă de bilă și nu calculezi toate elementele aflate pe acea cale, ci doar pe primul. Ar trebui să nu se încadreze în timp, dar testele problemei nu sînt testează bine astfel de soluții. Vezi comentariul 7. Folosești în mod inutil stegulețul st.
  • Voicu (81p): O soluție foarte corectă, cu bordare cu înălțimi maximale și vectori de direcție, bravo! Codul este puțin încîlcit, trebuie să lucrezi la a-ți descîlci gîndirea. Atenție la cod inutil, în while(dir>=0 && memo[l][c]==0 && a[l+dl[dir]][c+dc[dir]]<a[l][c]) ultima condiție este totdeauna adevărată, altfel dir ar fi fost -1, deci prima condiție ar fi fost falsă. Ratezi testul 6 dintr-o neatenție gravă de copy/paste: faci bordarea greșit cu n+1 în loc de m+1, la atribuire, linia 30 (a doua de mai jos):
    for(i=0;i<=n+1;i++)
        a[i][0]=a[i][n+1]=65001;

Grupa de după-amiază

  • Asgari (100p): Un program corect, dar nu ai înțeles memoizarea, vezi comentariul 7. Nu stochezi calea parcursă de bilă și nu calculezi toate elementele aflate pe acea cale, ci doar pe primul. Ar trebui să nu se încadreze în timp, dar testele problemei nu sînt testează bine astfel de soluții. Folosești un steguleț inutil, iar codul se încîlcește, trebuie să mai lucrezi la descîlcirea gîndirii, îți complică codul. Atenție la cod inutil: if( mat[l1+dl[dir]][l2+cl[dir]] < nr && mat[l1+dl[dir]][l2+cl[dir]] != 0 ) cum ar putea un element al matricei mat să ajungă zero? Ultima condiție este inutilă. Nu poți să spui "cea mai optimă sursă", adjectivul "optim" nu are grade de comparație, este optim sau nu este.
  • Cadîr (50p): O soluție bună, dar nu ai folosit memoizare. Vezi comentariul 7. De aceea iei TLE. Ai folosit corect bordarea cu înălțimi maximale, dar nu ai folosit vectori de direcție (comentariul 6), ceea ce duce la cod repetitiv la calculul vecinilor.
  • Dobre (p): O soluție bună, dar cu probleme. Ai folosit corect bordarea cu înălțimi maximale. Nu ai folosit vectori de direcție, ceea ce a dus la cod repetitiv la calculul vecinilor (comentariul 6). Bravo, te-ai prins că matricele pot fi de tip unsigned short. Folosești indici i și j, vezi comentariul 4. Din această cauză ai ratat un test, întrucît ai bordat incorect matricea. În programul tău liniile variază pînă la n, iar coloanele pînă la m, deci bordarea e greșită. Celelalte două teste le-ai ratat pentru că ai uitat o cerință: dacă avem mai multe drumuri maximale îl alegem pe cel în care bila pornește cît mai de jos.
  • Fares (30p-85p): Un program corect, care folosește memoizare. Este încîlcit, aici mai ai de lucru, la descîlcirea gîndirii. Nu folosești vectori de direcție, ceea ce duce la cod repetitiv și la greșeli. Le-am predat pentru ca tu să le poți ignora, să faci tot cum ai chef. Nu știu de ce mai vii la IQ Academy? Funcțiile pozi și pozj sînt aproape identice. Rostul funcțiilor este exact să nu repeți cod, deci este clar că nu înțelegi funcții. Atunci de ce le folosești? Faptul că nu memorezi calea bilei duce la o altă duplicare de cod, la reluarea căii. Însă motivul pentru care ratezi un test este unul de începător: copy/paste cu mare neatenție, combinat cu comentariul 4, folosirea de i și j acolo unde ai de fapt linii și coloane. Astfel nu ai observat că faci comparație a lui j cu n în loc de m, în toate cele trei funcții. O greșeală în una din ele s-a repetat de încă două ori prin copy/paste. Dacă făceai bordare nu ajungeai să mai compari. În concluzie, de ce ai ratat teste? Pentru că:
    • Ai făcut copy/paste - cod repetitiv
    • Nu ai folosit bordare
    • Ai folosit indici i și j în loc de l și c
    • Ai folosit funcții aiurea
  • Ilie (100p): Un program foarte frumos și ordonat, bravo! Folosești corect bordarea cu înălțimi maximale și vectori de direcție pentru vecini. Faci memoizare cu memorarea căii. Scurt și la obiect. Ca perfecționist poți să mai tai anumite repetiții, cum ar fi testul if(p>-1), vezi rezolvarea de mai jos.
  • Ipate (100p): Un program frumos și ordonat, bravo! Folosești corect bordarea matricei cu înălțimi maximale, precum și memoizare cu memorarea căii bilei. Din păcate, deși folosești vectori de direcție, nu îi folosești complet: calculul minimului vecinilor se putea face într-o buclă, pentru a nu repeta cod, care este și rolul vectorilor de direcție. Vezi mai jos o soluție ceva mai scurtă. Oricum, un program foarte bun, felicitări!
  • Marcu (50p-95p): Programul tău folosește corect bordarea cu înălțimi maximale și memoizarea. Nu memorezi calea ci o reparcurgi, ceea ce duce la repetiție atît de cod cît și de calcule, dar funcționează. Însă nu ai folosit vectori de direcție. Ilinca, dacă vrei să scurtezi condițiile folosește vectori de direcție. Pe care i-ai declarat și nu i-ai folosit! Ilinca! Dacă nu știi să calculezi minimul dintre patru elemente, întoarce-te la lecția de clasa a cincea te rog, elementul maxim dintr-o secvență. Codul tău este urît, cu enorm de multe teste! Minimul a patru numere se află cu 3 teste, nu-i așa?
  • Nicu (40p): Program foarte încîlcit. Folosești multe variabile inutile, pe care le transferi unele în altele. Se vede că te apuci direct de programat, în loc să scrii niște idei pe hîrtie înainte. Alex, dacă vrei să ajungi informatician trebuie să te corectezi. Pe calea pe care ești acum vei ajunge doar să dai cu forul, ca orice programator mediocru. Nu ai nevoie de IQ Academy pentru asta. Revenind la comentarii, programul tău folosește bordarea, dar cu zero, era utilă o bordare cu cea mai mare înălțime, 65001, care evita un test. Folosești corect și vectori de direcție, pentru a nu repeta calculul vecinilor. Din păcate nu folosești memoizare, comentariul 7. De aceea ai TLE la multe teste. Aș fi vrut să îți depanez programul, dar este prea încîlcit și fără noimă, nu am cum.
  • Stancu (0p): David, programul tău arată ca și cînd nu ți-ai dat silința. De exemplu afișezi numerele cerute cîte unul pe linie, se cerea să le afișezi pe aceeași linie cu spații între ele. Asta e o neglijență de clasa a cincea, nu de clasa a șasea la IQ Academy. Programul tău folosește corect bordarea, cu înălțimi maximale. Din păcate doar atît. Nu folosești vectori de direcție și nici memoizare. Ignori un avertisment de compilare important, variabila ok nu va fi mereu inițializată. Ce se întîmplă dacă nu intră pe nici una din ramurile if? Tu consideri că el este 3, în realitate era necesar să compari minimul și cu al patrulea vecin. Dacă faci această comparație vei pica testele 3, 4 și 5, iar testele 6-10 for lua TLE, deoarece nu folosești memoizare. Nu am mers mai departe cu depanarea.
  • Tatomir (100p): Programul tău pare este aproape perfect, mai puțin încîlceala cam mare. Folosești corect bordarea matricelor cu înălțimi maximale, vectori de direcție pentru calculul vecinilor și memoizare cu memorarea căii bilei. Însă la o privire mai atentă se vede cod repetat ciudat (golirea stivei, comparația m2[x][y] cu zero). Studiind repetițiile am remarcat și o încîlceală a testului de oprire a bilei, ceea ce pare a fi motivul repetițiilor. Vezi te rog soluția de mai jos. Vezi și comentariul 3, m1 și m2 se confundă între ele, cînd de fapt înseamnă lucruri cu totul diferite.
  • Teodorescu (50p-90p): Un program foarte ordonat. Folosești bordare corectă, cu înălțimi maximale, și memoizare cu memorarea căii bilei, pentru a nu repeta calcule. Din păcate folosești doar parțial vectorii de direcție, deoarece nu-i folosești în calculul vecinilor, ceea ce duce la destul de mult cod duplicat. Mai ai și alte mici repetiții, cum ar fi condiția dir != 4 sau drum[cl][cc] == 0. Una peste alta un program foarte clar și ordonat. Continuă să te perfecționezi!

Rezolvare

Problema bila1 a fost dată la ONI 2010 la barajul de gimnaziu.

Rezolvarea folosește elemente clasice:

  • bordarea matricei cu înălțimi foarte mari (infinit)
  • vectori de vecini (similari cu vectorii de direcție)

Rezolvarea forță brută este O(n3), deoarece drumul din fiecare turn poate avea lungime O(n). Această rezolvare nu trece testele mari. Rezolvarea optimă folosește memoizare și este O(n2). Pentru a nu recalcula drumul căderii bilei putem memora acel drum în doi vectori de coordonate linie și coloană.

Iată o soluție posibilă:

#include <stdio.h>

#define INFINIT 65001

int h[127][127], d[127][127];  // inaltimile si lungimile drumurilor (128K)
int cale[125*125][2];          // aici memoram calea de cadere a bilei (128K)
int dlin[4] = { -1, 0, 1, 0 }; // vectori de vecini
int dcol[4] = { 0, -1, 0, 1 };

int main() {
  FILE *fin, *fout;
  int n, m, l, c, lb, cb, sp, vec, i, lung, max, hmin;

  fin = fopen( "bila1.in", "r" );
  fscanf( fin, "%d%d", &n, &m );
  for ( l = 1; l <= n; l++ )
    for ( c = 1; c <= m; c++ )
      fscanf( fin, "%d", &h[l][c] ); // citim inaltimile
  fclose( fin );

  // bordare matrice cu turnuri foarte inalte
  for ( l = 1; l <= n; l++ )
    h[l][0] = h[l][m+1] = INFINIT;
  for ( c = 1; c <= m; c++ )
    h[0][c] = h[n+1][c] = INFINIT;

  max = 0;
  for ( lb = 1; lb <= n; lb++ ) // calculam fiecare element d[lb][cb]
    for ( cb = 1; cb <= m; cb++ ) {
      // pornim caderea bilei, folosim (l, c)
      l = lb;
      c = cb;
      sp = 0; // in cale[sp] stocam coordonatele prin care trecem

      // cadem cita vreme casuta curenta nu are scorul calculat
      while ( d[l][c] == 0 ) { // scor necalculat?
        vec = 0;               // recalculam vecinul minim
        for ( i = 1; i < 4; i++ )
          if ( h[l + dlin[i]][c + dcol[i]] < h[l + dlin[vec]][c + dcol[vec]] )
            vec = i;
        // vecinul minim este mai mic strict decit casuta curenta, avansam
        if ( h[l + dlin[vec]][c + dcol[vec]] < h[l][c] ) {
          cale[sp][0] = l; // memoram linia si coloana
          cale[sp][1] = c;
          sp++;
          l += dlin[vec]; // bila cade la noile coordonate
          c += dcol[vec];
        } else // bila a ajuns la capat, deci distanta parcursa este 1
          d[l][c] = 1;
      }
      
      // am ajuns la capatul drumului, o luam inapoi
      lung = d[l][c]; // pornim cu lungimea de cadere din casuta de oprire
      // pe toata calea memorata vom actualiza lungimile de cadere
      while ( sp > 0 ) {
        sp--;
        lung++; // drumul e mai lung cu unu la fiecare avans in sus al bilei
        d[cale[sp][0]][cale[sp][1]] = lung; // calculam lungimea
      }
      // vom reactualiza (max hmin) fie daca avem un drum mai lung, fie daca
      // avem un drum egal dar pornind de la o inaltime mai mica
      if ( d[lb][cb] > max || (d[lb][cb] == max && h[lb][cb] < hmin) )  {
        max = d[lb][cb];
        hmin = h[lb][cb];
      }
    }

  fout = fopen( "bila1.out", "w" );
  fprintf( fout, "%d %d\n", max, hmin );
  fclose( fout );

  return 0;
}

Problema ecuatie2

Problema ecuatie2 este una de atenție în a trata corect cele opt cazuri posibile. Observăm că putem împărți ecuațiile în două tipuri:

  • Tipul 1: x operator a = b
  • Tipul 2: a operator x = b

Această observație ne permite să nu repetăm prea mult codul de citire, scriind opt citiri diferite pentru cele opt cazuri. Vom scrie citirea pentru cele două cazuri, memorînd în x tipul ecuației citite și în op operatorul folosit. Apoi tratăm cele opt cazuri într-un switch de calcul.

Iată o soluție posibilă.

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  int ch, op, x, a, b, tip;

  fin = fopen( "ecuatie2.in", "r" );
  a = b = 0;
  ch = fgetc( fin );
  if ( ch == 'x' ) {
    x = 1; // conventie: x = 1 inseamna ca x a fost primul in ecuatie
    op = fgetc( fin );       // citim operatorul
    ch = fgetc( fin );       // citim prima cifra a numarului (a)
    while ( ch != '=' ) {    // cita vreme e cifra (nu am ajuns la semnul egal)
      a = a * 10 + ch - '0'; // adaug-o la 'a'
      ch = fgetc( fin );     // citeste urmatoarea cifra
    }
  } else {
    x = 2; // conventie: x = 2 inseamna ca x a fost al doilea in ecuatie
    while ( ch >= '0' && ch <= '9' ) { // citim intii numarul (a)
      a = a * 10 + ch - '0';
      ch = fgetc( fin );
    }
    op = ch;                 // citim operatorul
    fgetc( fin );            // citim 'x'
    fgetc( fin );            // citim '='
  }
  ch = fgetc( fin );         // prima cifra a numarului de dupa egal
  while ( ch >= '0' && ch <= '9' ) { // citim numarul de dupa egal (b)
    b = b * 10 + ch - '0';
    ch = fgetc( fin );
  }
  fclose( fin );

  switch ( op ) { // in functie de operator vom calcula diferit x
  case '+':
    tip = 3 - x;  // 3 - x ne calculeaza tipul atunci cind avem adunare
    x = b - a;    // formula de calcul
    break;
  case '*':
    tip = 7 - x;  // 7 - x ne calculeaza tipul ecuatiei cind avem inmultire
    x = b / a;    // formula de calcul
    break;
  case '-':
    tip = 5 - x;  // 5 - x ne calculeaza tipul ecuatiei cind avem scadere
    if ( x == 1 ) // in functie de pozitia lui x
      x = a + b;  // cind este primul, avem x = a + b
    else
      x = a - b;  // cind este al doilea, avem x = a - b
    break;
  case ':':
    tip = 9 - x;  // 9 - x ne calculeaza tipul ecuatiei cind avem impartire
    if ( x == 1 ) // in functie de pozitia lui x
      x = a * b;  // cind x este primul in ecuatie avem x = a * b
    else
      x = a / b;  // cind x este al doilea in excuatie avem x = a / b
  }
  
  fout = fopen( "ecuatie2.out", "w" );
  fprintf( fout, "%d\n%d\n", tip, x ); // afisam tipul ecuatiei si valoarea x
  fclose( fout );

  return 0;
}

Soluția neavînd practic bucle, în afara citirii, complexitatea va fi evident O(1), ca și memoria folosită (deoarece nu folosim vectori).

Problema maraton

Problema maraton a fost dată la ONI 2010 clasa a 7a. Ea este una de simulare. Greutatea problemei constă în găsirea unui mod eficient de a calcula pozițiile semafoarelor la momentul cînd Andrei ajunge la ele. Din păcate problema permite și o soluție forță brută, avînd timpul de executare de o secundă.

Forța brută va actualiza fiecare semafor la fiecare deplasare a lui Andrei. Complexitatea ei este O(n2). Ea va lua 100p. Straniu.

O soluție optimă va actualiza semafoarele o singură dată, la momentul cînd Andrei ajunge la ele. Complexitatea este O(n).

În soluția prezentată mai jos:

  • Vom considera că semafoarele trec printr-un ciclu de zece secunde. Apoi:
    • La începutul secundei 0 își schimbă culoarea în roșu
    • La începutul secundei 5 își schimbă culoarea în galben
    • La începutul secundei 8 își schimbă culoarea în verde
  • În loc de culori vom ține minte pentru fiecare semafor la ce secundă în ciclul său se află el.
  • Astfel, un semafor roșu va porni cu secunda 0, unul galben cu secunda 5, iar unul roșu cu secunda 8
  • Pentru inițializarea timpului semaforului folosim un vector de trei elemente ce memorează numerele de mai sus. El va fi util la o conversie facilă a codului de culoare la secunda semaforului. Mai exact, ts = tinit[culoare + 2];
  • Timpul fiecărui semafor avansează la fiecare secundă modulo 10.
  • Dacă Andrei ajunge la semafor la momentul t, iar la momentul 0 semaforul avea timpul intern ts, înseamnă că la momentul t el va avea timpul intern (t + ts) % 10.
  • Timpul de așteptare la semafor este diferit de zero doar dacă timpul intern al semaforului, ts, este strict mai mic ca 8, caz în care timpul de așteptare va fi 8 - ts.

Cu aceste observații soluția devine foarte scurtă:

#include <stdio.h>

#define TIMP_R 5
#define TIMP_G 3
#define TIMP_V 2
#define TIMP_TOT (TIMP_R + TIMP_G + TIMP_V)

int tinit[3] = { 0, TIMP_R, TIMP_R + TIMP_G }; // momentul semaforului

int main() {
  FILE *fin, *fout;
  int n, k, t, ts, cul, i;

  fin = fopen( "maraton.in", "r" );
  fscanf( fin, "%d%d", &n, &k );
  t = k; // cite secunde au trecut de la inceputul cursei
  for ( i = 0; i < n; i++ ) {
    fscanf( fin, "%d", &cul );   // culoarea semaforului la momentul 0
    ts = tinit[cul + 2];         // calculam timpul semaforului la t=0
    ts = (ts + t) % TIMP_TOT;    // timpul semaforului la momentul t actual
    if ( ts < TIMP_R + TIMP_G )  // daca e necesar, asteptam la semafor
      t += TIMP_R + TIMP_G - ts; // trebuie sa asteptam rosu si galben
    t += k;                      // deplasarea pina la semaforul urmator
  }
  fclose( fin );
  
  fout = fopen( "maraton.out", "w" );
  fprintf( fout, "%d\n", t );
  fclose( fout );

  return 0;
}

Complexitatea ei este O(n) în timp și O(1) ca memorie.

Rezolvări aici [1]

Lecție

Am discutat cele patru probleme de la temă.

Exemple de cod

Program 1

Putem simplifica?

    fscanf(fin, "%d", &n);
    for(i=1; i<=n; i++){
      fscanf(fin, "%d%d", &a, &b);
      v[i]=a;
    }

Program 2

Ce greșeli există?

    ch = fgetc(fin);
    a = 0;
    while (ch != '+' && ch != '-' && ch != '*' && ch != ':'){
      if ('0' < ch && ch < '9')
        a = a * 10 + ch - '0';
      ch = fgetc (fin);
    }

Program 3

Știm că minc este maxim 9. Putem simplifica?

            if(minc>=2 && minc<7){
                s[i]=-2;
                mint=minc-2;
            }else if(minc>=7 && minc<10){
                s[i]=-1;
                mint=minc-7;
            }else{
                mint=minc;
            }

Temă

Tema 20 clasa a 6a

  • numere24 dată la OJI 2018 clasa a 6a
  • turnuri dată la OJI 2018 clasa a 6a

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

Rezolvări aici [2]