Clasa a VII-a lecția 16 - 16 ian 2020

From Algopedia
Jump to navigationJump to search

Anunț

Este momentul să ne dezmorțim după vacanță! Duminică 19 ianuarie 2020, ora 15:00, vom organiza un concurs. El va dura o 1h45min și va consta dintr-o singură problemă.

Teme - comentarii generale

  • Felicitări lui Moroșan care a început să trimită rezolvări muncite la teme.
  • Avertisment lui Cadîr. Trebuie să muncești mai mult dacă vrei să îți păstrezi calificarea:
    • Nu ai trimis nici o sursă la concursul din ultima lecție.
    • Nu ai trimis nimic la tema 15, nici măcar după aceea, la arhivă.
    • Am mari îndoieli că sursele trimise la tema 14 sînt ale tale.
  • Avertisment Chivu: surse la mișto la 2x3y5z și zaphod1. Ele sînt probleme de exersat tipul coadă, nu pentru ca tu să îți practici cunoștințele de clasa a cincea.
  • Avertisment Mocanu: nici o rezolvare la 2x3y5z.

Tema 14 - rezolvări

Livada

Problema livada a fost dată la cercul de informatică la liceul Tudor Vianu în 2014.

Comentarii individuale

  • Badea: Folosești sume pe coloane și o coadă, bun. Dar nu folosești sume parțiale pentru vectorul de sume. De aceea faci verificarea unei sume în O(q) în loc de O(1). Ar fi bine să corectezi programul, căci ai și un incorect. Este un algoritm foarte simplu, nu accepta greșeli.
  • Calotă: program solid, clar și corect. Ai oareșice repetiții de cod și redundanțe, dar gîndirea este bună și ordonată, de informatician. Bravo :)
  • Dimulescu: nu inițializa variabile la declarare (int max = 0). Nu declara variabile în mijlocul codului. Nu folosi i și j pentru indici în matrice, folosește l și c. Repeți cod. De ce nu ai corectat problema, la arhivă? Ai greșit exact din cauza repetiției de cod, într-un loc ai scris bine, în altul rău. Iată, tu scrii la început:
  for( i = q; i < n; i++ ){
    sum -= sume[i - q];
    sum += sume[i];
    if( sum > max )
      max = sum;
  }

Apoi, mai jos, pentru același lucru, scrii:

    for( j = q; j <= n - q + 1; j++ ){
      sum -=sume[j - q];
      sum += sume[j];
      if( sum > max )
        max = sum;
    }

Dacă modifici limita greșită din 'for' programul va lua 100p.

  • Dobre: program bun și ordonat, bravo! Încearcă să nu repeți cod, este foarte periculos. Vezi mai jos cum.
  • Marcu: program bun și ordonat, bravo! Încearcă să nu repeți cod, este foarte periculos. Vezi mai jos cum.
  • Mocanu: nu folosi i și j pentru indici în matrice! Nu denumi matricea v[][]! Aș fi vrut comentarii, pentru a înțelege de ce folosești t2[]. Nu este nevoie de el. Vezi soluția.
  • Mușat: program bun, ordonat și cu comentarii, bravo! Apreciez că ai folosit o coadă cu lungime putere a lui 2, bravo din nou! Încearcă să nu repeți cod, este foarte periculos. Vezi mai jos cum.
  • Popescu: program bun, bravo! Încearcă să nu repeți cod, este foarte periculos. Vezi mai jos cum.
  • Rughiniș: Nu folosi i și j pentru indici în matrice, folosește l și c, mai ales nu folosi i și j interschimbabil, ba drept linii ba drept coloane. Literele seamănă, le mai și interschimbi? Ai depășiri evidente de matrice, se vede din avion cînd te uiți pe program ai un for cu condiție i<=n. Altfel cod OK, aș vrea mai multe comentarii. Ai unele repetiții de cod, evită-le, sînt periculoase.
  • Teodorescu: program bun și ordonat, bravo! Încearcă să nu repeți cod, este foarte periculos. Vezi mai jos cum.
  • Togan: am discutat soluția la curs. Tu folosești o coadă, dar nu folosești un vector de sume pe coloană. De aceea algoritmul este ineficient și depășești timpul. Nu pot să înțeleg rapid ce faci, deoarece nu ai nici un comentariu. Iar ai început să folosești while acolo unde ai de fapt for? Informatica este ușoară odată ce descifrăm tainele diferenței între for și while :)

