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 bila1

Comentarii generale

Felicitări celor ce au reușit o soluție de excepție: Hossu, Voicu, Ilie.
Mențiuni speciale: Nicola, Dobre, care au înjumatățit memoria folosind matrice de tip unsigned short.
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.
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!
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.
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.
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.
Mulți dintre voi mă ajută cu comentarii. Vă mulțumesc!
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!

Rezolvări aici [1]

Lecție

<html5media height="720" width="1280">https://www.algopedia.ro/video/2018-2019/2019-02-21-clasa-6-lectie-info-20-720p.mp4</html5media> 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 6^a

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

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

Rezolvări aici [2]

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

Contents