Sfaturi pentru olimpiadă

Iată cîteva sugestii pentru olimpiadă.

Ce să faceți / ce să nu faceți

Ce să faceți

Odihnă: odihniți-vă cu o zi înainte. Relaxați-vă cu activitatea favorită. Mergeți la un film, jucați jocul vostru preferat, etc. Încercați să nu vă gîndiți la concurs.
Ceas: aveți un ceas la voi. Nu ceasul calculatorului, al telefonului sau al smartphone-ului. Fiți conștienți de trecerea timpului, nu vă treziți din visare cînd mai este un sfert de oră. Pentru aceasta un ceas așezat pe banca de lucru este ideal. Nu uitați: toate celelalte ceasuri pot fi incorecte, sau să moară.
Țineți socoteala timpului: notați ora începerii concursului pe foaie. Verificați la final că ați avut tot timpul promis. Dacă aveți probleme cu calculatorul și cereți ajutorul supraveghetorului notați timpul cînd ați fost întrerupți și apoi timpul cînd reveniți la un calculator funcțional. Aveți dreptul la o prelungire a timpului egală cu timpul pierdut.
Cereți-vă drepturile: dacă vă opresc mai devreme decît e cazul, sau dacă ați pierdut zece minute din cauza unui calculator care nu a funcționat și nu vi se dau, cereți respectuos să vi se extindă timpul cu acele minute. Supraveghetorii pot uneori să uite, olimpiada este stresantă și pentru ei. Dacă nu înțelegeți textul unei probleme, după ce l-ați citit cu mare atenție, puneți întrebări pentru clarificare (formulate astfel încît răspunsul să fie 'DA' sau 'NU').
Low hanging fruit: rezolvați problema mai ușoară prima. Citiți toate problemele la început și hotărîți-vă care este mai ușoară. Cu ea începeți. Puteți inclusiv să rezolvați subpunctele mai ușoare primele. De exemplu puteți să rezolvați problema 1 punctul a), apoi problema 2 punctul b).
Moral ridicat: intrați în sală încrezători în voi. Sînteți printre cei mai buni din țară, aveți puterea să vă clasați printre primii din țară. Propuneți-vă să luați punctaj maxim și reamintiți-vă că puteți acest lucru.
Probleme grele: atunci cînd constatați că problemele sînt grele nu vă speriați. Bucurați-vă! Este cea mai bună situație pentru voi. Aveți numai de cîștigat: fie știți să faceți problema, caz în care este perfect, căci problema fiind grea v-ați asigurat că veți fi mai sus ca ceilalți. Fie nu știți să faceți problema și atunci care este șansa ca cei mai slabi ca voi să știe să o facă? Temeți-vă de problemele ușoare, pe care știu toți să le facă. Voi le veți gîndi, ceilalți le vor picta la perfecție.
Atenție: fiți foarte atenți la detalii: la numele fișierelor de intrare/ieșire; la numele sub care trebuie să salvați programul C; la setările de proiect CodeBlocks de care am vorbit: -Wall și -O2; la locul unde ați salvat proiectul, și numele proiectului în caz că aveți nevoie să le copiați în altă parte.

Ce să nu faceți

Nu îngrășați porcul în ajun: nu faceți probleme în ultima clipă . Vă veți extenua inutil. În urma stresului s-ar putea să nu reușiți să le faceți, ceea ce vă va demoraliza. Aveți nevoie de moral ridicat la concurs.
Nu vă panicați: panica ucide creierul. Panica vă face să gîndiți mai încet și să doriți în subconștient să ieșiți din sală. Controlați-o. Nu uitați că o problemă grea, pe care nu știți să o faceți, vă avantajează, pentru că probabil nici ceilalți nu știu, pe cînd voi aveți o șansă să luați puncte pe ea.
Nu-i băgați în seamă pe cei ce se dau mari: unii elevi spun cu voce suficient de tare să fie auziți, în timpul concursului, lucruri de genul 'aaah, am făcut-o și pe asta, super' sau 'am rupt, sigur iau suta', etc. Este modul lor inconștient de a vă demoraliza. De obicei ei se clasează slab. Ignorați-i. De asemenea veți vedea că unii dintre concurenți părăsesc sala mai devreme cu o oră cu un aer fericit, eventual spunînd 'sigur mă calific' sau 'am făcut tot, yesss'. Ignorați-i. Și ei se clasează slab. Nu vă demoralizați indiferent cîți elevi ies din sală. Lupta voastră nu este cu ei, ci cu problemele și punctele.
Nu ieșiți mai devreme din sală: dacă nu ați terminat problemele continuați să vă gîndiți la o soluție. Dacă ați terminat problemele și vă plictisiți creați mai multe teste pe care să le testați. Nu uitați: nimănui nu-i pasă cît de repede ați ieșit. Nu luați puncte suplimentare pentru asta.
Nu modificați în ultima clipă un program care funcționează: riscați să nu aveți timp să-l testați și să luați zero puncte la acea problemă.
Nu vă îngrijorați de părerea noastră: noi, instructorii, știm bine care este valoarea voastră. Nu avem nevoie de un rezultat la olimpiadă să aflăm. Nu o să ne vedeți vreodată supărați pe voi pentru că nu ați luat punctaj bun. Dimpotrivă, orice veți face vom fi mîndri de voi pentru cît de departe ați ajuns în numai cîteva luni. Grija voastră trebuie să fie rezolvarea problemelor, nu noi. Noi sîntem de partea voastră. Chiar dacă la cerc sau la clasă, cînd sîntem între noi, vă certăm sau ne mai supărăm pe voi, în momentul cînd ați ieșit din liceu să vă "luptați" cu olimpiada pentru noi, sîntem de aceeași parte a baricadei.