Alee

Problema alee a fost dată la OJI 2007 clasa a 10a. Ea este o aplicație directă a algoritmului de parcurgere pe lățime a unei matrice (Lee).


Rezolvări aici: [1]

Tema 14 opțională - rezolvări

Insule

Problema insule a fost dată la OJI 2009 clasa a 10a.

Tema 15 - rezolvări

2x3y5z

Problema 2x3y5z este o problemă clasică.

Comentarii individuale

  • Badea: Rezolvare bună, dar nu folosești coadă drept care folosești de 5 ori mai multă memorie. While-urile acelea sînt inutile, indicii vor avansa la momentul cînd numărul lor este selectat cu o singură poziție (deci vorbim de un if nu de un while).
  • Calotă: apreciez efortul. Dar ideea pare extrem de complicată. Nu ai un comentariu asupra metodei folosite, iar metoda este creață rău. Nu voi încerca să comentez.
  • Dimulescu: problemă clasică, rezolvare clasică. De ce să nu ne luăm după turmă, nu? Aceleași comentarii ca la începutul anului: nu inițializa variabile la declarare, declară toate variabilele la început de funcție sau de 'main'. Nu ai folosit o coadă drept care folosești de 5 ori mai multă memorie.
  • Dobre: modul în care calculezi minimul este urît. Rezolvare bună, dar nu folosești coadă drept care folosești de 6 ori mai multă memorie. While-urile acelea sînt inutile, indicii vor avansa la momentul cînd numărul lor este selectat cu o singură poziție (deci vorbim de un if nu de un while).
  • Marcu: apreciez că ai încercat să trimiți o soluție. Dar, pe lîngă că este o soluție slabă, tema de azi era în legătură cu cozi. Tu nu ai folosit nici o coadă.
  • Mușat: o soluție simpatică și interesantă ca idee, dar cu următoarele probleme:
    • Nu pare corectă matematic. Ai demonstrat?
    • Nu are nici o treabă cu cozile, subiectul lecției. Dacă nu vrei să înveți să implementezi cozi ai o soluție simplă, poți să nu mai vii la IQ Academy.
    • Fără comentarii nu o pot corecta. Mi-ar lua prea mult timp să fac inginerie inversă pe codul tău.
  • Mocanu: nici o sursă?
  • Popescu: problemă clasică, rezolvare clasică. De ce să nu ne luăm după turmă, nu? Nu ai folosit o coadă drept care folosești de 5 ori mai multă memorie.
  • Rughiniș: ok, am înțeles că nu ai avut timp să trimiți temele, deoarece călătoriile sînt mai importante decît IQ Academy. Apreciez că ai muncit ulterior și ai trimis la arhivă. Dar programul tău este științifico-fantastic! Cum ar fi de presupus să ți-l corectez cînd face minuni de neînțeles și nu ai pus măcar un comentariu? Remus, ne supărăm! Tratează serios clubul curioșilor dacă nu vrei să rămîi pe din-afară!
  • Teodorescu: ideea algoritmului este bună. Mă bucură că implementarea este a ta. Felul urît în care scrii de trei ori același cod o dovedește :) Dar nu ai folosit coadă, tema lecției. Folosești de 5 ori mai multă memorie. Nu mi-e clar ce este cu acele while-uri. Cred că indicele crește mereu cu unu.
  • Togan: Părțile bune ale programului tău sînt că funcționează, ia 100p și e așa de încîlcit încît mi-e clar că e al tău. Are semnătura ta pe el. Părțile proaste sînt că nu folosești coadă drept care folosești de 5 ori mai multă memorie. Că ai un calcul de minim care îmi ridică părul în cap (deși nu prea am păr). Iar while-urile acelea sînt inutile, indicii vor avansa la momentul cînd numărul lor este selectat cu o singură poziție (deci vorbim de un if nu de un while).

Zaphod1

Problema zaphod1 a fost dată la cercul de informatică al liceului Tudor Vianu. Ea cere să se genereze o secvență clasică, numită secvența Hofstadter. Este o secvență studiată relativ recent, despre care nu se știu așa multe lucruri.

Comentarii individuale

  • Badea: Ai nimerit peste soluție, dar nu știi dacă este corectă sau doar ai trecut testele. Ai redus memoria artificial, sperînd să funcționeze. Speranța nu e o idee bună cînd rezolvăm probleme de informatică. Vezi mai jos demonstrația că programul tău nu numai că este corect, dar poate folosi, în fapt, doar o optime din memorie.
  • Calotă: program principial corect și foarte ordonat. Soluția depășește memoria. Vezi cum reducem memoria în soluția de mai jos.
  • Dimulescu: Aceleași comentarii ca la începutul anului: nu inițializa variabile la declarare, declară toate variabilele la început de funcție sau de 'main'. Programul este principial bun, dar consumator de memorie. Ar funcționa cu o coadă mult mai mare, dar nu ai memorie pentru ea. Vezi cum micșorezi memoria în soluția de mai jos.
  • Dobre: Program bun! Bravo! Nu mi-e clar dacă ai nimerit peste soluție, dar nu știi dacă este corectă sau chiar ai calculat memoria necesară. Pentru că dacă calculai îți dădeai seama că nu ai nevoie să memorezi numere long long în coadă. Dacă ai redus memoria artificial, sperînd să funcționeze, nu e o idee bună. Speranța nu e o idee bună cînd rezolvăm probleme de informatică. Vezi mai jos demonstrația că programul tău este corect.
  • Marcu: apreciez că ai încercat să trimiți o soluție. Dar, pe lîngă că este o soluție slabă, tema de azi era în legătură cu cozi. Tu nu ai folosit nici o coadă. În plus, dacă ai o idee netrivială m-ar fi ajutat mult comentarii, să o pot înțelege și corecta.
  • Mocanu: coada denumită d[], indicii prim și ultim sînt j și z, nu ai comentarii, codul este cu variabile denumite ca litere. Cam ce șanse am să înțeleg ce ai vrut să faci? Mocanu, ne supărăm!
  • Mușat: pescuim pînă la moarte! Ai nimerit peste soluție, dar nu știi dacă este corectă sau doar ai trecut testele. Ai redus memoria artificial, sperînd să funcționeze. Speranța nu e o idee bună cînd rezolvăm probleme de informatică. Vezi mai jos demonstrația că programul tău nu numai că este corect, dar poate folosi, în fapt, doar o optime din memorie. Nu inițializa variabile la declarare! Ar ajuta mult comentariile, într-un program în care toate variabilele sînt litere. Dar lasă, mai bine să vedem dacă mă prind. Constantele definite sînt pentru începători, avansații pun direct numere prin program!
  • Popescu: programul este dens și greu de urmărit fără comentarii. Pare corect, un program bine scris, folosești cozi, iar dimensiunea cozilor este corectă. Cred că dacă declarai lungimea cozii ca putere a lui doi nu ai fi depășit timpul la ultimul test. Nu uita, împărțirile la puteri ale lui doi nu sînt de fapt împărțiri!
  • Rughiniș: ai avertisment grav de compilare. Avertisment și ție, precum am discutat lecția trecută. Programul este principial corect, dar folosește prea multă memorie. Vezi cum reducem memoria în soluția de mai jos.
  • Teodorescu: idee bună, algoritm încîlcit. Nu folosești coadă, folosești mult mai multă memorie. Mi-e greu să înțeleg toate detaliile pentru că nu ai comentarii. Folosești trei vectori cînd este necesar doar unul.
  • Togan: program bun ca idee, bravo! Te-ai prins de o limită rezonabilă, chit că un pic mare. Implementarea lasă de dorit: încîlceli, cazuri particulare introduse de tine, etc. Comentariile ar ajuta enorm.

Inginer

Problema inginer a fost dată la .campion 2008.

Romeo și Julieta

Problema Romeo și Julieta a fost dată la OJI 2004 clasa a 10a.

Ea este clasică, cerînd, în mare, două parcurgeri BFS pe matrice (Lee), una pentru Romeo și una pentru Julieta. Apoi căutăm poziții de distanță egală, luînd minimul.

Puncte delicate:

  • Distanța egală minimă nu este neapărat optimă ca timp de întîlnire. În exemplul din enunț ei s-ar putea întîlni mai repede dacă unul din ei ar sta un pas pe loc, așteptîndu-l pe celălalt (3 pași în loc de 4). Acest lucru nu este permis, de aici și ineficiențele.
  • Atenție la resetarea algoritmului Lee, coada.
  • O implementare eficientă nu scrie de două ori Lee, ci transmite ca parametru matricea de distanțe.

Rezolvări aici: [2]

Lecție