Lecție

În continuare vom discuta rezolvări ale unor probleme clasice cu vectori.

Căutare în vector

Se dă un vector v de n elemente și un extra element e. Să se găsească poziția p în v unde apare prima oară elementul e. Dacă elementul e nu apare p va avea valoarea n. O soluție elegantă care nu iese forțat din buclă și care nu folosește stegulețe este:

// avem vectorul v de n elemente si o valoare e de gasit in acest vector
p = 0;
while ( p < n && v[p] != e )
  p++;
// acum p este fie pozitia primei aparitii a lui e, fie n daca e nu exista in v

Inserare în vector

Se dă un vector v de n elemente, un extra element e și o poziție p. Să se insereze elementul e la poziția p. În final elementul e va fi pe poziția p în vector, iar elementele de la poziția p pînă la final vor fi deplasate spre final cu o poziție. Vom considera că p este o poziție validă, între 0 și n.

// avem vectorul v de n elemente si o valoare e de inserat la poziția p
for ( i = n - 1; i >= p; i-- ) // deplasăm elementele spre dreapta
  v[i+1] = v[i];
v[p] = e;
n++; // vectorul are acum n+1 elemente!

Ștergere din vector

Se dă un vector v de n elemente și o poziție p. Să se elimine elementul de la poziția p din vector. Elementele de la poziția p pînă la final se vor deplasa către începutul vectorului cu o poziție.

// avem vectorul v de n elemente si o poziție p ce trebuie eliminata
for ( i = p + 1; i < n; i++ ) // deplasam elementele spre stinga
  v[i-1] = v[i];
n--; // vectorul are acum n-1 elemente!

Răsturnare vector

Se dă un vector v de n elemente. Inversați poziția elementelor în vector. Avem mai multe soluții posibile, una foarte simplă este să folosim doi indici, unul care crește și unul care descrește. Vom interschimba elementele celor doi indici. Vom repeta acest lucru pînă ce indicii se întîlnesc.

// avem vectorul v de n elemente, vrem sa il rasturnam
i = 0;
j = n – 1;
while ( i < j ) {
  aux = v[i];
  v[i] = v[j];
  v[j] = aux;
  i++;
  j--;
}

Rotire vector

Se dă un vector v de n elemente. Să se rotească vectorul cu o poziție către început cu o poziție. De exemplu [1, 6, 2, 7, 4, 3, 2] se va transforma în [6, 2, 7, 4, 3, 2, 1].

// avem vectorul v de n elemente, vrem sa il rotim la stinga cu o pozitie
aux = v[0];
for ( i = 1; i < n; i++ )
  v[i-1] = v[i];
v[n-1] = aux;

Mutare zerouri la coadă

Se dă un vector v de n elemente. Să se modifice ordinea elementelor în vector astfel încît toate elementele zero să fie la coada vectorului. Celelalte elemente nu trebuie să își păstreze ordinea originală (pot fi în orice ordine). O soluție posibilă este să mergem cu doi indici, unul crescător și unul descrescător. Cel crescător avansează pînă ce găsește un zero. Apoi interschimbă cu celălalt indice, pe care îl scade.

// avem vectorul v de n elemente, vrem sa mutăm zerourile la coada
i = 0;
j = n – 1;
while ( i < j ) {
  if ( v[i] == 0 ) { // daca avem un zero pe pozitia i
    v[i] = v[j];     // il trecem la coada, interschimbind cu pozitia j
    v[j] = 0;
    j--;             // deoarece pe pozitia j avem un zero, putem sa scadem j
  } else
    i++;             // daca avem nonzero pe pozitia i putem avansa i
}

Există și soluții mai eficiente pe care nu le vom discuta aici.

Comparație vectori

Dați doi vectori de caractere să se spună care este ordinea lor lexicografică. Cu alte cuvinte, ordinea în care vor apărea cele două cuvinte în dicționar.

Rămîne ca temă.

Rotire multiplă de vector *

Se dă un vector v de n elemente și un număr k. Să se rotească vectorul cu o poziție către început cu k poziții. De exemplu, pentru k=3 [1, 6, 2, 7, 4, 3, 2] se va transforma în [7, 4, 3, 2, 1, 6, 2].

Rămîne ca temă pentru cei dornici să se lupte cu o problemă grea.

Discuție probleme temă

Trebuia să avem o discuție despre rezolvarea problemelor de la temă, dar nu am mai avut timp.

magic1 dată la OJI 2011 clasa a 5^a
felinare dată la ONI 2008 clasa a 5^a

Temă

Rezolvați următoarele probleme:

Tema 24 clasa a 5^a

compus problemă de exersat operațiile clasice pe vectori, rezolvare aici [1]
magic1 dată la OJI 2011 clasa a 5^a
felinare dată la ONI 2008 clasa a 5^a

Rezolvări aici [2]

Opțional, teme de gîndire:

Comparația a doi vectori: dați doi vectori, v de lungime m și w de lungime n să se spună dacă v este mai mic, egal, sau mai mare decît w. Gîndiți-vă cum ați face această problemă și încercați să scrieți o bucată de program C care să o rezolve.
Grea: rotk (rotație multiplă vector fără a face rotații repetate cu unu). Rezolvare aici [3]

Clasa a V-a lecția 24 - 11 feb 2014

Contents