<html5media height="720" width="1280">https://www.algopedia.ro/video/2019-2020/2020-01-16-clasa-7-lectie-info-16-720p.mp4</html5media>

Tipul deque (coadă dublă)

Coada dublă este o coadă la care putem adăuga și scoate din ambele capete. Poate fi considerată ca o coadă și o stivă într-o singură structură de date, cu diferența că în coada dublă putem adăuga la începutul cozii.

Cum implementăm o coadă dublă?

O putem implementa la fel ca pe o coadă, într-un vector circular și folosind doi indici, primul și ultimul.

  • Adăugarea unui element la final de coadă dublă, precum și eliminarea unui element de la început de coadă dublă se face întocmai ca la o coadă obișnuită.
  • Eliminarea unui element de la final se face astfel:
int pop() {
  ultim = (ultim - 1 + QMAX) % QMAX;
  return coada[ultim];
}
  • Adăugarea unui element la început se face astfel:
void pushFront( int e ) {
  prim = (prim - 1 + QMAX) % QMAX;
  coada[prim] = e;
}

Vom vedea că operațiunile pe biți pot simplifica puțin modificarea indicilor prim și ultim.

Observație: toate operațiunile pe o coadă dublă se fac în timp constant, O(1).

Maximum în fereastră glisantă (maximum over a sliding window)

  • Enunț: dîndu-se un șir de n numere considerăm cele n – k + 1 subsecvențe de k numere consecutive în șir (denumite și "ferestre" de lungime k). Putem vedea aceste ferestre ca pe o singură fereastră, deplasabilă, care ne dă acces la k elemente din vector odată. Se cere ca pentru fiecare fereastră să se găsească maximul.
  • Algoritmul de rezolvare trivial (forță brută) recalculează maximul pentru fiecare din ferestre, avînd complexitate O(kn).
  • Pentru a reduce complexitatea găsirii maximului procedăm astfel: luăm prima fereastră, de la 0 la k-1. Să spunem că maximul se află pe poziția p1. Pe măsură ce vom deplasa fereastra este imposibil ca elementele din-naintea maximului să fie vreodată maximul ferestrei, deoarece ele vor face parte împreună cu maximul din această fereastră. Să considerăm poziția celui mai mare element după maxim și la dreapta lui, în fereastră. Fie ea p2. Rezultă că nici un element pe pozițiile intermediare i, p1 < i < p2, nu poate fi vreodată maxim în fereastră, deoarece aceste elemente vor fi împreună cu p2 în toate ferestrele care le conțin. Similar, considerînd p3 poziția următorului maxim, nici un element între p2 și p3 nu va putea fi maxim.
În figură noul maxim va elimina din coadă maximele 2 și 3. Coada rămasă va conține maximul 1 și maximul nou

În urma acestor observații apare următorul algoritm:

  • Memorăm toate maximele descrescătoare din prima fereastră, într-o coadă dublă. Primul element din coadă este maximul ferestrei.
  • Cînd deplasăm fereastra trebuie să actualizăm structura de maxime din coadă. Pentru aceasta dăm atenție elementului care dispare din fereastră și celui care intră în fereastră.
  • Dacă elementul care iese nu este maximul curent, nu avem nimic de făcut. Maximul curent este primul din coadă (cel mai din stânga).
  • Dacă este maximul curent vom scoate primul element din coada de maxime.
  • Dacă elementul proaspăt adăugat în fereastră este mai mic decît ultimul maxim din coadă se adaugă la coadă. În caz contrar el va "arunca" ultimul element, iar și încercăm din nou adăugarea în coadă.
  • Rezultă că noul element din fereastră "aruncă" toate elementele de la urma cozii strict mai mici ca el, iar apoi îl adăugăm normal la coadă.

Observații

  • Atunci cînd eliminăm de la începutul cozii maximul care iese din fereastra glisantă coada dublă acționează ca o coadă.
  • Atunci cînd eliminăm din coadă toate elementele de la final care sînt mai mici decît elementul ce intră în fereastra glisantă, coada dublă acționează ca o stivă.
  • Atunci cînd adăugăm la final elementul care intră în fereastra glisantă coada dublă acționează atît ca o stivă cît și ca o coadă.

Exemplu de cod

Iată un exemplu de implementare. În programul următor:

  • n este numărul de elemente citit la intrare
  • k este mărimea ferestrei glisante
  • deq[] este coada dublă ce memorează k elemente, dar va fi dimensionată la următoarea putere a lui 2
  • rasp[] este vectorul de răspunsuri, dar care este folosit și la stocarea elementelor de la intrare, pentru a ști ce iese din fereastră; rasp[i] este maximul din fereastra ce începe la poziția i.
  fin = fopen( "mfg.in", "r" );
  fscanf( fin, "%d%d", &n, &k );
  for ( i = 0; i < n; i++ ) {
    if ( i >= k ) {
      if ( (max = deq[prim]) == rasp[i - k] ) // daca max iese din fereastra
        prim = (prim + 1) % MAXK_P2;          // elimina maximul din fereastra
      // stocheaza raspunsul pentru fereastra [i-k..i-1]
      // este ok sa suprascriem rasp[i - k], el nu va mai fi necesar
      rasp[i - k] = max; 
    }
    
    rasp[i] = h = readInt(); // stocam inaltimea curenta, e nevoie la iesire
    while ( ultim != prim && deq[ultim - 1] < h ) // elimina din coada
      ultim = (ultim - 1 + MAXK_P2) % MAXK_P2;    // cata vreme h e mai mare
    deq[ultim] = h;          // depunem inaltimea curenta in coada
    ultim = (ultim + 1) % MAXK_P2;
  }
  fclose( fin );
  rasp[n - k] = deq[prim];   // stocam separat ultimul maxim - caz particular

Complexitate

  • La prima vedere pare că, la fiecare pas, putem elimina k elemente din coada dublă, deci complexitatea ar părea O(kn).
  • Folosind analiza amortizată rezultă complexitatea reală ca fiind O(n). Fiecare element este adăugat în coadă o dată și este scos cel mult o dată.
  • Memoria suplimentară folosită este mărimea maximă a cozii, adică O(k).

Aplicație: numărul maxim ce se poate forma prin eliminarea a K cifre

Enunț: dat un număr de N cifre, dorim să eliminăm K cifre. Să se afișeze numărul maxim ce se poate forma astfel.

Cum rezolvăm această problemă și ce legătură are ea cu maximul în fereastră glisantă?

La prima vedere problema pare complicată. Numărul este foarte mare. Și atunci încercăm să o simplificăm:

  • Putem afla care este prima cifră a acestui număr?
  • Știm că numărul va avea N-K cifre.
  • Este clar că numărul va începe cu una din primele K+1 cifre. De ce? Deoarece dacă el începe cu a K+2-a cifră, ar trebui să eliminăm K+1 cifre de la începutul numărului, ceea ce nu putem.
  • Vrem ca prima lui cifră să fie cît mai mare.
  • Este, deci, logic, că prima cifră a numărului va fi maximul din primele K+1 cifre. Să presupunem că cifra maximă este a cincea.
  • Pentru ca a cincea cifră să devină prima trebuie să eliminăm primele patru cifre.
  • Am rămas deci cu restul numărului, ce are N-5 cifre (patru eliminate, una selectată), din care mai avem de eliminat K-4 cifre.
  • Putem deci relua metoda, cu un număr mai mic.

Ce facem dacă în primele K+1 cifre avem mai multe maxime dintre care să alegem? Vom alege primul maxim, deoarece nu vrem să eliminăm cifre maximale.

Rezultă următorul algoritm:

Algoritmul 1

1 Citește de la intrare primele K cifre.
2 Cîtă vreme mai avem cifre de eliminat (K > 0)
    2.1 Citește încă o cifră de la intrare.
    2.2 Calculează maximul dintre primele K+1 cifre. Fie cifra C pe poziția P.
    2.3 Afișează la ieșire cifra C.
    2.4 Elimină din cifrele memorate primele P-1 cifre.
    2.4 K = K - (P - 1)
3 Citește cifrele rămase la intrare și afișează-le.

Observații:

  • Algoritmul selectează, pe rînd, cifrele rămase, în loc să se concentreze pe cifrele eliminate.
  • Algoritmul nu specifică cum găsim maximul cifrelor. O căutare liniară ar duce la un algoritm ineficient.

Cum găsim eficient maximul din primele K+1 cifre? Folosind o coadă dublă. Vom avea o fereastră glisantă de lungime variabilă. Ea va avea la început lungimea K+1, iar apoi va scădea pe măsură ce scade K

Rezultă algoritmul:

Algoritmul 2

1 Depune primele K cifre de la intrare într-o coadă dublă, păstrînd doar maxime consecutive descrescătoare, dar memorînd și pozițiile lor.
2 Cîtă vreme mai avem cifre de eliminat (K > 0)
    2.1 Citește încă o cifră de la intrare și depune-o în coadă cu poziția sa, eliminînd cifrele mai mici ca ea.
    2.2 Prima pereche din coadă va fi maximul C, cu poziția sa P.
    2.3 Afișează la ieșire cifra C.
    2.4 Elimină prima pereche din coadă.
    2.4 K = K - (P - 1)
3 Citește cifrele rămase la intrare și afișează-le

Observații:

  • Algoritmul se poate aplica și pentru numărul minim, cu o singură diferență: nu putem alege ca primă cifră minimă o cifră zero. Următoarele cifre pot fi zero.
  • În realitate, dacă urmărim acest algoritm cu atenție, coada va conține întotdeauna maximele celor K+1 elemente din care dorim să găsim maximul. Explicație: cifrele eliminate sunt eliminate și din coadă. Singura cifră care dispare din coadă este cea afișată, pe care o compensăm la pasul 2.1 citind încă o cifră.

Astfel, algoritmul de mai sus se simplifică, nemaiavând nevoie să stocăm indici, ci doar valori. Să vedem.

Algoritmul 3

1 Depune primele K cifre de la intrare într-o coadă dublă, păstrînd doar maxime consecutive descrescătoare.
2 Cîtă vreme mai avem cifre de citit
    2.1 Citește încă o cifră de la intrare și depune-o în coadă, eliminînd cifrele mai mici ca ea.
    2.2 Prima cifră din coadă va fi maximul C
    2.3 Afișează la ieșire cifra C.
    2.4 Elimină cifra C din coadă.

Discuție probleme temă

Ambele probleme de la temă cer calculul numărului minim/maxim obținut după eliminarea unor cifre. Genul acesta de prelucrare, eliminarea unor cifre ale unui număr astfel încît numărul rămas să fie maxim (sau minim) apare des la olimpiade:

  • Problema cuburi s-a dat la ONI 2012 clasa a 8a. Ea cere eliminarea unui număr mic de cifre, totdeauna 3, ceea ce înseamnă că nu sîntem obligați să implementăm o coadă dublă pentru a o rezolva, putem calcula minimul prin forță brută.
  • Problema maxim este o problemă de clasa a 5a la origine, adaptată pentru clasa a 7a. Rezolvați-o folosind algoritmul de mai sus.
  • Atenție: rezolvarea voastră la problema maxim trebuie să folosească o coadă dublă și algoritmul de mai sus. Scopul este să învățăm să implementăm coada dublă.
  • Notă: cei cărora le plac provocările, încercaţi să rezolvaţi problema maxim cu memorie O(Σ), unde Σ este numărul de cifre, adică 10. Pentru aceasta trebuie să modificați implementarea cozii duble.

Fulgerică (test fulger)

Găsiți un algoritm la următoarea problemă și explicați-l pe o foaie de hîrtie. Dacă nu vă descurcați să îl explicați puteți scrie cod. Sau puteți scrie ambele. Important este ca algoritmul să se înțeleagă și să fie corect. Atenție! Spre deosebire de varena, vi se cere un algoritm corect, echivalentul unei rezolvări care să treacă toate testele. Nu gîndiți la modul "cum fac să iau cît mai multe puncte". Nu se acceptă "mînăreli". Voi corecta lucrările personal. Nu vă concentrați pe citire, sau scriere. O soluție poate fi descrisă la modul "citim numerele într-un vector, le sortăm, și apoi testăm dacă fiecare număr este mai mare cu unu decît cel din-naintea lui în vectorul sortat".

Suită

Se dau la intrare un milion de numere între 0 și 1018. Să se spună dacă după ordonare ele pot forma o suită. O suită este un șir de numere în care fiecare număr din șir este cu unu mai mare decît cel din-naintea lui. De exemplu 8 6 7 5 poate fi suită în vreme ce 5 4 5 6 nu este suită și nici 8 5 6 4.

La ieșire veți afișa 1 dacă numerele de la intrare pot forma o suită, sau 0 în caz contrar.

Atenție: puteți folosi maxim 3MB de memorie, pe lîngă cea ocupată de program (codul executabil).

Temă

Tema 16 clasa a 7a

  • cuburi dată la ONI 2012 clasa a 8a
  • maxim dată la ONI 2007 clasa a 5a

Rezolvări aici [3]