Revista Informatica CNTV - Nr. 1

1

CUPRINS

I. InfoCNTV la C.N.T.V. 2

II. Probleme de concurs - OJI 4

III. Articole. Studii de caz

Elemente de combinatorică

Rezolvarea numerică a ecuațiilor algebrice și

transcendente

Cum ne influențează viața invazia de biți?

Studiu de caz – problema rucsacului

10

10

14

17

18

IV. Ocolul pamântului în ... Informatică - marca C.N.T.V. 21

V. Programatorul cel viteaz ... 100 dintr-o lovitură!

Soluții de 100 de puncte la probleme de concurs

Rezultate la olimpiade și concursuri naționale 2013-2014

26

26

37

VI. Gânduri, pasiuni, experiențe...

Cariera în IT, de la provocare tehnică la creativitate

Ce începe cu "I" și se termină cu "nformatică"

Totul despre participarea mea la Infomatrix

Ce este Cinema 4D?

38

38

39

40

41

VII. Mici programatori ... viitori (posibil !) mari programatori

Probleme propuse și rezolvate de elevi

43

43

VIII. Informatică DAR ... nu numai!

Algoritmii imaginației

Informatica în rime

De la GOOGLE citire ...

45

45

45

46

2

I. ”InfoCNTV” la C.N.T.V.

Pentru toți cei care au trecut pragul acestei școli - elevi, absolvenți, profesori,

C.N.T.V. ne poartă cu gândul către Cunoaștere, Noutate, Tradiție, Valoare.

Și pentru că măsura valorii unei școli rezidă nu numai în valoarea profesorilor

dar, mai ales, în reușita în viață a elevilor pe care i-a format, cu o tradiție de 22 de ani,

profilul Matematică – Informatică a adus colegiului, în timp, elevi de excepție care au

devenit absolvenți cu strălucite cariere în IT. De aceea, am considerat că cea mai

frumoasă idee a acestei reviste, pe lângă consistența informatică, este aceea de a

cunoaște (reaminti) câțiva dintre ei, care au răspuns, cu drag, invitației de a ne fi

alături în acest demers.

Pentru acest prim număr al revistei de Informatică, cel mai potrivit argument

pentru a vă convinge să parcurgeți paginile revistei noastre, sunt rândurile scrise de

Andrei Homescu, olimpic național la Informatică al C.N.T.V., actualmente doctorand la

U.C. IRVINE-USA, un exemplu care poate insufla inspirație și poate însufleți imaginația

actualilor elevi, determinându-i să-și clădească visurile pe studiu și seriozitate.

Așteptăm și totodată invităm toți absolvenții să facă parte din proiectul nostru de

a readuce alături marea familie a IT - iștilor C.N.T.V. -iști, care ne reprezintă cu cinste pe

mapamond (și vă veți convinge că este așa, citind în continuare…).

Prof. Gabriela Nodea

Idealuri devenite realitate!

Andrei Homescu, PhD Candidate at UC Irvine, USA

Anii de liceean la Colegiul Naţional „Tudor

Vladimirescu” din Tg-Jiu şi-au lăsat amprenta asupra mea prin profesionalismul dascălilor mei şi dinamismul permanent al colegilor.

Premiile anuale, obţinute la Olimpiada Naţională de Informatică (2001 - Premiul III, 2002 - Premiul II, 2003 - menţiune şi selectare Lot naţional, 2004 - Premiul II) şi la numeroase alte concursuri, au conturat alegerile ce au urmat în cariera mea. În acei ani ştiam doar că-mi doresc ca activitatea mea să fie utilă! Nu anticipam cum se va realiza visul meu, dar alegerile pe care le-am făcut au fost mereu legate de importanţa muncii şi mai puţin de partea financiară! Acum nu regret fiindcă cele două componente se îmbină intrinsec!

În anul 2009 am absolvit Facultatea de Calculatoare din cadrul Universităţii Politehnica din Bucureşti.

Am continuat să particip la concursuri de programare şi am reprezentat facultatea la 3 ediţii consecutive ale concursului ACM pentru Europa de Sud-Est, obţinând locuri de top. În anii de facultate am participat împreună cu prietenii mei şi la alte concursuri internaţionale, toate în Europa.

3

În 2008 am fost admis la un internship la Google- Mountain View California, iar licenţa am pregătit-o în 2009 în Finlanda, la Tampere, în cadrul unei burse Erasmus.

Cele patru luni petrecute la Tampere University of Technology m-au apropiat de ceea ce înseamnă cercetare adevărată. Aprecierea de care m-am bucurat acolo mi-a întărit convingerea că încă aveam multe idei neexplorate, că beneficiez de o oportunitate de dezvoltare profesională, iar activitatea desfăşurată acolo a influenţat deciziile mele ulterioare.

Când am absolvit facultatea, aveam de făcut alegerea vieţii: să merg să lucrez la Google sau Facebook sau să mă înscriu la doctorat. Am aplicat la un internship la Facebook- Palo Alto, California (unde am şi mers în 2010), dar am aplicat şi pentru doctorat la mai multe universităţi în SUA.

Începusem să-mi conturez ceea ce doresc: să continui cercetarea la nivel de vârf! La vremea respectivă, părea multora o alegere greşită, dar eu asta-mi doream! Voiam să am acces la cercetare adevărată, să-mi fac cunoscute ideile, să ajung să lucrez cu pasionaţi ca mine! Alegerea universităţii a fost legată de domeniul de cercetare şi dacă ar fi să mai aleg odată, tot University of California Irvine ar fi preferinţa mea. În vacanţele de la doctorat am mai mers la internshipuri la Facebook – Palo Alto în 2011 şi 2013. Activitatea mea la UC Irvine mă reprezintă: lucrez într-o echipă extraordinară, cu un profesor coordonator pasionat.

În cei patru ani de când sunt la UCI, am avut satisfacţia propriei contribuţii la securitatea datelor, domeniu sensibil în protecţia informaţiilor. Rezultatele obţinute în laborator împreună cu colegii s-au concretizat în articole pe care le-am prezentat la conferinţe internaţionale: The 20th ACM Conference on Computer and Communications Security, CCS '13, Berlin, Germany, November 2013 (articolul “Transparent Code Randomization for Just-in-Time Compilers”), International Symposium on Code Generation and Optimization, CGO '13, Shenzhen, China, February 2013 (articolul “Profile-guided Automated Software Diversity“), The 6th USENIX Workshop on Offensive Technologies, WOOT '12, Bellevue, WA, USA, August 2012 (“Microgadgets: Size Does Matter in Turing-complete Return-oriented Programming“), Symposium on Dynamic Languages, DLS '11, Portland, OR, USA, October 2011 (articolul “HappyJIT: A Tracing JIT Compiler for PHP“). La toate acestea am fost coautor, iar ele sunt publicate la adresa www.ics.uci.edu/~ahomescu/.

Rezultatele muncii din ultimii ani în laboratorul de la UCI a atras atenţia şi s-au găsit persoane care să investească în punerea în practică a ideilor noastre.

Şi uite-aşa fac ce-mi place, contribui la dezvoltarea securităţii datelor în contextul globalizării, văd lumea şi simt că trăiesc cu adevărat!

Pe lângă activitatea de cercetare, sunt permanent preocupat să cunosc oameni şi locuri, să ştiu detalii istorice sau date biografice ale personalităţilor acestei lumi, în general îmi place să fiu informat.

Alegerile în viaţă mi-au permis să văd multe locuri fascinante, printre care Marele Canion al fluviului Colorado, cunoscut sub denumirea Grand Canyon, cea mai mare minune naturală şi stabilită ca rezervaţie, dar şi multrâvnitul Hollywood, intrat în istorie prin intermediul industriei cinematografice. Hollywood-ul este un district situat în regiunea centrală a Los Angeles-ului, California, USA. Creată în 1923, dar supusă numeroaselor vandalizări de-a lungul anilor, vestita semnătură hollywoodiană a fost restaurată începând cu anul 2005, finalizându-se în anul 2009. Semnătura este amplasată pe muntele Lee din lanţul muntos Santa Monica. Cele 9 majuscule au

http://www.ics.uci.edu/~ahomescu/

4

înălţimea de 14m şi se întind pe o lungime de 110m. Sistemele de supraveghere şi securitate a zonei fereşte zona de acte de vandalism care să mai contribuie la deteriorarea minunatei semnături hollywoodiane. Marele Canion al fluviului Colorado l-am vizitat împreună cu prietenii din facultate. Minunile create de ape, formele bizare ale reliefului şi întinderea imensă a rezervaţiei te fac să uiţi de oboseală şi să te minunezi permanent de unicitatea peisajului. Voi reveni cu plăcere în Marele Canion, oricând voi avea un răgaz, deoarece totdeauna poţi vedea altceva din minunăţiile acestei rezervaţii naturale.

Ca o concluzie a experienţei mele de până acum, aş sugera tuturor să-şi urmeze

instinctul în alegerile pe care le iau în viaţă!

Dacă la baza alegerilor făcute este şi o documentare adevărată, dublată de

pasiunea unor lucruri bine făcute, succesul este garantat!

Andrei Homescu, absolvent C.N.T.V. Tg. Jiu, promoţia 2000-2004 Profilul Matematică-Informatică

II. Probleme de concurs

Cum poți ajunge autor de probleme

la Olimpiade și Concursuri Școlare?

prof. Eugen Nodea Membru al Comisiei Naționale de Informatică

Membru al Comisiei Științifice de pregătire a Lotului Național de Informatică – juniori Activitatea de compunere a problemelor se caracterizează prin spontaneitatea, imaginația și creativitatea

autorului în scopul stimulării gândirii, a inteligenţei elevilor implicați în concursurile școlare.

Criteriile urmărite de autor atunci când scrie o problemă:

- noutatea și originalitatea enunțului și a rezolvării

- departajarea concurenților prin punctaje parțiale pentru complexității diferite

- conceperea unui set de teste ce acoperă toate cazurile particulare ale problemei

- respectarea programei școlare

Vă supun atenției două probleme de la Olimpiada Județeană de Informatică, al căror autor sunt

(http://campion.edu.ro/arhiva/index.php?page=auth&action=view&type=author&id=5021).

Problema 1 - compresie (Olimpiada Județeană 2012, clasa a X-a)

Se consideră un text memorat într-o matrice M, definită prin coordonatele colţului stânga sus (x1,y1) şi

coordonatele colţului dreapta jos (x2,y2).

Prin aplicarea unui algoritm de compresie, matricei M i se asociază un şir de caractere, notat CM.

Şirul de caractere CM este construit prin aplicarea următoarelor reguli:

a) dacă matricea M are o singură linie şi o singură coloană atunci CM conţine numai

caracterul memorat în matrice;

b) dacă toate elementele matricei sunt identice atunci întreaga matrice M se

comprimă şi CM este şirul kc, unde k reprezintă numărul de caractere din

matrice, iar c caracterul memorat;

c) dacă matricea este formată din caractere diferite şi are cel puţin două linii şi

două coloane atunci:

- matricea este împărţită în 4 submatrice A, B, C, D după cum este ilustrat în figura alăturată, unde

http://campion.edu.ro/arhiva/index.php?page=auth&action=view&type=author&id=5021

5

coordonatele colţului stânga sus ale submatricei A sunt (x1,y1), iar coordonatele colţului dreapta

jos sunt ((x2+x1)/2,(y2+y1)/2);

- CM este şirul *CACBCCCD unde CA, CB, CC, CD sunt şirurile de caractere obţinute, în ordine, prin

compresia matricelor A, B, C, D utilizând acelaşi algoritm;

d) dacă matricea este formată din caractere diferite, are o singură linie şi mai multe coloane atunci CM

este şirul *CACB unde A, B, CA, CB au semnificaţia descrisă la punctul c);

e) dacă matricea este formată din caractere diferite, are mai multe linii şi o singură coloană atunci CM

este şirul *CACC unde A, C, CA, CC au semnificaţia descrisă la punctul c).

Cerinţă

Dat fiind şirul de caractere CM ce se obţine în urma aplicării algoritmului de compresie asupra unei matrice M

de dimensiune NxN să se determine:

a) numărul de împărţirii care au fost necesare pentru obţinerea textului compresat;

b) matricea iniţială din care provine textul compresat.

Date de intrare

Fişierul de intrare compresie.in conţine pe prima linie un şir de caractere ce reprezintă textul compresat.

Date de ieşire

Fişierul de intrare compresie.out conţine:

- pe prima linie un număr natural ce reprezintă numărul nr de împărţirii care au fost necesare pentru

obţinerea textului compresat;

- pe următoarele N linii se găsesc câte N caractere, ce reprezintă, în ordine, liniile matricei iniţiale.

Restricţii şi precizări

2 ≤ N ≤ 1000

0 ≤ nr ≤ 1000000

1 ≤ lungimea şirului compresat ≤ 1000000

Textul memorat iniţial în matricea M conţine numai caracterele din mulţimea literelor mici {a...z}.

Pentru rezolvarea corectă a cerinţei a) se acordă 20% din punctaj, iar pentru rezolvarea corectă a

ambelor cerinţe se acordă tot punctajul.

Exemple compresie.in compresie.out Explicaţii *4b*bbab4a*abbb 3

bbbb

bbab

aaab

aabb

Au fost efectuate 3 împărţiri:

bb

ba

aa

aa

ba

bb

bb

bbM * )1

))()()(*( )2 babbba

bb

))()()(*( )3 bbba

bb

ba

*4a*ab*aba

3

aaa

aab

aba

Au fost efectuate 3 împărţiri:

abab

a

aa

aaM

* )1

))(*( )2 bab

a

))(*( 3) baba

Timp maxim de executare/test: 0.5 secunde

Memorie totală disponibilă: 4MB, din care pentru stivă maxim 3MB

Descriere soluţie compresie

Cerinţa 1

Numărul de împărţirii care au fost necesare pentru obţinerea textului compresat: nr = numărul de steluţe ‘*’

Cerinţa 2

Dimensiunea N a matricei iniţiale

- Expandăm şirul comprimat construind un şir de caractere ce conţine doar caracterele literă mică din

şirul comprimat. Fiecare caracter din şirul comprimat care are înaintea lui un număr k se va repeta în

noul şir de k ori.

- Fie L lungimea acestui şir: N = [sqrt(L)]

6

Cerinţa 3

Rezolvarea cerinţelor problemei se face prin divide et impera.

Reţinem matricea prin colţul stânga sus (x1,y1), respectiv colţul dreapta jos (x2,y2).

Vom parcurge şirul compresat cu variabila k.

divide mx = (x2 + x1) / 2; my = (y2 + y1) / 2;

// reconstruiesc submatriciile A,B,C,D

divide (x1, y1, mx, my); //A

divide (x1, my + 1, mx, y2); //B

divide (mx + 1, y1, x2, my); //C

divide (mx + 1, my + 1, x2, y2); //D

stăpâneşte - Dacă x1=x2 && y1==y2 atunci M[x1][x2] = sir[k]

- Daca sir[k] € {‘0’..’9} atunci se va forma numărul x, iar submatricea definită de

coordonatele colţului stânga sus (x1,y1) şi de coordonatele coltului dreapta jos (x2,y2) va fi

completată cu caracterul din şir asociat numărului format.

Nu este necesară etapa combină.

Sursa C++ 1. # include <cstdio> 2. # include <cmath> 3. # include <cstring> 4. using namespace std; 5. 6. char s[1000001]; 7. char M[1001][1002]; 8. int L, N, nr, i, j, k; 9. void reconstruieste(short x1, short y1, short x2, short y2)

10. {

11. short mx, my, x, i, j;

12.

13. //conditia de oprire

14. if (x1<=x2 && y1<=y2 && k<L)

15. {

16. //stapaneste

17. if (x1==x2 && y1==y2) M[x1][y1] = s[k++];

18. else

19. if (s[k]>='0' && s[k] <='9')

20. {

21. x = 0;

22. while (s[k]>='0' && s[k]<='9')

23. {

24. x = x*10 + (s[k] - '0');

25. ++k;

26. }

27. //completez submatricea

28. for (i=x1; i<=x2; ++i)

29. for (j=y1; j<=y2; ++j)

30. M[i][j] = s[k];

31. ++k;

32. }

33. else //s[k] == '*'

34. {

35. //divide

36. mx = (x2 + x1) >> 1; my = (y2 + y1) >> 1;

37. ++k;

38. // reconstruiesc submatricile A, B, C, D

39. reconstruieste(x1, y1, mx, my); //A

40. reconstruieste(x1, my + 1, mx, y2); //B

41. reconstruieste(mx + 1, y1, x2, my); //C

42. reconstruieste(mx + 1, my + 1, x2, y2); //D

7

43. }

44. }

45. }

46. int main()

47. {

48. freopen("compresie.in", "r", stdin);

49. freopen("compresie.out","w", stdout);

50.

51. fgets(s, 1000001, stdin);

52. L = strlen(s);

53. //punctul 1 si 2

54. k = 0; nr = 0; j = 0;

55. for (i=0; i < L; ++i)

56. if (s[i] == '*') ++nr;

57. else if (s[i]>='0' && s[i]<='9') k = k*10 + (s[i] - '0');

58. else if (s[i]>='a' && s[i]<='z')

59. {

60. if (s[i-1]<'a' && k) j+=k, k=0;

61. else ++j;

62. }

63. N = (int) sqrt((double) j);

64. printf("%d %d\n", nr, N);

65.

66. //punctul 3

67. k=0;

68. reconstruieste(1,1,N,N);

69. for (i=1; i<=N; ++i)

70. {

71. for (j=1; j<=N; ++j)

72. printf("%c", M[i][j]);

73. printf("\n");

74. }

75. return 0;

76. }

Problema 2 - cool (Olimpiada județeană 2014, clasa a IX-a)

Se consideră un șir A cu N elemente naturale nenule, Numim secvență de lungime K a șirului A orice

succesiune de elemente consecutive din șir: Ai, Ai+1,…, Ai+K-1.

O secvență o numim secvență cool dacă elementele care o compun sunt distincte și pot fi rearanjate astfel

încât să alcătuiască o secvență continuă de numere consecutive.

De exemplu, dacă considerăm șirul A=(3,1,6,8,4,5,6,7,4,3,4) secvența (8,4,5,6,7) este o

secvență cool deoarece conține elemente distincte ce pot fi rearanjate astfel încât să alcătuiască șirul de

numere consecutive 4,5,6,7,8, pe când secvențele (4,3,4), (6,7,4,3) nu sunt considerate secvențe

cool.

Cerinţă

Fiind dat un şir de N numere naturale nenule să se determine:

a) Pentru o valoare dată K să se verifice dacă secvența A1, A2,…, AK este secvență cool. Dacă secvența

este cool se va afișa cea mai mare valoare ce aparține secvenței. Dacă secvența nu este cool se va

afișa numărul elementelor distincte din secvența A1, A2,…, AK, adică numărul elementelor care apar

o singură dată.

b) lungimea maximă a unei secvențe cool și numărul secvențelor cool de lungime maximă.

Date de intrare

Fişierul de intrare cool.in conţine pe prima linie un număr natural p. Pentru toate testele de intrare, numărul

p poate avea doar valoarea 1 sau valoarea 2.

Pe linia a doua linie se găsesc despărțite prin spațiu două numere naturale N K.

Pe următoarea linie se găsesc N numere întregi separate prin spațiu, ce reprezintă elementele şirului.

8

Date de ieşire

Dacă valoarea lui p este 1, se va rezolva numai punctul a) din cerință.

Fişierul de ieşire cool.out va conţine pe prima linie un număr natural, număr ce reprezintă conform cerinței

a) maximul secvenței A1, A2,…, AK dacă secvența este secvență cool, sau numărul elementelor distincte din

secvență, dacă aceasta nu este secvență cool.

Dacă valoarea lui p este 2, se va rezolva numai punctul b) din cerință.

Fişierul de ieşire cool.out va avea două linii. Prima linie conține un număr natural nenul ce reprezintă

lungimea maximă a unei secvențe cool, iar următoarea linie un număr natural nenul ce reprezintă numărul de

secvențe cool care au lungimea maximă.

Restricţii și precizări

1 N 5000

2 K 1000

1 A[i] 1000, 1 i N

Pentru 30% dintre teste N 1000

Pentru rezolvarea primei cerinţe se acordă 20% din punctaj, iar pentru cerința a doua se acordă 80% din

punctaj.

Exemple cool.in cool.out Explicaţie 1

7 4

6 4 5 7 8 3 5

7 Atenție! Pentru acest test se rezolvă doar cerința a). Secvența 6 4 5 7 este cool. Valoarea maximă din secvență este 7

cool.in cool.out Explicaţie 1

7 6

6 4 5 7 5 4 3

2 Atenție! Pentru acest test se rezolvă doar cerința a). Secvența 6 4 5 7 5 4 nu este secvență cool. Numărul valorilor distincte din secvență este 2. Valorile distincte sunt: 6,7

cool.in cool.out Explicaţie 2

11 4

7 4 5 6 8 4 5 7 4 3 2

5

2 Atenție! Pentru acest test se rezolvă doar cerința b). Cele două secvențe cool de lungime maximă 5 sunt: 7 4 5 6 8

6 8 4 5 7 Timp maxim de execuţie/test: 0.5 secunde.

Memorie totală disponibilă: 2 MB, din care 1 MB pentru stivă

Descriere soluție cool

Cerința a) ( 20 puncte)

Printr-o simplă verificare a frecvenței de apariție a primelor k numere se obține răspunsul așteptat.

Cerința b . ( 80 puncte)

O soluție brute-force obține 25p. O soluție bazata pe set(stl) obține 40-50p.

Rezolvarea cerinței b) pentru a obține cele 100p necesită câteva observații.

Fie secvența ce conține k numere consecutive distincte:

x+1, x+2, ... , x+k

Observăm că:

1) min = x+1, max = x + k => max - min == k-1

2) elementele sunt distincte

3) relația 1) este adevărată indiferent de ordinea elementelor

Așadar,

- pentru orice secvența care începe pe poziția i și se termina pe poziția j se va determina minimul și

maximul

- secvența este cool daca respectă relațiile 1) si 2)

Astfel, complexitatea rezolvării subpunctului b) poate fi redusă la O(N*k) amortizat.

9

Sursa C++ 1. # include <cstdio> 2. # include <cstring> 3. # define NMax 5003 4. # define Nmax 1003 5. using namespace std; 6. 7. int a[NMax], ap[Nmax]; 8. int n, Max, nr; 9. 10. void cool()

11. {

12. int i, j, k, min, max;

13. for (i=1; i < n; ++i)

14. {

15. min = a[i]; max = a[i];

16. ap[a[i]] = 1;

17. for (j=i+1; j<=n; ++j)

18. {

19. if (ap[a[j]]) break;

20. ap[a[j]] = 1;

21. if(a[j] < min) min = a[j];

22. if(a[j] > max) max = a[j];

23. k = j - i + 1;

24. if(max - min == k - 1)

25. {

26. if (k > Max) Max = k, nr = 1;

27. else if (k == Max) ++nr;

28. }

29. }

30. memset(ap, 0, sizeof(ap));

31. }

32. }

33. int main()

34. {

35. int i, k, p, Min = 1001, nr_dist = 0;

36. freopen ("cool.in", "r", stdin);

37. freopen ("cool.out","w", stdout);

38. scanf("%d", &p);

39. scanf("%d %d", &n, &k);

40. for (i=1; i<=n; ++i)

41. scanf("%d", &a[i]);

42. if (p == 1)

43. { //a

44. for (i=1; i<=k; ++i)

45. {

46. ap[a[i]]++;

47. if (a[i] < Min) Min = a[i];

48. if (a[i] > Max) Max = a[i];

49. }

50. for (i=Min; i<=Max; ++i)

51. if (ap[i] == 1) ++nr_dist;

52. if (nr_dist == k) printf("%d\n", Max);

53. else printf("%d\n", nr_dist);

54. }

55. else

56. { //b

57. cool();

58. printf("%d\n%d\n", Max, nr);

59. }

60. return 0;

61. }

10

III. Articole. Studii de caz

Elemente de combinatorică Prof. Gabriela Nodea

Cuprins:

Permutări. Aranjamente. Combinări

Implementări sugerate

Acest articol își propune să insiste mai mult pe algoritmi ce necesită cunoștințe de combinatorică. Evident că sunt necesare cunoștințe matematice de bază din teoria mulțimilor și a numerelor, iar cunoștințele și abilitățile algoritmice nu trebuie ignorate.

Permutări. Aranjamente. Combinări Fie și și o funcție , unde și sunt mulțimi finite, astfel încât

și , . Acestei funcții i se pune in corespondență o aranjare a mulțimii de obiecte în mulțimea de

căsuțe, astfel încât în căsuța să intre obiectele din mulțimea .

Propoziție 1: Numărul funcțiilor este egal cu , unde și . Propoziție 2: Numărul funcțiilor injective , notat cu

, este egal cu , unde și .

și reprezintă numărul de aranjări a obiecte în căsuțe ordonate. Fiecare căsuță poate conține oricâte obiecte din , dar schimbând ordinea obiectelor într-o căsuță rezultă aranjări diferite.

Dacă în definiţia aranjamentelor renunţăm la restricţia ca cele obiecte să fie distincte obţinem un aranjament cu repetiţie de obiecte luate câte . În acest caz nu este necesar să presupunem .

Exemplu: Fie . Aranjamentele de obiecte ale lui în căsuțe sunt: . Fie Aranjamentele cu repetiţie ce se pot forma cu aceste trei obiecte luate câte două

sunt: . Propoziție 3: Numărul funcțiilor bijective , notat cu , este egal cu

, unde . (factorial)

și reprezintă numărul de permutări a obiecte în căsuțe ordonate. Se numește permutare de grad funcția bijectivă și se scrie sub următoarea formă:

Se notează cu mulțimea permutărilor de gradul și evident . Exemplu: Fie mulțimea , . Permutările de obiecte ale lui sunt:

Observație: corespondența ”funcție – cuvinte” Vom lua în considerare cuvinte de lungime formate din simboluri ale alfabetului

. Oricărei funcţii îi putem pune în corespondenta cuvântul

11

în care ordinea literelor contează. Invers, cuvântului îi putem asocia funcția

Vom nota:

Propoziție 4: Numărul de cuvinte crescătoare de lungime folosind simboluri este cu

(combinări cu repetiție)

Propoziție 5: Numărul de cuvinte strict crescătoare de lungime folosind simboluri este cu

(combinări)

Exemplu: , ; Combinările de obiecte ale lui în căsuțe sunt: . Fie Combinările cu repetiţie ce se pot forma cu aceste trei obiecte luate câte două sunt:

Formule și noțiuni derivate 1. Permutări

Se numește permutarea identică a mulțimii , permutarea pentru care

Se numește punct fix al unei permutări un număr pentru care avem . Evident permutarea identică are puncte fixe

Numărul de permutări de elemente fără puncte fixe, notat cu este

Se poate demonstra ușor că:

Numărul de permutări a unei mulțimi de obiecte cu puncte fixe este

Se numește inversiune a unei permutări o pereche cu și .

O permutare a mulțimii poate avea cel mult

inversiuni

2. Aranjamente

,)1( 1 k

n

k

n AknA unde .2k

Numărul de aranjări ale unei mulțimi de obiecte în căsuțele astfef încât în sa avem obiecte, în obiecte, …, în sa avem

obiecte, unde , este

Altfel spus, cele elemente de tip se pot plasa în 1n

nC moduri pe cele poziții ale

permutării, cele elemente de tip se pot plasa în 2

1

n

nnC moduri pe pozițiile rămase, ...,

cele obiecte de tip se pot plasa în k

k

n

nnnC11 ... moduri.

Numărul de aranjamente cu repetiție este

mm

n nA ~

Avem un număr infinit de obiecte de tipurile .. În câte moduri putem așeza

12

obiectele pe n poziții? k

nA~

Avem un număr infinit de obiecte de tipurile . Numărul de moduri în care putem alege n obiecte dintre aceste este

n

kn

k

kn CC 1

1

1

3. Combinări

Dacă notăm cu m

nC~

numărul combinărilor cu repetiție, atunci există relația: m

nm

m

n CC 1

~

1

11

k

n

k

n

k

n CCC

kn

n

k

n CC

nn

nnn CCC 2...10

Binomul lui Newton: nn

n

nn

n

n

n

n

n

n

n

nbCabCbaCbaCaCba 11222110 ...

Termenii din dezvoltare au forma generala: kknk

nk baCT

1

Implementări sugerate Generarea permutărilor

backtracking recursiv # include <fstream>

using namespace std;

ifstream f(”permutari.in”);

ofstream g(”permutari.out”);

int N, st[101], k, ap[101];

void tipar(int k){

for(int i=1; i<=k; ++i)

g << st[i] << ’ ’;

g << ’\n’;

}

void back(int k)

{

int x, ev;

for(x=1; x<=N; ++x)

{

st[k] = x;

ev = (ap[st[k]] == 0);

if (ev){

ap[st[k]]=1;

if(k == N) tipar(k);

else back(k + 1); //urcam in stiva

ap[st[k]] = 0;

}

}

}

int main()

{

f >> N;

back(1);

return 0;

}

folosind next_permutation # include <fstream>

# include <algorithm>

# include <vector>

http://www.infoarena.ro/problema/permutari

13


ifstream f(”permutari.in”);

ofstream g(”permutari.out”);

int n;

vector<int> a;

void tipar()

{

for (int i=0; i<n; i++)

g << a[i] << ’ ’;

g << ’\n’;

return;

}

int main()

{

f >> n;

for (int i=1; i<=n; i++)

a.push_back(i);

do {

tipar();

}while (next_permutation(a.begin(), a.end()));

return 0;

}

Generarea triunghiului lui Pascal folosind o matrice void comb(int N)

{

int i, j;

C[0][0] = C[1][0] = C[1][1] = 1;

for (i=2; i<=N; ++i){

C[i][0] = C[i][i] = 1;

for (j=1; j<i; ++j)

C[i][j] = (C[i-1][j-1] + C[i-1][j]) % Mod;

}

}

folosind doi vectori void comb(int N)

{

int i, j;

L0[0] = L0[1] = 1; // linia 1

for (i=2; i<=N; ++i)

{

L0[i-1] = 1;

for (j=1; j<i; ++j)

L[j] = L0[j-1] + L0[j];

L[i] = 1;

//copiem linia curenta

for (j=0; j<=i; ++j)

L0[j] = L[j];

}

}

Bibliografie

[1.] Ioan Tomescu, Combinatorica si teoria grafurilor, Tipografia Universitatii Bucuresti, 1978; [2.] Ioan Tomescu, Probleme de combinatorica si teoria grafurilor, EDP, Bucuresti, 1981; [3.] www.infoarena.ro

http://www.infoarena.ro/

14

Rezolvarea numerică a ecuațiilor algebrice și transcendente

Prof. Oana Dabelea

Se numeşte ecuaţie algebrică cu o singură necunoscută o ecuaţie de forma: f(x)=0, unde f este un polinom nenul.

Forma generală a unei ecuaţii algebrice de gradul n este: 0},,...3,2,1{,,,0............

0

1

1

1

1

aaxaxaxa ni

n

n

n

nniCaCx

Într-o ecuaţie algebrică se realizează numai operaţii algebrice ca adunări, scăderi, înmulţirii, împărţiri, ridicări la putere sau extrageri de radicali.

Dacă o ecuaţie nu poate fi redusă la o ecuaţie algebrică folosind operaţiile de mai sus se numește ecuaţie transcendentă (ecuaţii exponenţiale, ecuaţii logaritmice, ecuaţii trigonometrice).

A rezolva o ecuaţie înseamnă a-i determina rădăcinile sau soluţiile ecuaţiei, adică acele numere αєC pentru care f(α)=0. Dacă pentru ecuaţiile algebrice se pot obţine forme generale ale soluţiilor şi se pot stabili propoziţii în legătură cu numărul lor, acest lucru nu mai e posibil pentru ecuaţiile transcendente.

Prezentăm mai jos o metodă de rezolvare a ecuaţiilor algebrice transcendente:

Metoda înjumătăţirii(bisecţiei) intervalului

Fie ecuația : f(x)=0 unde f:[a,b] → R , f continua (1) f(a)<0 şi f(b)>0 (2) Vom demonstra că ecuaţia are cel puţin o soluţie în [a,b]. Ştim că orice funcţie continuă pe un interval are proprietatea lui Darboux pe acel interval, adică:

2121 ],,[,)( xxbaxx şi oricare ar fi numărul c situat între )( 1xf şi )( 2xf (există cel puţin un

punct ),( 21 xxx astfel încât f(x)=c. f(b).

Notăm cu c mijlocul intervalului [a,b] adică c=(a+b)/2. Definim a1=a şi b1=c dacă f( c)>0 respectiv a1=c şi b1=b, dacă f( c)<0.

Dacă f(c)=0, atunci soluția ecuaţiei este c. În caz contrar f:[a1,b1]→R îndeplinește aceleaşi condiţii iniţiale(1), (2) dar lungimea domeniului de definiţie este redusă la jumătate.

Metoda poate fi continuată prin alegerea mijlocului [a1, b1] iar noul interval [a2, b2] va fi definit în același mod că cel precedent. Deci, metoda înjumătăţirii intervalului constă în încadrarea succesivă a soluţiei ecuaţiei în intervale din ce în ce mai fine sau altfel spus constă în definirea a trei şiruri { an},{bn},{cn} care sunt convergente la soluția ecuaţiei f(x)=0. Demonstrăm următoarele:

Proprietatea 1:

Şirul { an} este monoton crescător şi şirul { bn} este monoton descrescător. Demonstraţie : Calculăm

bn – an= bn-1- cn-1= bn-1-( an-1+ bn-1)/2=( bn-1- an-1)/2 dacă f(cn-1)<0; sau bn- an= cn-1- an-1=( an-1+ bn-1)/2 - an-1=( bn-1- an-1)/2 dacă f(cn-1)>0;

Deci pentru orice n≥1, bn- an=( bn-1- an-1)/2; Utilizând această egalitate pentru: n-1,n-2,…,1 rezultă bn- an=( (b-a)/2ⁿ) >0 pentru că b>a ;

Deci bn>an nєN ; Pe de altă parte cn este mijlocul intervalului [an, bn] şi avem relaţia : an< cn< bn nєN; Pentru a arăta că şirul { an} este monoton crescător avem an= an-1 dacă f(cn-1)>0;sau an= cn-1 dacă f(cn)<0; Pentru că an< cn< bn rezultă că an-1 ≤ an { an} monoton crescător analog şirul {bn} este monoton descrescător.

Proprietatea 2:

Şirurile { an} şi { bn} sunt mărginite. Demonstraţie: Pornim de la relaţia an < bn şi majorăm membrul drept (deoarece {bn} este şir monoton descrescător) an≤ bn≤ bn-1 ≤ bn-2 ≤…≤ b1≤ b0 nєN; Analog minorăm în membrul stâng pentru că { an } este şir monoton crescător obţinem

15

a0≤ a1≤…≤ an ≤ bn nєN;

Deci a0≤ a1≤…≤ an≤ bn≤ bn-1≤…≤ b1≤ b0 nєN;

Rezultă a0≤ an< b0 { an} mărginit;, a0< bn≤ b0 { bn} mărginit;

Proprietatea 3:

Şirurile { an} şi { bn} sunt convergente şi au aceeaşi limită. Demonstraţie : Conform criteriului lui Weierstrass orice şir monoton şi mărginit este convergent→{ an} şi { bn} sunt convergente .

Fie limn

an=A sau an→ A limn

bn= B sau bn→B A,B ba,

Atunci limn

(an –bn) =limn

n

ab

2

= 0 A-B=0 A=B

Folosind criteriul cleştelui şirul {cn} este convergent şi el:

În relatia an≤ cn ≤bn limn

an < limn

cn ≤ limn

bn limn

cn=α

Dacă an →α şi an→α şi în relatia an ≤ cn ≤ bn an→α nєN;

Proprietatea 4:

Numărul α (limita comună a şirurilor {an },{bn}{cn} este soluţie a ecuaţiei f(x)=0; Demonstraţie: datorită modului în care sunt definite şirurile rezultă f(an)<0 şi f(bn)>0. Cum f este continuă prin trecere la limită se obţine:

limn

f(an)≤0 f(α)≤0 şi limn

f(bn)≥0 f(α)≥0 de unde f(α)=0.

Pentru a exemplifica mai bine modul în care se poate determina soluţia prezentăm mai jos un program care l-am implementat în C++ şi arată foarte clar pe paşi cum se realizează această înjumătăţire pentru

un n dat. Implementarea s-a făcut pentru ecuaţia 01sin)1ln(2 xxx , în care I=[0,2] şi n=10. #include <iostream>

#include <cmath>

#include <iomanip>


double a,b,c;

int i,n;

double f(double x)

{return x*x*log(1+x)-sin(x)-1;}

int main()

{

cout<<"dati intervalul I=[a,b]"<<'\n';

cout<<"a=";cin>>a;

cout<<"b=";cin>>b;

cout<<"Numarul de iteratii:"<<'\n';

cin>>n;

for (i=1;i<=n;i++)

{ c=(a+b)/2;

if (f(c)<0) a=c;

else b=c;

cout<<"la iter."<<i<<"sol. se afla in

interv." << setprecision(6) << a << ","

<< setprecision(6) << b <<"\n";

}

return 0;

}

Deşi nu am determinat soluţia, putem spune că dacă o păstrăm numai cu primele două zecimale soluţia este 1.48; prin continuarea procedeului de înjumătăţire pentru un n mai mare, putem obţine oricâte zecimale exacte ale unei valori necunoscute.

Mai jos sunt prezentate pentru ecuaţia 01sin)1ln(2 xxx ], datele obţinute prin executarea

programului pentru n=10: la iter.1 sol. se afla in interv.1.0000,2.0000 la iter.2 sol. se afla in interv.1.0000,1.5000 la iter.3 sol. se afla in interv.1.2500,1.5000 la iter.4 sol. se afla in interv.1.3750,1.5000 la iter.5 sol. se afla in interv.1.4375,1.5000

la iter.6 sol. se afla in interv.1.4688,1.5000 la iter.7 sol. se afla in interv.1.4688,1.4844 la iter.8 sol. se afla in interv.1.4766,1.4844 la iter.9 sol. se afla in interv.1.4805,1.4844 la iter.10 sol. se afla in interv.1.4805,1.4824

Estimarea erorii: În cele mai multe situaţii nu vom putea determina valoarea exactă a lui α. Dar vom putea aproxima cu oricâte zecimale. Astfel vom calcula un număr de termeni ai şirului {cn} şi ne vom fixa un număr ε astfel încât | cn-α|<ε. Estimarea apriori a erorii constă în obţinerea unei inegalitati de forma | cn -α|<ε(n). Dacă inecuaţia cu necunoscuta n ε(n)<ε poate fi rezolvată, fără calculul termenilor şirului { cn } atunci vom şti, care element al şirului { cn } aproximează soluţia cu precizia ε. Pentru estimarea apriorii a erorii folosim relația: bn – an =(b-a)/2ⁿ şi faptul că α , cn є [an, bn].

16

Atunci | cn -α|<| an - bn |= bn – an =(b-a)/2ⁿ ; Deci dacă vrem să obţinem soluţia aproximativă a ecuaţiei f(x)=0 cu eroarea ε va trebui să calculăm termenii şirului {cn} până la prima valoare a lui n care îndeplineşte condiţia (b-a)/2ⁿ<ε adică n=[ln((b-a)/ε)/ln2]+1. Vom prezenta mai jos modul în care se poate determina cu trei zecimale exacte soluţia ecuaţiei:

01sin)1ln(2 xxx , pe intervalul I=[0,2] cu estimare apriorii a erorii. #include <iostream>

#include <cmath>

#include <iomanip>


double a,b,c,eps;

int i,n;

double f(double x)


int main()

{


cout<<"a=";cin>>a;

cout<<"b=";cin>>b;

if(f(a)<0&&f(b)>0)

{

cout<<"dati estimarea erorii:";

cin>>eps;

n=floor(log((b-a)/eps)/log(2))+1;

for (i=1;i<=n;i++){

c=(a+b)/2;

if (f(c)<0) a=c;

else b=c;}

cout<<"solutia cu trei zec. exacte si

cu estim. apriorii a erorii

"<<setprecision(6) << c<<"\n";

}

else cout<<"nu este respectata ipoteza

problemei";

return 0;

}

Soluţia cu trei zecimale exacte şi cu estimare apriorii a erorii pentru eps=0.001 este: 1.481

Estimarea aposteori a erorii Constă în obţinerea unei inegalităţi de forma | cn -α|<const·| cn - cn-1 |. Problema determinării soluţiei cu o eroare dată este acum principal modificată în sensul că o dată cu calculul termenilor cn , vom testa realizarea condiţiei: const·| cn - cn-1 |<ε Pentru estimarea aposteori a erorii pornim de la : | an - cn|=| bn - cn |=| an - bn |/2 De unde rezultă | an – bn |=2·| an – cn|; | an – bn |=2·| bn – cn | Deoarece an = cn-1 sau bn = cn-1 înseamnă că cel puţin una din cele două egalităţi anterioare au membrul drept egal cu 2·| cn-1 - cn |, deci | an - bn |=2·| cn-1 - cn | Pentru că α , cn є [an, bn] rezultă | cn -α|<| an - bn |=2·| cn - cn-1 | Deci, dacă vrem să obţinem soluţia aproximativă cu eroarea ε estimată aposteori pentru ecuatia f(x)=0 prin metoda înjumătăţirii intervalului trebuie să calculăm termenii şirului {cn } până când 2·| cn - cn-1 |<ε. În cadrul acestei metode este posibil să utilizăm ambele estimări. Vom prezenta mai jos modul în care se poate determina cu trei zecimale exacte soluţia ecuaţiei:

01sin)1ln(2 xxx cu estimare apostori a erorii. #include <iostream>

#include <cmath>

#include <iomanip>


double a,b,c,eps,c1;

int i,n;

double f(double x)


int main()

{


cout<<"a=";cin>>a;

cout<<"b=";cin>>b;

if(f(a)<0&&f(b)>0)

{

cout<<"dati estimarea erorii:";

cin>>eps;

c=a;

do{

c1=c; c=(a+b)/2;

if (f(c)<0)a=c;

else b=c;}

while(abs(c-c1)>=eps/2);

cout<<"solutia cu trei zecimale

exacte si cu estim. aposteori a erorii

" << setprecision(6)<<c<<"\n";

}

else cout<<"nu este respectata

ipoteza";

return 0;

}

Soluţia cu trei zecimale exacte şi cu estimare aposteorii a erorii pentru eps=0.001 este: 1.481.

Bibliografie:

[1.] Analiză numerică. Proiect manual XII Informatică, G.D. Matescu, Ileana Matescu, Editura Petrion [2.] Metode de calcul numeric, Dumitru Ebâncă, Editura Sitech Craiova, 1994. [3.] Mică enciclopedie matematică, Editura tehnică Bucuresti, 1975

17

Cum ne influenţează viaţa invazia de biţi? Prof. Carmen Negrea

Acest eseu, se doreşte o fi o Scrisoare deschisă… o provocare pe care o lansez … vouă, elevilor Colegiului Naţional Tudor Vladimirescu …. De ceva vreme, mă tot gândesc ce aş putea să scriu în acest prim număr al revistei noastre. Ce anume v-ar părea interesant? Răspunsul la această întrebare nu l-aţi putea da decât voi, elevii. Chiar nu cred că diferenţele/conflictele dintre generaţii sunt atât de mari, indiferent de vârsta, dar… există un dar, nu?!!

Aceste diferenţe, există, normal, nu sunt şi nu vreau să fiu ipocrită, le consider chiar benefice! Dacă n-ar exista atunci ar n-ar mai fi evoluţie, nu?

Adevăr şi provocare! Nu, nu are legătură cu niciun joc, ambele sunt legate strict de realitatea educaţională pe care

uneori o negăm din comoditate, alteori din ignoranţă sau din nefericire din indiferenţă. Dar totul are un început, nu? şi, orice început e greu şi generează erori, dar întotdeauna învăţăm din greşeli, sau, uneori pur şi simplu ni se formează „întregul” mai greu. Care-i problema? Important este să nu clachezi, e mai simplu să cedezi, nu? e mai simplu să afirmi şi să susţii, ca profesor, că numai cum faci tu e bine, că numai instrumentele , metodele de învăţare-predare-evaluare pe care în timp ca dascăl ţi le-ai format şi însuşit au devenit de neatins , adică... să recunoaştem că am devenit “prizonierii propriilor noastre limite”[1]?

Într-un eseu publicistic “PRO/ FESORII, tot mai departe de elevi“, Andrei Măjeri, elev al Colegiului Naţional Tudor Vladimirescu Tg-Jiu, menţiona în 2009, “trăim într-o societate ale cărei drepturi şi libertăţi variază pe o scară destul de amplă şi cu o sumedenie de carenţe şi a cărei ghilotină morală a ruginit de mult timp, dacă cumva a funcţionat vreodată. Sistemul educaţional, deşi intens mediatizat, a dezvoltat lacune( sau mai bine spus lagune) ce nu vor fi uşor "desecate" şi readuse în "circuitul agricol”... profesorii prea exigenţi, subiectele pentru bac mult prea grele pentru un elev de nivel mediu, cu însuşi sistemul bolnăvicios şi viciat. Am ajuns însă, la un nivel al decadenţei inacceptabil, la saturaţie...care ar fi cauzele? Octavian Paler spunea: “Avem o psihologie de popor superficial, de popor care poate frige mititei pe orice Golgotă.” ...ceea ce ne lipseşte nouă ca naţiune este voinţa, mentalitatea dinamică şi renunţarea la "victimismul" de care suferim ca popor prin excelentă.. ".[2]

Cam dramatic şi destul de trist , nu ? Din nefericire, nu pot nega în totalitate ce menţionează Andrei, acesta este adevărul, îl conştientizăm sau nu, el există.

Nimeni nu contestă că tehnologia oricât de avansată ar fi, va înlocui vreodată profesorul de la clasă, trebuie să recunoaştem că cele mai importante lecţii de viaţă sunt predate fără ajutorul unui calculator, pur şi simplu apariţia calculatoarelor şi a instrumentelor tehnologice care există pot fi utilizate în mod controlat în beneficiul elevilor iar curiozitatea explorării diferitelor platforme/reţele de comunicare şi colaborare de către elevi ar putea fi direcţionată în scop educativ cu efecte benefice şi vizibile în timp.

Ieri, tabla, creta, planşele, mulajele erau principalele instrumente prin care profesorii îşi construiau mesajul educaţional. Spre exemplu, la orele de chimie, de cele mai multe ori, diferenţa dintre o lecţie dezastruoasă şi una interesantă, motivantă, în care elevii învăţau din clasă, era dată de accesul în laborator şi de existenţa substanţelor necesare. Acum, această diferenţă o fac noile tehnologii, aproape la orice materie. Tot “ieri”, în laboratorul de informatică existau câteva calculatoare HC90 iar Bil Gates afirma că este imposibil ca unei persoane să-i trebuiască pentru nevoi personale un calculator cu o memorie mai mare de 64 KO.

Grigore Moisil spunea: "Calculatorul nu rezolvă probleme, cum se spune. Problemele le rezolvă omul, dar în rezolvarea lor omul se serveste nu numai de toc şi hârtie, ci şi de calculator", subliniind faptul că un calculator este un instrument de lucru, nu o "inteligentă" de sine stătătoare.

Provocarea pe care o lansez !

Încercaţi să răspundeţi, în scris, sau în gând dacă nu aveţi curajul public la următoarele întrebări ([email protected] ): Poate reuşi tehnologia să creeze un mediu educaţional modern? Cum?

mailto:[email protected]

18

Care sunt carenţele sistemului educational şi cum aţi vedea voi un sistem/mediu educațional astfel încât să ieşim cu toţii (şi noi ... şi voi!!) din apatia asta generalizată… din mediocritatea care din nefericire ne înconjoară şi în care ne complacem? (un articol foarte interesant, scris de un fost olimpic la informatică îl puteţi citi aici http://www.invatamantul.ro/ )

Pot reţelele de socializare să înlocuiască comunicarea şi socializarea? Mă puteţi convinge, prin argumente , exemple de bună practică, să accesez/utilizez frecvent pagina de facebook, în condiţiile în care zilnic toată lumea postează orice, oricât, fără discernământ …când văd că toată lumea dă “click” la orice material?! Sincer, de “like”, nici nu vreau să vorbesc, chiar vă rog să nu încercaţi să mă convingeţi … dacă vreau să felicit pe cineva, pot s-o fac personal, pot să dau un telefon….pot să comunic fără “click” iar numărul de “like-uri”, nu mă interesează….90% din ele le consider false, ipocrite!! Sunt şi excepţii, le-am enumerate chiar eu, mai sus (la utilizarea instrumentelor tehnologice)... Sunt subiectivă, normal! Dar, e dreptul meu! Nu pot înţelege, de ce 80% din cei care folosesc această platformă de socializare se autodiscreditează ? (prin postarea unor materiale, imagini compromiţătoare, penibile, triste, sigur, în noul DOOM va fi adăugat cuvântul „selfie’… patetic, nu?)

Bibliografia [1]_A.Adler,”Cunoaşterea omului”, Editura IRI,1996 [2] Andrei Măjeri, eseu publicistic “ PRO/ FESORII, tot mai departe de elevi “, 2009

Studiu de caz – problema rucsacului Prof. Carmen Negrea

http://www.infoarena.ro/problema/rucsac Se dă o mulțime formată din N obiecte, fiecare fiind caracterizat de o greutate și un profit. Să se găseasca o submulțime de obiecte astfel încât suma profiturilor lor să fie maximă, iar suma greutăților lor să nu depășească o valoare G.

Date de intrare

Pe prima linie a fişierul rucsac.in se vor gasi valorile N si G, cu semnificația din enunt. Pe urmatoarele N linii se vor găsi perechile de valori Wi si Pi, reprezentând greutatea, respectiv profitul obiectului i. Date de ieşire În fişierul de ieşire rucsac.out se va afisa o singura valoare Pmax, profitul maxim care poate fi obținut respectând condiția problemei.

Restricţii 1 ≤ N ≤ 5000, 1 ≤ G ≤ 10000

0 ≤ Wi, Pi ≤ 10000

Exemplu

rucsac.in rucsac.out

6 10

3 7

3 4

1 2

1 9

2 4

1 5

29

Rezolvare: Pentru a calcula dinamic (în timp/pas cu pas) valoarea câștigului maxim utilizând o anumită greutate, folosim o matrice cu n linii si gmax coloane (n- numarul de obiecte, gmax= greutatea maximă a rucsacului) Semnificații: i- numarul de linie= numărul obiectului analizat la un moment dat j- coloana= greutatea care se poate obține folosind obiectul cu numărul i castig[i][j] - valoarea câștigului dacă se folosește obiectul i pentru greutatea j Valoarea maximă a câștigului va fi ultimul element al matricei castig[n][gmax]

http://www.invatamantul.ro/

http://www.infoarena.ro/problema/rucsac

19

Pentru a arăta și obiectele care au fost utilizate se foloseste matricea selectat[][]- numărul ultimului obiect utilizat.

Sursa C++

# include <fstream>


ifstream f("rucsac1.in");

ofstream g("rucsac1.out");

int n, gmax, castig[1000][10000], gr[100000], c[200], selectat[1000][10000];

int main()

{ int i,j,k,p;

f>>n>>gmax;

for(i=1;i<=n;++i)

f>>gr[i]>>c[i]; //prelucrare

for(i=1;i<=n;++i)

{ for(j=1;j<=gmax;++j)

{ if(gr[i]<=j)

{if(c[i]+castig[i-1][j-gr[i]]>castig[i-1][j])

{

castig[i][j]=c[i]+castig[i-1][j-gr[i]];

selectat[i][j]=i;

}

else

{ castig[i][j]=castig[i-1][j];

selectat[i][j]=selectat[i-1][j];

}}

else

{castig[i][j]=castig[i-1][j];

selectat[i][j]=selectat[i-1][j];

}}

//afișări intermediare pentru a verifica cum se modifică

g<<"modificare matrice castig la pasul "<<i<<endl;

for(k=1;k<=n;++k)

{for(p=1;p<=gmax;++p)

g<<castig[k][p]<<" ";

g<<endl;}

g<<"modificare matrice selectat la pasul" <<i<<endl;

for(k=1;k<=n;++k)

{for(p=1;p<=gmax;++p)

g<<selectat[k][p]<<" "; g<<endl;}

}

i=n; j=gmax;

g<<"castig total="<<castig[i][j]<<endl;

// afisare obiecte selectate

while(selectat[i][j])

{ int x=selectat[i][j];

g<<selectat[i][j]<<" ";

while(x==selectat[i][j]){j=j-gr[x];--i;}

}}

Exemplu 1 modificare matrice castig la pasul 1 0 0 7 7 7 7 7 7 7 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 modificare matrice selectat la pasul1 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 modificare matrice castig la pasul 2 0 0 7 7 7 7 7 7 7 7 0 0 7 7 7 11 11 11 11 11 0 0 0 0 0 0 0 0 0 0 …… 0 0 0 0 0 0 0 0 0 0 modificare matrice selectat la pasul2 0 0 1 1 1 1 1 1 1 1 0 0 1 1 1 2 2 2 2 2 0 0 0 0 0 0 0 0 0 0 ……………

20

modificare matrice castig la pasul 3 0 0 7 7 7 7 7 7 7 7 0 0 7 7 7 11 11 11 11 11 2 2 7 9 9 11 13 13 13 13 0 0 0 0 0 0 0 0 0 0 ………….. modificare matrice selectat la pasul3 0 0 1 1 1 1 1 1 1 1 0 0 1 1 1 2 2 2 2 2 3 3 1 3 3 2 3 3 3 3 0 0 0 0 0 0 0 0 0 0 ………………….. modificare matrice castig la pasul 4 0 0 7 7 7 7 7 7 7 7 0 0 7 7 7 11 11 11 11 11 2 2 7 9 9 11 13 13 13 13 9 11 11 16 18 18 20 22 22 22 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 modificare matrice selectat la pasul4 0 0 1 1 1 1 1 1 1 1 0 0 1 1 1 2 2 2 2 2 3 3 1 3 3 2 3 3 3 3 4 4 4 4 4 4 4 4 4 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 modificare matrice castig la pasul 5 0 0 7 7 7 7 7 7 7 7

0 0 7 7 7 11 11 11 11 11 2 2 7 9 9 11 13 13 13 13 9 11 11 16 18 18 20 22 22 22 9 11 13 16 18 20 22 22 24 26 0 0 0 0 0 0 0 0 0 0 modificare matrice selectat la pasul5 0 0 1 1 1 1 1 1 1 1 0 0 1 1 1 2 2 2 2 2 3 3 1 3 3 2 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 5 4 4 5 5 4 5 5 0 0 0 0 0 0 0 0 0 0 modificare matrice castig la pasul 6 0 0 7 7 7 7 7 7 7 7 0 0 7 7 7 11 11 11 11 11 2 2 7 9 9 11 13 13 13 13 9 11 11 16 18 18 20 22 22 22 9 11 13 16 18 20 22 22 24 26 9 14 16 18 21 23 25 27 27 29 modificare matrice selectat la pasul6 0 0 1 1 1 1 1 1 1 1 0 0 1 1 1 2 2 2 2 2 3 3 1 3 3 2 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 5 4 4 5 5 4 5 5 4 6 6 6 6 6 6 6 6 6 castig total=29 obiecte selectate 6 5 4 2 1

Exemplu 2 Date de intrare: 5 10 3 4 3 10 5 greutati 2 3 8 12 7 cost modificare matrice castig la pasul 1 0 0 2 2 2 2 2 2 2 2 0 0 0 0 0 0 0 0 0 0 modificare matrice selectat la pasul 1 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 modificare matrice castig la pasul 2 0 0 2 2 2 2 2 2 2 2 0 0 2 3 3 3 5 5 5 5 0 0 0 0 0 0 0 0 0 0 modificare matrice selectat la pasul2 0 0 1 1 1 1 1 1 1 1 0 0 1 2 2 2 2 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 modificare matrice castig la pasul 3 0 0 2 2 2 2 2 2 2 2 0 0 2 3 3 3 5 5 5 5 0 0 8 8 8 10 11 11 11 13 0 0 0 0 0 0 0 0 0 0 modificare matrice selectat la pasul 3 0 0 1 1 1 1 1 1 1 1 0 0 1 2 2 2 2 2 2 2

0 0 3 3 3 3 3 3 3 3 0 0 0 0 0 0 0 0 0 0 modificare matrice castig la pasul 4 0 0 2 2 2 2 2 2 2 2 0 0 2 3 3 3 5 5 5 5 0 0 8 8 8 10 11 11 11 13 0 0 8 8 8 10 11 11 11 13 0 0 0 0 0 0 0 0 0 0 modificare matrice selectat la pasul 4 0 0 1 1 1 1 1 1 1 1 0 0 1 2 2 2 2 2 2 2 0 0 3 3 3 3 3 3 3 3 0 0 3 3 3 3 3 3 3 3 0 0 0 0 0 0 0 0 0 0 modificare matrice castig la pasul 5 0 0 2 2 2 2 2 2 2 2 0 0 2 3 3 3 5 5 5 5 0 0 8 8 8 10 11 11 11 13 0 0 8 8 8 10 11 11 11 13 0 0 8 8 8 10 11 15 15 15 modificare matrice selectat la pasul5 0 0 1 1 1 1 1 1 1 1 0 0 1 2 2 2 2 2 2 2 0 0 3 3 3 3 3 3 3 3 0 0 3 3 3 3 3 3 3 3 0 0 3 3 3 3 3 5 5 5 castig total=15 5 3

21

IV. Ocolul pãmântului în …

INFORMATICÃ - marca C.N.T.V. Deschidem seria articolelor care leagă foști elevi, cu activitate în afara țării sau având

realizări de excepție cu impact internațional, de generația actuală, aspirantă la poziții de top în mari companii de IT sau cercetare la nivel de vârf.

Vom continua să-i căutăm și să-i atragem în marea familie a C.N.T.V. – iștilor pe toți cei care-și lasă amprenta într-un domeniu atins de globalizare într-un ritm alert. Ei sunt mai mulți și ni se vor alătura în urmatoarele numere ale revistei!

De la C.N.T.V. la ... GOOGLE Mă numesc Bogdan Druțu, am terminat liceul

„Tudor Vladimirescu” în mai 2006, profilul Matematică - Informatică. Pentru că de mic am fost pasionat de programare și calculatoare am decis să urmez „Automatică și Calculatoare” din cadrul Universității Politehnica din București.

Când am început să învăț programare aveam doar 8 ani și am fost pasionat de cum poți desena obiecte pe calculator folosind „10: & 20: ... “ si „LINE & CIRCLE” din vechiul Basic rulat pe un HC făcut înainte ca eu să mă nasc. Pe la 11 ani am trecut la urmatorul nivel: „Turbo Pascal” a fost pentru mine ca și când aș fi redescoperit programare și tot universul s-a schimbat. Îmi aduc aminte că unul dintre primii algoritmi învățați a fost Backtracking prin clasa a 6-a. În ultimii ani de liceu am trecut la ceea ce urma sa devină „marea dragoste”: C/C++.

În timpul liceului am participat la Olimpiada Națională de Informatică de mai multe ori, iar în ultimul an am reușit să mă calific la proba de baraj pentru Olimpiada Internațională de Informatică. A fost poate una dintre cele mai mari performanțe ale mele din timpul liceului (împreună cu alte câteva mențiuni la faza națională și multe alte premii câștigate la concursurile inter-județene).

În ceea ce privește programarea și algoritmica, am participat și în timpul facultății la ACM, iar cea mai bună performanță acolo a fost un loc 10 la faza European Centrală. De asemenea, în tot timpul facultății am fost destul de pasionat de ceea ce învățam acolo și asta m-a făcut să învăț și să deprind multe cunoștințe.

Îmi aduc aminte cu multă plăcere de primul meu job ca intern la Adobe care a fost în momentul în care îmi scriam lucrarea de licență și am decis că ar fi interesant să fac asta la o firmă și de ce nu, dacă se putea, la una de renume. Interviul a fost unul dintre cele mai interesante din viața mea pentru că am fost acolo fără să știu nimic despre cum este procesul de recrutare, ba mai mult decât atât, fără să știu nimic despre ce urma sa fac la lucrarea de licență (era despre WEB, iar eu nu știam diferența dintre HTML si JS). Am trecut acel interviu poate cu mult noroc pentru că am reușit să demonstrez că am cunoștințele de bază despre calculatoare și cred că una dintre cele mai importante am reușit să rezolv o problemă de logică. După prima mea experiență de lucru a urmat un alt job tot la Adobe, de data aceasta ca full-time.

În vara anului 2011, într-un moment în care îmi doream să văd America (ca orice oltean) am căutat o soluție ca Adobe să mă trimită la o conferință, un meeting, orice, ca să pot să ajung acolo. Din păcate/fericire acest lucru nu a fost posibil și am auzit că ar fi unele firme care pot să plătească o excursie în America pentru un interviu. Am ajuns în San Francisco (Silicon Valley) și nu a fost nici un motiv să mă întorc, pentru că cei mai buni ingineri din lume sunt aici. Google, că despre aceasta firmă este vorba, mi-a oferit libertatea și toate condițiile pentru a putea face lucruri pe care nu am avut ocazia să le fac în altă parte.

În toată viața mea m-am ghidat după un simplu moto:

22

„Dacă înveți și ești serios în viață, atunci viața va fi serioasă cu tine !”

Pentru mine așa a fost și nu regret niciun moment când stăteam în timpul liceului în laboratorul de informatică (și îi mulțumesc domnului Nodea pentru asta) și nici atunci când în timpul facultății petreceam ore scriind cod sau citind cărți.

Un C.N.T.V. – ist la ... Hong Kong “Visele de licean pot deveni realitate !”

Sunt CNTV-ist!

Perioada 2002-2006 reprezintă pentru mine îmbinarea fascinantelor momente copilăreşti, înconjurat de colegi şi prieteni, cu magnificele ore, susţinute cu dăruire de profesori care au contribuit la alegerile mele ulterioare în viaţă. Visam atunci să lucrez la mari companii, să văd lumea şi să contribui şi eu la progresul omenirii.

Cu gândul la visele mele de împlinire, mă străduiam să învăţ cât mai mult, participam la concursuri şi olimpiade şi alte activităţi împreună cu colegii mei.

Amprenta lăsată de fiecare profesor cu care am studiat la Colegiul Naţional “Tudor Vladimirescu” din Tg.Jiu, profilul Matematică-Informatică, este cheia alegerii continuării studiilor în domeniul calculatoarelor la Universitatea Politehnica din Bucureşti.

Încă din studenţie m-am angajat ca programator pentru a încerca să-mi îndeplinesc visul. Am lucrat înainte, succesiv, la 3 firme de IT şi la fiecare mi-am îndeplinit câte o părticică din vis: mi-aduceam contribuţia la dezvoltare în domeniul IT, relativ la nivelul la care ajungeam în momentul respectiv.

Din iunie 2013 lucrez ca inginer de sistem pentru instituţii bancare la Luxoft. Luxoft este o firmă de top care oferă servicii IT de calitate clienţilor de pe întregul glob, în diverse domenii, în special financiar-bancare.

Este ceea ce visam când eram elev!

Activitatea pe care o desfăşor este complexă, dar satisfacţiile sunt pe măsură: firma susţine continua perfecţionare a personalului, oferind şanse reale de participare la sesiuni gratuite de training în diverse locuri pe glob. Eu am fost plecat în Hong Kong de două ori, câte 3 luni, respectiv 2 luni, într-un singur an.

Deşi Hong Kong-ul este considerat ca făcând parte din China, acesta este un teritoriu cu propriile legi, recunoscut de organizaţiile internaţionale sub denumirea "Hong Kong, China". Există consulate ale tuturor statelor cu care au fost încheiate parteneriate economice (peste 59 consulate generale şi 62 consulate).

Influenţa britanică din perioada de colonie engleză şi-a pus amprenta asupra educaţiei şi dezvoltării economice a insulei, iar poziţia geografică şi alipirea teritorială la China, de-a lungul istoriei sale, au influenţat cultura unei civilizaţii considerată una dintre punţile dintre Orientul îndepărtat şi Occident.

Localnicii din Hong Kong, frumoşi şi foarte inteligenţi, arată asiatic, dar majoritatea au nume europene şi mulţi dintre ei sunt creştini. Beneficiind de investiţii ale marilor companii mondiale, Hong Kong-ul a favorizat convieţuirea oamenilor de diferite religii, de pe toate continentele.

Trăind aici oameni de pe întregul glob, am găsit restaurante cu specific chinezesc, japonez, franţuzesc, grecesc ş.a. Provocarea a fost pentru mine mare pentru a gusta din fiecare fel de mâncare. Am reuşit chiar să învăţ să mănânc atât cu beţe chinezeşti, cât şi cu cele japoneze. Ca un premiu pe care mi l-am acordat pentru reuşită, am cumpărat câteva seturi de beţe pentru acasă.

23

În Hong Kong te simţi ca pe o punte între două lumi: zgârie-norii şi luxul, evidente în central oraşului, şi măreţia statuilor, templelor budhiste şi clădirile cu aspect oriental existente pe insulă sau în zonele apropiate.

Activitatea mea zilnică s-a desfăşurat în centrul oraşului, unde eram şi cazat. De aceea, în weekend-uri ieşeam în zone mai puţin influenţate de arhitectura occidentală: zone montane cu spaţii verzi, clădiri cu arhitectură asiatică şi temple.

Într-unul dintre weekend-uri mi-am planificat o excursie pe insula Lantau pentru a vedea vestita statuie “Big Buddha”. După un drum de aproape două ore (o oră cu metroul şi una cu autocarul), am ajuns într-o zonă magică, tronată de o statuie gigant: statuia, situată pe coama unui deal, tronează şi parcă vegheză asupra întregii regiuni. Magnifică prin construcţie şi plasament, statuia “Big Buddha” oferă turistului ca mine trăirea unui sentiment unic de mulţumire sufletească.

Satisfacţia personală este dublă: lucrez în domeniul pe care-l visam şi pot să văd

lumea, deci, visele de licean pot deveni realitate!

Liviu Homescu, absolvent al Colegiului Naţional “Tudor Vladimirescu” Tg-Jiu Profilul Matematică-Informatică, promoţia 2006

Un C.N.T.V. - ist la ... Londra Numele meu este Dragoș Mihai Popescu și studiez

Matematica și Computer Science în Marea Britanie, la King’s College London. Probabil că unele dintre posibilele întrebări la care mulți dintre voi se gândesc sunt: De ce în străinătate? De ce Marea Britanie? Răspunsul este foarte simplu: o experiență care te pregătește pentru viață și pentru o viitoare carieră.

Unele dintre primele lucruri esențiale pe care le-am învățat în primul an de facultate sunt resposabilitatea și puterea de adaptare la un oraș nou, unde ești al nimănui la început. Trebuie să recunosc ca prima lună și jumatate a fost destul de dificilă. Tot ceea ce îmi stătea în minte era să cunosc cât mai multă lume și să-mi fac prieteni noi. Dar facultatea în sine iți oferă o multitudine de oportunități de a cunoaște persoanele prin organizarea de evenimente interactive și, poate cel mai important, prin creearea societăților (ex. Business Club, Finance and Entrepreneurship, Computing etc.). Fiecare facultate are echipe din fiecare disciplină sportivă (fotbal, tenis, cricket, volei, tenis de masă, rugby etc.) și participă constant în competiții. Miercurea și sâmbăta sunt, de obicei, zilele în care toate facultățile dispută meciuri între ele.

Eu m-am înscris la trei dintre aceste societăți: Business Club, Finance and Computing, unde sunt resposabil de stabilirea relațiilor cu companii și organizarea evenimentelor la facultate. Insă pot spune ca Business Club-ul a fost cea mai bună alegere. Această societate a organizat anul acesta o excursie de oportunități la companiile tech din San Francisco si Silicon Valley, unde am avut șansa sș cunosc câteva persoane de la care am aflat cum se poate începe un business în IT si cum este, de fapt, să lucrezi într-un corporate (ex. Facebook, Microsoft, Google). Pot să spun că sistemul educațional este complet diferit față de cel din România. Facultatea iți arată cum să înveți, nu mai ești ajutat tot timpul de profesori, dar, în schimb, iți sunt date materiale pe care le poți folosi pentru a reuși să iți rezolvi seminarele sau tutorialele. Dacă într-adevăr nu te descuri în a găsi răspunsul la o întrebare, poți să întrebi tutorul personal, care te ajută nu numai cu lucruri legate de facultate, ci și în alte situații, cum ar fi să iți scrie recomandări pentru anumite job-uri.

Există un Career Centre al facultății, care iți oferă tot ceea ce iți trebuie pentru a-ți găsi un loc de muncă, atât în timpul facultății, cât și după terminarea acesteia. Fiecare angajator caută persoane cu o personalitate cât mai variată, cu note bune, CV și Cover Letter bine structurate. De asemenea, poți avea întâlniri one-on-one cu o persoană specializată în job-uri, care te va ajuta la creearea unui CV cât mai bine organizat, ceea ce a fost și cazul meu.

24

Am cunoscut și persoane din anul doi, care m-au sfătuit să aplic pentru cât mai multe stagii de practică în bănci de investiții, stagii ce se desfășurau primăvara. Fiecare stagiu avea o durată de aproximativ una-două săptămâni. Competiția era imensă, dar am reușit cu un CV bine pregătit și un interviu telefonic să fiu acceptat la două dintre aceste programe, în cadrului departamentului de Tehnologie la două corporații renumite. Problema a fost că ambele se desfășurau în același timp și am avut de făcut o alegere foarte grea. Acest pre-internship este o oportunitate unică de a face primul pas spre o carieră de succes. În cazul unei bune relații de comunicare și asimiliarea cât mai multor cunoștinte în domeniul respectiv al companiei, iți va fi oferit un assessment centre, unde va trebui să ai un interviu face-to-face bazat pe competențe personale și unul tehnic, câteva exerciții de grup în care va trebui să demonstrezi că esti capabil de iei decizii rapide și să dai dovadă că ești un bun membru într-o echipă). Dacă ești acceptat la acest stagiu, atunci pentru vara din anul 2 si 3 vei fi acceptat la un program de internship, care, în proportie de 80%, iți va asigura un loc stabil de muncă, asta dacă te-ai descurcat, bineînțeles.

Cred că acum este timpul totuși să vă povestesc și despre cum poți fi acceptat în Marea Britanie. Poți aplica la maximum cinci facultăți prin intermediul site-ului UCAS. Trebuie să ai un Personal Statement foarte bine structurat și organizat, în care trebuie să spui de ce vrei să studiezi cursul respectiv și ce te califică pentru a fi ales. Iți trebuie de asemenea și o scrisoarea de recomandare de la dirigintele tău sau de la un profesor, care să reflecte activitățile tale extra-școlare, cât și rezultatele din timpul anilor. În cazul în care ești acceptat, ți se vor pune câteva condiții pentru a intra la facultatea respectivă. Prima este, desigur, să ai un test de limba engleza certificat (ex: IELTS, Cambridge Advanced sau Proficiency, TOEFL). După aceea, în mod normal, ar trebui să iți ceară Diploma de Bacalaureat. Fiecare facultate are condiții diferite de admintere. De exemplu, pentru Medicina sau Arhitectură, vor trebui prezentate dosare cu anumite lucrări.

Cred că experiența pe care am avut-o în acest an de facultate a fost unică. Mi-am făcut mulți prieteni, am reușit să mă implic destul de mult și în cateva activități extra-școlare și, cel mai important, am învățat să fiu resposabil, organizat și să iau deciziile potrivite în diferite situații. Sper că în viitor să lucrez unul-doi ani la o companie, după care aș dori să imi deschid propriul business. Vă urez succes la toți și să vă gândiți bine la ceea ce veți face în viitor!

Dacă aveți întrebări, în iulie sunt acasă :D !

Dragoş Mihai Popescu, absolvent C.N.T.V. Profil Matematică – Informatică, promoția 2012

Un C.N.T.V. - ist la ... Comisia Europeanã

Mă numesc Emanuela Epure, am terminat liceul “Tudor Vladimirescu” în Iunie 2004, profilul Matematică-Informatică. Pentru că îmi plăcea foarte mult matematica și informatica am decis să urmez “Facultatea de Matematică-Informatică” din cadrul Universitații din București în perioada 2004-2008.

Dar după primul an de facultatea am decis că viața mea nu era suficient de complicată așa că m-am înscris la “Facultatea de Turism” din cadrul Universității Româno-Americane, urmând în paralel cursurile celor două facultăți.

Dar în 2006 am avut oportunitatea de a merge pentru 6 luni cu o bursă de merit la Universitatea de Studii din Trieste, Italia, “Departamentul de Matematica și Informatică”, unde am cunoscut studenți din diferite țări cu obiceiuri și tradiții diferite, cu un alt mod de a gândi, cu opinii diferite, de accea am decis, deși mai aveam facultățile din București de terminat, să ma înscriu la “Facultatea de Inginerie” din cadurul Universității din Trieste. Am mers în paralel pentru un an cu anul 4 din România de la “Facultatea de Matematică și Informatica” și cu cea din Trieste, dar a trebuie să renunț la “Facultatea de Turism” pentru că mi-ar fi fost prea greu să fac 3 facultăți în paralel. În 2008 după terminarea

25

Universității din București, m-am înscris la master la ASE București la “Facultatea de Cibernetica, Statistica și Informatica Economică”, specializarea “Baze de Date”, mergând în paralel cu masterul și facultatea din Trieste, terminându-le în 2010.

Între timp, pentru că singura mea sursa de venit era bursa de studii de la facultatea din Italia, am început să dau meditații de matematică la elevi de liceu din Italia, să lucrez într-un restaurant și în același timp în colaborare cu un profesor de la Universitate din Trieste cu care am scris articole în Statistică pe care le-am publicat împreuna la reviste din America, în general.

Și pentru că îmi place extaordinar de mult să călătoresc, în anii de universitate am reușit să văd aproape întreaga Europă și să economisesc și bani din care i-am cumparat mamei mele un apartament de care sunt foarte mândră.

Revenind la carieră, imediat după terminarea facultății și masterului în 2010 am început să lucrez la o companie internațională ESTECO ca și software architect, programând în JAVA, la un desktop software folosit în proporție mai mare de 50% în industria automobilistică, iar după mai mult de un an am lucrat și la varianta web al aceluiași software. Dar între timp, pentru că mie îmi place să-mi complic singură viața, am lucrat de acasă la o mobile application pentru o companie din Italia.

Din ianuarie 2013 lucrez ca și software developer pentru Comisia Europeana, Joint Research Center (JRC) în Ispra, Italia, la 2 proiecte (INSPIRE și Air Quality System) care au ca rezultate 2 website-uri care sunt folosite de toate statele membre ale Uniunii Europene. Acestea mi-au dat oportunitatea de a cunoaște, colabora și lucra cu persoane din toate statele membre. Cum am ajuns să lucrez pentru Comisia Europeană? Nu a fost deloc complicat. Am dat câteva interviuri cu cei de la Comisie și am fost acceptată. Am renuntat la contractul permanent pe care îl aveam cu job-ul precedent doar pentru că știam că în JRC este un mediu multicultural, foarte competitiv și stimulativ.

Întotdeauna am fost ambițioasă și am știut ce îmi doresc și cred că orice tânar

ambițios, prin muncă și multă pasiune pentru ceea ce face, perseverență, dar și puțin

noroc poate ajunge acolo unde nu și-a imaginat vreodată.

Munții Alpi Ras Mohamed National Park Marino

Italia

Egipt

Emanuela Epure , absolvent C.N.T.V.

Profil Matematică - Informatică

26

V. Programatorul cel viteaz … 100 dintr-o loviturã !

Câţiva dintre elevii noştri, programatori pasionaţi, vă supun atenţiei câteva probleme date la concursuri şi olimpiade şcolare, la care ei au obținut punctaj maxim în concurs, însoţite de scurte comentarii, sperăm lămuritoare.

Continuăm să-i așteptăm cu soluțiile la care au obținut sau vor obține punctajul maxim de 100 puncte la competiții naționale recunoscute! Implementare placută!

Concursul ONI 2014 Elev POPESCU GEORGE, clasa a X-a A

Medalie de ARGINT, calificare BARAJ LOT

spion1 Timp maxim de execuţie / test: 0.1s

Memorie totala disponibilă / stivă: 16MB/8MB

Spionul 008 vrea să găsească o locaţie secretă în junglă, având asupra lui un

dispozitiv de localizare. Iniţial spionul se află la intrarea în junglă pe nivelul 1 şi

cu fiecare pas, el avansează de la nivelul i la nivelul i+1, ajungând la locaţia

secretă, aflată pe ultimul nivel, în poziţia u faţă de marginea stângă a nivelului

curent. Pentru a ajunge în locaţia secretă, el poate să se deplaseze cu o poziţie spre

Sud-Est (codificat cu caracterul E) sau spre Sud-Vest (codificat cu caracterul V),

trecând de pe nivelul i pe nivelul i+1 cu viteză constantă. Numărul de poziţii de pe

un nivel creşte cu unu faţă de nivelul anterior, conform imaginii alăturate. Numim

traseu o succesiune formată din caractereleE sau V, corespunzătoare deplasării

spionului de pe nivelul 1 la locaţia secretă. Pentru exemplul din figura alăturată

succesiunea de caractere VEEVE reprezintă un traseu ce corespunde locaţiei

secrete din poziţia 4 a nivelului 6.

Cerinţă

Cunoscând succesiunea de caractere corespunzătoare unui traseu, determinaţi:

a) poziţia locaţiei secrete de pe ultimul nivel;

b) numărul de trasee distincte pe care le poate urma spionul plecând din poziţia iniţială pentru a ajunge în

locaţia secretă corespunzătoare traseului dat. Două trasee se consideră distincte dacă diferă prin cel puţin o

poziţie.

Date de intrare

Fişierul de intrare spion1.in conţine pe prima linie un număr natural p din {1,2}, iar pe a doua linie o

succesiune de caractere corespunzătoare unui traseu.

Date de ieşire

Dacă valoarea lui p este 1, atunci se va rezolva numai punctul a) din cerinţă. În acest caz, fişierul de ieşire

spion1.out va conţine pe prima linie un număr natural ce reprezintă poziţia de pe nivelul final a locaţiei

secrete.

Dacă valoarea lui p este 2, atunci se va rezolva numai punctul b) din cerinţă. În acest caz, fişierul de ieşire

spion1.out va conţine pe prima linie un număr natural ce reprezintă numărul de trasee distincte modulo

100003.

Restricţii

• 2 ≤ lungimea şirului paşilor ≤ 100 000

• Pentru alte 10% din teste valoarea lui p=2 şi 3000 ≤ lungimea secvenţei de caractere ≤ 5000.

Exemplu

spion1.in spion1.out Explicaţii

1

VEEVE 4 Locaţia secretă este în poziţia 4 de pe nivelul 6.

27

2

VEV 3 Există trei trasee: VVE, VEV, EVV.

2

EVEVVEVEEE 210

Descriere soluție

Pentru punctul a) este suficient să contorizăm numarul de caractere "E" .

Notăm acest număr cu y. Noi vom afișa y+1 deoarece pornim de pe poziția 1.

Pentru punctul b) trebuie sa observam ca numarul de drumuri este exact C(n,y); pentru a obtine cele 100 de

puncte puteam să calculăm acest numar:

- descompuneam fiecare numar de la 1 la n în factori primi și retineam un vector cu puterile fiecărui

factor prim.

- analog pentru toate numerele de la 1 la y și de la 1 la n-y, doar ca puterile acestora vor fi reținute în alt

vector.

Vom calcula C(n,y) dupa formula n!/y!*(n-y)! dupa ce avem fiecare factor prim și puterea la care se află

acesta, putem sa calculam produsul ridicand la putere logaritmic fiecare factor prim.

De asemenea, pentru o descompunere mai rapida in factori primi putem precalcula factorii primi folosind

Ciurul lui Erathostenes.

Sursa C++ # include<fstream>

# include<cstring>

# define NMAX 100005

# define MOD 100003


int nrp[10010];

int p;

char s[100009];

int factn[NMAX+9],factk[NMAX+9];

int y,i,n;

int k,viz[NMAX+10];

//Cirul lui Erathostenes

void ciur()

{

int i,j;

for (i=2;i<=NMAX;++i){

if (viz[i]==0){

nrp[++k]=i;

for (j=i+i;j<=NMAX;j+=i) viz[j]=1;

}

}

}

//ridicare la putere in timp logaritmic

int lgput(int a,int b)

{

long long s;

if (b==1) return a;

if (b==2) return a*a;

if (b%2==0) s=((lgput(a,b/2)%MOD)*(lgput(a,b/2)%MOD))%MOD;

else s=a*(lgput(a,b-1)%MOD)%MOD;

return s;

}

int main()

{

ifstream f("spion.in");

ofstream g("spion.out");

f>>p;f.get();

ciur();

f.getline(s,100005);

n=strlen(s); y=0;

for (i=0;i<n;++i){

28

if (s[i]=='E') ++y;

}

//tratam puncul a)

if (p==1) {g<<y+1<<'\n';return 0;}

else

{

//tratam punctul b

//descompunem numerele de la 1 la n in factori primi

for (i=2;i<=n;++i){

int x=i;

p=1;

while (x!=1 && viz[x]==1)

{

while (x%nrp[p]==0) x=x/nrp[p],++factn[nrp[p]];

++p;

}

if (viz[x]==0) ++factn[x];

}

//descompunem numerele de la 1 la y in factori primi

for (i=2;i<=y;++i){

int x=i;

p=1;


{

while (x%nrp[p]==0) x=x/nrp[p],++factk[nrp[p]];

++p;

}

if (viz[x]==0) ++factk[x];

}

int r=n-y;

//descompunem numerele de la 1 la n-y in factori primi

for (i=2;i<=r;++i){

int x=i;

p=1;


{

while (x%nrp[p]==0) x=x/nrp[p],++factk[nrp[p]];

++p;

}

if (viz[x]==0) ++factk[x];

}

//facem diferenta de factori

for (i=2;i<=n;++i){

factn[i]-=factk[i];

}

long long sum=1;

//ridicam la putere in timp logaritmic fiecare factor

for (i=2;i<=n;++i){

if (factn[i]!=0) sum=(sum*lgput(i,factn[i]))%MOD;

}

g<<sum<<'\n';

}

}

zimeria Timp maxim de execuţie / test: 0.6s


Olimpia D’Info a găsit o placă gravată ce conţine mai multe cuvinte scrise cu semne grafice necunoscute,

fiecare cuvânt fiind format din exact 5 semne grafice. Studiind cu atenţie cuvintele, a dedus că în scrierea

acestora sunt utilizate 12 semne grafice distincte şi a asociat câte o literă mică din alfabetul englez fiecărui

semn. După asociere, a stabilit pentru fiecare semn o complexitate, scriind literele în ordinea crescătoare a

complexităţilor pe care le-a stabilit anterior. Olimpia consideră că această ”complexitate” este cel mai potrivit

criteriu de ordonare lexicografică.

29

Cerinţă

Cunoscând ordinea semnelor şi cuvintele de pe placă determinaţi:

a) Numărul de cuvinte distincte existente pe placă

b) Şirul de cuvinte ordonat lexicografic, conform criteriului formulat de Olimpia

Date de intrare

Fişierul de intrare zimeria.in conţine pe prima linie un numărul natural p din {1,2}, reprezentând varianta

cerinţei de rezolvare. Pe a doua linie se află un număr natural n reprezentând numărul de cuvintede pe placă.

Pe a treia linie sunt scrise 12 caractere, litere mici ale alfabetului englez, care reprezintă semnele codificate, în

ordinea lexicografică a semnelor. Pe fiecare dintre următoarele n linii se află câte un cuvânt.

Date de ieşire

Dacă valoarea lui p este 1, atunci se va rezolva numai punctul a) din cerinţă. În acest caz, fişierul de ieşire

zimeria.out va conţine pe prima linie numărul de cuvinte distincte de pe placă.

Dacă valoarea lui p este 2, atunci se va rezolva numai punctul b) din cerinţă. În acest caz, fişierul de ieşire

zimeria.out va conţine n linii, pe fiecare linie câte un cuvânt în ordine lexicografică, conform complexităţii

stabilite de către Olimpia.

Restricţii

n < 400000

30% din teste vor avea pe prima linie valoarea 1, iar restul de 70% din teste vor avea pe prima linie

valoarea 2.

Exemple:

zimeria.in zimeria.out Explicaţii

1

5

qwertyuiopas

reeet

wyuty

reeet

oiopp

oiopp

3 Placa conţine 3 cuvinte distincte.

Descriere soluție

Avem un alfabet format din exact 12 caractere si cate n cuvinte, fiecare avand 5 caractere. Observam foarte

usor ca fiecare caracter din acel alfabet poate fi inlocuit cu o cifra a uneia din bazele mai mari ca 11. Am ales

sa consideram fiecare litera din alfabetul nostru ca fiind reprezentantul unei cifre din baza 13.

Pentru exemplul 2: 6

qwertyuiopas

sapoi

sapou

wyuty

reeet

oiopp

oiopp

Vom inlocui fiecare alfabetul nostru qwertyuiopas, astfel 0123456789AB. Deci cuvantul "sapoi" se

va transforma in "BA987".

Aceste numere le vom transforma in baza 10 si apoi le vom sorta folosind un algoritm de sortare, urmand sa

retrecem vectorul cu numere sortate innapoi in baza 13, iar apoi in literele alfabetului nostru. Acestea au fost

pentru cazul al doilea.

Pentru primul caz se fac aceleasi conversii de baze, doar ca nu se sorteaza, numerele se pun intr-un vector de

aparitii iar apoi se parcurge vectorul pentru a verifica exact cate numere sunt. (Memoria ne permite acest lucru

deoarece cuvintele au maxim 5 caractere.)

Sursa C++ # include <fstream>



char alf[50],sir[50],s[50],ap[50];

30

bool viz[400005];

int v[400005],n,i,j,p;

int put[]={1,13,169,2197,28561};

//transformam numarul k din baza 13 in baza 10

void transf3(int k)

{

for (int t=0;t<5;++t){

if (ap[t]>='0' && ap[t]<='9'){

v[k]+=((ap[t]-'0')*put[4-t]);

}

else {

int x=ap[t]-'a'+10;v[k]+=(x*put[4-t]);

}

}

}

//transformam numarul k din baza 10 in baza 13

void transf10(int k)

{

int i=4;

while (v[k]>0){

int r=v[k]%13;

if (r<=9) ap[i]=(char)('0'+r);

else {

if (r==10) ap[i]='a';else ap[i]='b';

}

--i;

v[k]=v[k]/13;

}

if (i>=0) while (i>=0) ap[i]='0',--i;

}

int main()

{

fstream f("zimeria.in",ios::in);fstream g("zimeria.out",ios::out);

f>>p>>n;f.get();f.getline(sir,15);

//initializam alfabetul

alf[sir[0]-'a']='0'; alf[sir[1]-'a']='1'; alf[sir[2]-'a']='2';



alf[sir[9]-'a']='9'; alf[sir[10]-'a']='a'; alf[sir[11]-'a']='b';

for (i=1;i<=n;++i){

f.getline(s,10);

for (int j=0;j<5;++j){

ap[j]=alf[s[j]-'a'];

}

transf3(i); //marcam numarul v[i] in vectorul de aparitii

if (viz[v[i]]==0) ++viz[v[i]];

}

if (p==1){

//tratam cazul intai al problemei

int sum=0;

for (i=0;i<=400000;++i) sum+=viz[i];

g<<sum<<'\n';

return 0;

}

else{

//tratam cel de-al doilea caz

sort(v+1,v+n+1);//sortam

for (i=1;i<=n;++i)

{

//facem conversia fiecarui nr din baza 10 la loc in cuvant pentru a afisare

transf10(i);

for (int j=0;j<5;++j)

if (ap[j]>='0' && ap[j]<='9') g<<sir[(ap[j]-'0')];

31

else {

int x=ap[j]-'a'+10; g<<sir[x];

}

g<<'\n';

}

return 0;

}

Concurs ONI 2013

Elev Mărgeloiu Andrei, Clasa a X- a A MENȚIUNE M.E.C. / Medalie AUR

aranjare Timp maxim de execuţie / test: 0.3s


Toată lumea ştie că Mirel are 2*N sticluţe cu parfum aşezate pe un raft cu 2*N poziţii, numerotate de

la 1 la 2*N. El are N sticluţe cu parfum cumpărate din ţară şi alte N sticluţe cu parfum cumpărate din Franţa.

Sticluţele cumpărate din ţară sunt etichetate cu r1, r2, …, rN, iar sticluţele cumpărate din Franţa sunt etichetate

cu f1, f2, …, fN. Fiecare sticluţă are asociată valoarea cu care a fost cumpărată.

Iniţial, Mirel are aşezate pe primele N poziţii sticluţele cumpărate din ţară sortate crescător după valoare, iar

pe următoarele N poziţii sticluţele cumpărate din Franţa sortate tot crescător după valoare. Astfel,

cele 2*N sticluţe cu parfum sunt aşezate în felul următor: r1, r2, …, rN, f1, f2, …, fN. Mai exact, sticluţa ri se află

pe poziţia i, iar sticluţa fi se află pe poziţia N+i, pentru i din intervalul [1, N].

Prietenul său cel mai bun, Marian, s-a gândit să-i facă o surpriză şi să-i schimbe aranjarea sticluţelor cu

parfum în următoarea ordine: r1, f1, r2, f2, …, rN, fN. Cum Marian are două mâini, el poate face numai

următorul tip de operaţie: ia două sticluţe cu parfum de pe raft (de pe două poziţii diferite) şi le interschimbă.

Cerinţă

Dându-se numărul N şi 2*N valori reprezentând valoarea fiecărei sticluţe cu parfum, ajutaţi-l pe Marian să

facă operaţiile necesare pentru a schimba ordinea sticluţelor cu parfum în ordinea precizată în enunţ.

Date de intrare

Fişierul de intrare aranjare2.in conţine pe prima linie numărul N, iar pe următoarea linie 2*N numere naturale,

separate prin câte un spaţiu. Primele N numere reprezintă valorile sticluţelor cumpărate din ţară, iar

următoarele N numere reprezintă valorile sticluţelor cumpărate din Franţa. Atât primele N, cât şi

ultimele N numere sunt sortate crescător în funcţie de valoare.

Date de ieşire

Fişierul de ieşire aranjare2.out va conţine mai multe linii. Pe fiecare linie se vor afla două numere

diferite x şi y din intervalul [1, 2*N], semnificând faptul că Marian trebuie să interschimbe sticluţa de pe

poziţia x cu sticluţa de pe poziţia y.

Restricţii

2 ≤ N ≤ 31 000

Dacă există mai multe soluţii, se poate afişa oricare dintre ele. Soluţia nu trebuie să facă neapărat

numărul minim de operaţii.

Exemple

aranjare.in aranjare.out Explicaţii

3

1 3 5 2 3

5

2 4

3 5

3 4

În explicaţia de mai jos, fiecare sticluţă are numele etichetei urmat de valoarea ei

în paranteză.

Şirul iniţial este: r1(1) r2(3) r3(5) f1(2) f2(3) f3(5)

După prima mutare devine: r1(1) f1(2) r3(5) r2(3) f2(3) f3(5)

După a doua mutare devine: r1(1) f1(2) f2(3) r2(3) r3(5) f3(5)

După ultima mutare devine: r1(1) f1(2) r2(3) f2(3) r3(5) f3(5)

Descrierea soluţiei

Se observă că valorile sticluţelor din fişierul de intrare nu influenţează cu nimic rezolvarea problemei, deci

32

putem citi doar n, numărul de sticluțe.

Configuraţie iniţială: r1 r2 r3 … rN f1 f2 f3 … fN. Configuraţie finală: r1 f2 r2 f2 r3 f3 … rN fN

Ţinem minte pentru fiecare sticluţă poziţia pe care se află:

- pentru i de la 1 la 2*N

◦ dacă pe poziţia i nu avem sticluţa care trebuie:

- interschimbăm i şi pozitia pe care se află sticluţa ce trebuie aşezată pe poziţia i

Complexitate: O(N)

Sursa C++ # include <fstream>


ifstream f("aranjare.in");

ofstream g("aranjare.out");

int n, var[200005], poz[200005], i;

int main()

{

f>>n;

for(i=1; i<=2*n; ++i)

poz[i]=i, var[i]=i;

for(i=1; i<n; ++i){

if (var[2*i]!=n+i){

var[poz[n+i]]=var[2*i];

poz[var[2*i]]=poz[n+i];

g<<2*i<<" "<<poz[n+i]<<"\n";

}

if (var[2*i+1]!=i+1){

var[poz[i+1]]=var[2*i+1];

poz[var[2*i+1]]=poz[i+1];

g<<2*i+1<<" "<<poz[i+1]<<"\n";

}

}

return 0;

}

gradina Timp maxim de execuţie / test: 0.1s

Memorie totala disponibilă / stivă: 2MB / 1MB

Păcală a reuşit să ducă la bun sfârşit înţelegerea cu boierul căruia-i fusese slugă şi, conform învoielii, boierul

trebuie să-l răsplătească dându-i o parte din livada sa cu pomi fructiferi. Boierul este un om foarte ordonat, aşa

că livada sa este un pătrat cu latura de N metri unde, pe vremuri, fuseseră plantate N rânduri cu câte N pomi

fiecare. Orice pom fructifer putea fi identificat cunoscând numărul rândului pe care se află şi poziţia sa în

cadrul rândului respectiv. Cu timpul, unii pomi s-au uscat şi acum mai sunt doar P pomi. Păcală trebuie să-şi

delimiteze în livadă o grădină pătrată cu latura de K metri.

Cerinţă

Cunoscând dimensiunile livezii şi grădinii, numărul pomilor din livadă şi poziţia fiecăruia, determinaţi

numărul maxim de pomi dintr-o grădină pătrată de latură K şi numărul modurilor în care poate fi amplasată

grădina cu numărul maxim de pomi.

Date de intrare

Fişierul gradina1.in conţine pe prima linie numerele naturale N P K, separate prin câte un spaţiu, cu

semnificaţia din enunţ. Pe următoarele P linii se află câte 2 numere naturale Lin şi Col, separate printr-un

spaţiu, reprezentând numărul rândului, respectiv poziţia în rând a fiecărui pom din livadă.

Date de ieşire

Fişierul gradina1.out va conţine pe prima linie numărul maxim de pomi fructiferi dintr-o grădină pătrată cu

latura de K metri. Pe a doua linie va fi scris numărul de posibilităţi de a amplasa grădina astfel încât să conţină

numărul maxim de pomi determinat.

Restricţii

2 ≤ N ≤ 1000

1 ≤ P ≤ N2

1 ≤ K ≤ N

33

Exemple

gradina1.in gradina1.out Explicaţii

12 10 5

4 3

5 5

6 8

7 3

7 7

8 8

9 3

9 6

10 10

11 5

5

5 Grădina lui Păcală poate avea maximum 5 pomi

fructiferi.

Ea poate fi amplasată în 5 moduri, având colţul stânga-

sus de coordonate:

(5, 3), (5, 4), (5, 5), (6, 6), (7, 3)

.

Sursa C++ # include <cstdio>


int i,j,n,p,k,maxx,nr,x,y,q,var;

int a[1005][1005];

int main ()

{

freopen ("gradina.in", "r", stdin);

freopen ("gradina.out", "w", stdout);

scanf ("%d%d%d", &n, &p, &k);

for (i=1; i<=p; ++i){

scanf ("%d%d", &x, &y);

a[x][y]=1;

}

for (i=1; i<=n; ++i)

for (j=1; j<=n; ++j)

a[i][j]=a[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];

for (i=k; i<=n; ++i)

for (j=k; j<=n; ++j){

var=a[i][j]-a[i-k][j]-a[i][j-k]+a[i-k][j-k];

if (var>maxx) maxx=var, nr=1;

else if (var==maxx) ++nr;

}

printf ("%d\n%d\n", maxx, nr);

return 0;

}

Concursul RoTopCoder / 26-28 aprilie 2013

Elev Stochiţoiu Radu Dumitru, Clasa a XII- a B Premiul I

lambda Timp maxim de execuţie / test: 0.2s


Definim o λ-listă ca fiind o mulțime ordonată, finită, de elemente întregi. λ-listele se notează astfel:

L = [x1, x2, …, xn].

Pe o λ-listă se definesc următoarele operații:

[1.] Adunarea cu un scalar: dacă a ℤ și L = [x1, x2, …, xn], atunci: L + a = [x1 + a, x2 + a, …, xn + a]

[2.] Extragerea unei sub-liste: dacă L = [x1, x2, …, xn], și a, b ℕ, 1 ≤ a ≤ b ≤n, atunci: L[a:b] = [xa,

xa+1, …, xb].

[3.] Diferența a două λ-liste: dacă L1 = [x1, x2, …, xn] și L2 = [y1, y2, …, ym], cu n ≥ m, definim L1 -

L2 = [z1, z2, …, zp], unde pentru fiecare zi cu 1 ≤ zi ≤ n - m, există q ℤ pentru care L2 = q +

L1[zi:zi+m].

Elementele z1, z2, …, zp sunt ordonate crescător.

De exemplu, dacă L1 = [4, 5, 6, 7, 6, 5, 4], L2 = [0, 1, 2], iar L3 = [10, 11, 10], atunci:

[1.] L1 - L2 = [1,2], deoarece L1[1:3] = [4,5,6] = [0,1,2]+4 = L2+4, iar L1[2:4] = [5,6,7] = [0,1,2]+5 = L2+5.

[2.] L1 - L3 = [3], deoarece L1[3:5] = [6,7,6] = [10,11,10] - 4 = L3 - 4.

34

Cerință

Fiind date două liste L1 și L2, să se calculeze diferența L1 - L2.

Date de intrare

Pe prima linie a fișierului de intrare lambda.in se află lungimea λ-listei L1. Pe cea de-a doua linie se află

elementele lui L1, separate prin spații. Pe cea de-a treia linie se află lungimea lui L2, iar pe cea de-a patra

linie se află elementele liniei L2, separate prin spații.

Date de ieşire

Pe prima linie a fișierului de ieşire lambda.out se află dimensiunea λ-listei L1 - L2, iar pe cea de-a doua linie

elementele ei, separate prin spații.

Restricții și precizări

Elementele listelor sunt numere naturale mai mici decât 1000. Listele au maxim 100000 de elemente.

Exemplu

lambda.in lambda.out

7

4 5 6 7 6 5

4

3

0 1 2

2

1 2

Descriere soluție

În primul rând să observăm că soluția este de fapt numărul de poziții (şi indexul lor) pentru care diferențele dintre următoarele L2 elemente sunt egale cu diferențele dintre cele L2 elemente citite la sfârșitul fișierului. Pentru a obține 100 de puncte este necesar un algoritm cu o complexitate liniară, cum este KMP-ul (O(n+m)), deoarece soluția brută (naivă) nu s-ar încadra în timp. (O(n*m)

Sursa C++ # include <iostream>

# include <cstdio>

# define maxn 100010


int a[maxn],b[maxn],pi[maxn],pos[maxn],i,q,n,m,ct,ante,x;

void KMP()

{

int i,q=0;

for(i=2, pi[1]=0; i<=m; ++i){

while(q && a[q+1]!=a[i])

q=pi[q];

if(a[q+1]==a[i]) ++q;

pi[i]=q;

}

}

int main()

{

freopen("lambda.in","r",stdin);

freopen("lambda.out","w",stdout);

scanf("%d%d",&n,&ante);

for(i=1; i<n; ++i){

scanf("%d",&x);

b[i]=x-ante; ante=x;

}

scanf("%d%d",&m,&ante);

for(i=1; i<m; ++i){

scanf("%d",&x);

a[i]=x-ante; ante=x;

}

n--,m--;

KMP(); //FORMAREA PREFIXELOR PENTRU ALGORITMUL KMP

for(i=1; i<=n; ++i){

while(q && a[q+1]!=b[i])

q=pi[q];

35

if(a[q+1]==b[i]) ++q;

if(q==m){

q=pi[m];

pos[++ct] = i-m;

}

}

printf("%d\n", ct);

for(i=1; i<=ct; ++i)

printf("%d ", pos[i]+1);

printf("\n");

return 0;

}

Concursul OJI 2012

Elev Galbenu Dorin, Clasa a XII- a D Premiul II

culori Timp maxim de execuţie / test: 0.2s


Pasiunea Mirunei este să coloreze. Vacanţa trecută şi-a petrecut-o la bunica ei la ţară şi pentru că se cam

plictisea s-a gândit să vopsească gardul de la casa bunicii.

Gardul este compus din N scânduri dispuse una lângă alta. Miruna a găsit în garajul bunicii 5 cutii de vopsea

de culori diferite: albă, albastră, roşie, verde şi galbenă. Când a vopsit gardul, Miruna a respectat

următoarele reguli:

- Dacă o scândură era vopsită cu alb, următoarea scândură o vopsea obligatoriu cu albastru

- Dacă o scândură era vopsită cu albastru, atunci următoarea scândură o vopsea cu alb sau roşu

- Dacă o scândură era vopsită cu roşu, atunci următoarea scândură o vopsea cu albastru sau verde

- Dacă o scândură era vopsită cu verde, atunci următoarea scândură o vopsea cu roșu sau galben

- Dacă o scândură era vopsită cu galben, atunci următoarea scândură o vopsea obligatoriu cu verde

După ce a și-a terminat treaba Miruna își admira “opera de artă” și se întreba în câte moduri diferite ar fi putut

să vopsească gardul bunicii.

Cerinţă

Ajutați-o pe Miruna să găsească răspunsul la întrebarea sa.

Date de intrare

Fişierul culori.in conţine pe prima sa linie un singur număr natural N (1 N 5000).

Date de ieşire

Fişierul de ieşire culori.out va conţine pe prima sa linie un singur număr întreg reprezentând numărul

de moduri diferite în care Miruna ar fi putut să vopsească gardul bunicii.

Restricţii şi precizări:

1 N 5000;

Pentru 25% dintre teste N45.

Exemplu culori.in culori.out Explicaţii

4 24 Gardul poate fi vopsit astfel:

(alb,albastru,alb,albastru); (alb,albastru,rosu,albastru);

(alb,albastru,rosu,verde); (albastru,alb,albastru,alb);

(albastru,alb,albastru,rosu); (albastru,rosu,albastru,alb);

(albastru,rosu,albastru,rosu); (albastru,rosu,verde,rosu);

(albastru,rosu,verde,galben); rosu,albastru,alb,albastru);

(rosu,albastru,rosu,albastru); (rosu,albastru,rosu,verde);

(rosu,verde,rosu,albastru); (rosu,verde,rosu,verde);

(rosu,verde,galben,verde); (verde,rosu,albastru,alb);

(verde,rosu,albastru,rosu); (verde,rosu,verde,rosu);

(verde,rosu,verde,galben); (verde,galben,verde,rosu);

(verde,galben,verde,galben); (galben,verde,rosu,albastru);

(galben,verde,rosu,verde); (galben,verde,galben,verde).

36

Sursa C++

#include<iostream>

#include<fstream>

#define lmax 200

#define nmax 5005


typedef int nrMare[lmax];

ifstream f("culori1.in");

ofstream g("culori1.out");

int s[10],n;

nrMare a;

void read()

{ f>>n;

}

void inmulteste(nrMare a, int x)

{

int t=0;

for(int i=1;i<=a[0];i++){

a[i]=a[i]*x+t;

t=a[i]/10; a[i]%=10; }

while(t)

{ a[++a[0]]=t%10;

t/=10;

}

}

void creeaza(nrMare a,int x)

{ a[0]=0;

while(x)

{ a[++a[0]]=x%10;

x/=10; }

}

void show(nrMare a)

{ for(int i=a[0];i>=1;i--)

g<<a[i];

g<<"\n";

}

void solve()

{

if(n%2==0)creeaza(a,s[2]);

else creeaza(a,s[3]);

for(int i=1;i<=n/2-1;i++)

inmulteste(a,3);

}

int main()

{

s[1]=5; s[2]=8; s[3]=14;

read(); solve(); show(a);

return 0;}

Descriere soluție Putem nota:

Nr[ i, j ] = numărul de variante de a vopsii primele i scânduri, dacă scândura i este vopsită cu culoarea j ( j=1,

2, 3, 4, 5)

S[ i ] = numărul de variante de a vopsi primele i scânduri din gard.

Se observă că apare următoarea relație de recurență:

S[ i ] = nr[ i, 1] + nr[ i, 2] + nr[ i, 3] + nr[ i, 5]

nr[i,1]=nr[i-1,2]

nr[i,2]=nr[i-1,1]+nr[i-1,3]

nr[i,3]=nr[i-1,2]+nr[i-1,4]

nr[i,4]=nr[i-1,3]+nr[i-1,5]

nr[i,5]=nr[i-1,4]

Deoarece nr[1, j]=1, se poate vedea ușor că:

nr[i, 1]= nr[i, 5], nr[i, 2]= nr[i, 4], nr[i, 3]= 2 * nr[i, 2]

Așadar:

nr[i,2]=nr[i-1,1]+nr[i-1,3]=nr[i-2,2]+2*nr[i-2,2]=3*nr[i-2,2] pentru i>2

nr[i,1]=nr[i-1,2]=3*nr[i-3,2]=3*nr[i-2,1] pentru i>4

nr[i,3]=2*nr[i-1,2]=6*nr[i-3,2]=3*nr[i-2,3] pentru i>4

S[i]= 2*nr[i,1]+2*nr[i,2]+nr[i,3] = 6*nr[i-2,1]+6*nr[i,2,2]+3*nr[i-2,3] = 3*S[i-2]

În concluzie se obține că:

S[1]=5, S[2]=8, S[3]=14

S[2k] = 3^(k-1) * S[2], pt k>1

S[2k+1] = 3^(k-1) *S[3], pt k>1

Soluția problemei este reprezentată de numărul S[n].

Pentru calcularea acestor expresii trebuie folosite numerele mari.

37

Rezultate la olimpiade și concursuri naționale 2013-2014

Olimpiada Națională de Informatică

Nr. crt. Nume și prenume elev Clasa Premiul

1. Cernăianu Mihai Ionuț IX Medalia de argint

2. Popescu George Aurelian X Medalia de argint

3. Dabelea Ioana Viviana V Medalia de bronz

4. Stochițoiu Radu Dumitru XII Medalia de bronz

Concursuri Naționale

Nr. crt. Nume și prenume elev Clasa Concurs Premiul

1. Pogonaru Mihai XI C.N. de Soft Lugoj I

2. Comăneci Andrei XI C.N. de Soft Lugoj II

3. Popescu George Aurelian X C.N. de Soft Lugoj III

4. Popescu George Aurelian X PACO-București Mențiune

Concursuri Internaționale

Nr. crt. Nume și prenume elev Clasa Concurs Premiul

1. Comăneci Andrei XI Concursul

Internațional CANGUR II

Concursul interjudețean INFO-OLTENIA, Drobeta Turnu-Severin


1. Mărgeloiu Andrei X III, individual

2. Comăneci Andrei / Ilie Horațiu Ovidiu

XI I, echipaj

3. Mărgeloiu Andrei / Cernăianu Mihai Ionuț

IX-X Mențiune, echipaj

4. Popescu George Aurelian / Pogonaru Mihai

X-XI Mențiune, echipaj

Olimpiada Județeană de Informatică


1. Dabelea Ioana Viviana V I

2. Bunget Andreea Maria V II

3. Cernăianu Mihai Ionuț IX I

4. Popescu Octavian IX Mențiune

5. Popescu George Aurelian X I

6. Mihai Alexandru X II

7. Mărgeloiu Andrei X III

8. Ciofu Șerban X III

9. Duiu Octavian X Mențiune

10. Toma Alexandru X Mențiune

11. Pogonaru Mihai XI II

12. Comăneci Andrei XI III

13. Ilie Horațiu Ovidiu XI Mențiune

14. Gogonea Andrei XI Mențiune

15. Stochițoiu Radu Dumitru XII I

16. Galbenu Dorin XII III

38

Olimpiada Județeană de Tehnologia Informației


1. Enchescu Theodor Mihai IX II

2. Răbonțu Isabel IX Mențiune

3. Șerbănescu Valentine IX Mențiune

4. Galbenu Dorin XII I

5. Mândruț Raluca Bianca XI II

6. Ilie Horațiu Ovidiu XI III

Olimpiada Națională de Tehnologia Informației


1. Galbenu Dorin XII Medalie de bronz

Medaliații ONI 2014

VI. Gânduri, pasiuni, experienţe …

Cariera în IT, de la provocare tehnică la creativitate ”Domeniul IT nu mai este o opțiune manifestată înaintea examenului

de bacalaureat sau de admitere la facultate. Dinamica acestei industrii a reușit, în timp, să seteze alte cerințe și așteptări din partea viitorilor specialiști: mulți ani de învățare, analiză, cercetare, gândirea mai multor scenarii de testare, precum și antrenarea unor aptitudini antreprenoriale. În industria IT, acestea asigură întregirea performanțelor prin viziune, capacitatea de anticipare sau de implementare corectă a tendințelor, precum și provocarea spiritului pragmatic, extrem de necesar în această direcție.

Și pentru că am vorbit despre cât de important este ca IT-ul să devină un obicei, în sensul asumării sale în totalitate ca domeniul de activitate, este evident că demersul pornește de pe băncile școlii. Este o formare continuă, o auto-modelare a elevului, o preluare a organizării a acțiunilor sale, atât de asemănătoare celor pe care le folosește în algoritmii informatici. Mai mult decât atât, vorbind despre un domeniu dinamic, extrem de ofertant, IT-ul nu mai înseamnă tehnica dezvoltării, ci și capacitatea de a privi o funcționalitate ca o potențială direcție de business, personalizată cerințelor și trendurilor pieței. Cu siguranță, acestea sunt aspecte pe care elevii nu le aprofundează în timpul liceului, dar deschiderea, privirea de ansamblu, capacitatea de a vedea dincolo de o funcție sau de un algoritm pot deveni obiective palpabile încă din ultimii ani ai liceului.

Dezvoltarea completă a unui programator sau a unui practicant în domeniul IT este tot mai mult asociată abilităților creative, inovatoare, un alt punct comun cu segmentul antreprenorial. Astfel, programatorii nu mai sunt acei oameni tehnici retrași, de cele mai multe ori invizibili, care livrează linii de cod, dar care nu participă sub alte forme la dezvoltarea unui produs. Acum, ei îndeplinesc cu succes

39

un set complet de aptitudini precum inovație, logică, perseverență, spirit analitic.” Am terminat liceul în anul 2005, trecând succesiv prin mai multe etape în cariera profesională:

programator, consultant, antreprenor. În momentul de față sunt Product Director în cadrul companiei Avantera și fondatorul start-up-ului Softlead http://www.softlead.ro/ (prima platformă din România dedicată promovării și comercializării de aplicații informatice).

Andrei Dumitrașcu, absolvent Matematică – Informatică, C.N.T.V.

Ce începe cu ‘I’ și se termină în ”nformatică”? Viața mea se împarte în două perioade simbolice: înainte de a cunoaște informatica și după

cunoașterea ei, sau cel puțin câteva din vastele-i taine. Vă mai amintiți școala generală? Să va dau un indiciu: locul acela în care matematica domnește peste tot și toate, iar celelalte materii pălesc în fața ei. Așa mi s-a spus, așa că acesta a fost principiul după care am crescut. Cifre, numere, logică, improvizație, nesiguranță, antrenament. Până și mândria că ai rezolvat o problemă înaintea tuturor celorlalți te face să iubești matematica. Am iubit-o, o iubesc, dar... Totul devenise monoton. Trebuia să schimb ceva, așa că m-am gândit: “ Ce-ar fi dacă aș putea să-mi programez calculatorul să-mi facă toate calculele care mie îmi ocupă întreaga zi? “. Într-adevăr, a fost cea mai inspirată întrebare la care mă puteam gândi. Parcă totul era de partea mea deoarece nu a trebuit să renunț la matematică, ba chiar anumite cunoștințe au trebuit consolidate. Ce-ți poți dori mai mult decât să evoluezi de la o matematică rapidă la una supersonică?! Informatica. Până și numele îți dezvăluie menirea sa: procesarea informațiilor, perpetua căutare și elaborare de soluții noi, pur și simplu pofta de cunoaștere capătă un alt sens. Mulți o văd inabordabilă, inaccesibilă, nefolositoare poate, dar s-a gândit cineva vreodată câtă INFORMATICĂ există în fiecare moment al vieții noastre?

Viața nu oferă “a doua șansă”, ci te dirijează să ți-o confecționezi singur. La fiecare greșeală omul tinde să-și urmeze pașii înapoi pentru a vedea ce trebuie schimbat și pentru a o lua de la început. Deci întreaga viață este doar o înșiruire de pași (verificarea următoarei linii de cod), salturi (la respectiva linie de cod) și stagnări (breakpoints). Totul se rezumă într-un final la algoritmul folosit și cum timpul a devenit principala monedă de schimb și cel mai căutat artefact în prezent, avem nevoie de optimizări și de complexități cât mai mici. Lumea caută timp liber, libertate și relaxare. Nimic mai simplu: Fă-ți un algoritm eficient! Hai să te ajut. Prima dată, te gândești la o abordare brută, un plan de rezervă. În continuare, trebuie să-ți folosești toate cunoștințele în domeniu și să încerci să găsești o soluție mai bună decât cea anterioară. Ai reușit? Continuă! Nu ai reușit? Rotește-te cu un unghi α și continuă! Sunt atâtea căi în cele 360° accesibile oricui pentru rezolvarea unei probleme, atât în viața de zi cu zi, cât și la nivel programatic, încât tind să cred din ce în ce mai mult că unitatea structurală și funcțională a ființei umane este SOLUȚIA. Suntem dependenți de soluții, avem nevoie de ele, ni le dorim și în fiecare clipă încercăm să ne creăm o gamă cât mai vastă de soluții.

Dacă partea teoretică nu v-a convins, voi încerca să vă dezvălui câteva momente în care am îmbrățișat informatica nu numai cu mintea, ci și cu trupul și sufletul. Am participat la multe concursuri de informatică, dar nu am fost niciodată la două concursuri identice. De ce oare? Tot probleme, algoritmi și bătaie de cap și la deal și la vale, nu-i așa? Ei bine... NU! Informatica nu înseamnă numai învățare, cercetare și antrenament. Ea leagă prietenii, îți oferă șansa de a observa alți oameni și felul în care ei gândesc. Cine nu și-a dorit de mic, uitându-se la televizor, să ajungă un mare informatician? Oricine ar spune că n-a vrut măcar o dată să fie considerat un virtuos al descifrării codurilor și al calculatoarelor fie nu a gustat încă dulceața inteligenței artificiale (dar mai este timp), fie spre rușinea sa, minte. Primele mele concursuri de informatică au fost un adevărat “rai pe pământ”. Locul I pretutindeni, aplauze, zâmbete și o recunoaștere a meritelor ce mă îmbujora. Nu a fost nici măcar o competiție în informatică de unde să plec fără un nou prieten, fie el și pentru o scurtă durată. Am continuat pe acest drum și, ajuns la liceu, lucrurile au devenit serioase. Înfrângerile, într-adevăr, au devenit mai usturătoare, dar nu am lăsat acest lucru să mă sperie și nu regret, deoarece după cum oricărei acțiuni îi corespunde o reacțiune egală și de sens opus eram sigur că voi gusta din nou fericirea biruinței. Și nu m-am înșelat. Înfrângerile erau mai aspre, dar victoriile… INEGALABILE! Informatica a

http://www.softlead.ro/

40

devenit mai mult decât o materie. A devenit o parte din mine care cu timpul s-a tot mărit și m-a făcut din ce în ce mai fericit. Informatica e o cale a vieții, e o alegere. Am ales și prima durere am simțit-o devreme, chiar în clasa a noua. Atunci când eram mai sigur pe mine, lucrurile au luat o întorsătură nefavorabilă și am rămas acasă, în timp ce prietenii mei din celelalte colțuri ale țării își mărturiseau la Olimpiada Națională ultimele lor “aventuri informatice”. Dacă până atunci aveam nevoie de motivație suplimentară, ei bine, lucrurile s-au schimbat. Am lucrat, m-am distrat (știu că nu pare credibil, dar te simți genial atunci când găsești rezolvarea optimă a unei probleme dificile) și am lăsat timpul să vindece rănile din primul an de liceu. Drept răsplată, anul următor, în clasa a X-a, am participat la Olimpiada Nationala de Informatică din Iași. Aveam nevoie de un motiv bun pentru a merge atâta drum, nu? Și nu am regretat. Imaginați-vă un atlet. Neîncălzit corespunzător nu va da niciodată randamentul maxim, dar după prima tură își dorește din ce în ce mai mult să alerge. Așa că și eu am alergat din ce în ce mai tare, iar în clasa a XI-a nu m-am lăsat așteptat la Timișoara, la o nouă ediție a Olimpiadei. Cine se gândea vreodată că informatica ar putea avea vreo legătură cu sportul? N-ar trebui să dezvălui secretele mele, însă pentru că ați fost răbdători vă pot șopti unul. Nu există zi în care să nu eliberez stresul prin sport! Fiecare trebuie să aibă o modalitate de a înlătura oboseala psihică. În mod contrar, cea mai bună prietenă a mea și a multor altora, informatica, poate fi necruțătoare. Totuși, în încheiere, doresc tuturor să se bucure așa cum eu m-am bucurat și mă bucur de informatică. Dați-i o singură șansă și dacă nu vă este pe plac, veniți să mă căutați pe mine.

PS: Mereu am un algoritm bine stabilit pentru a scăpa de cei care vor să -mi

ceară socoteală. Slavă informaticii ! Radu Dumitru Stochiţoiu, clasa a XII-a B

Totul despre participarea mea la concursul

INFOMATRIX Te-ai întrebat vreodată cum e să realizezi un scurt metraj? Dacă ai nevoie de un talent înnăscut

pentru asta? Eu nu, până mi s-a propus să particip la concursul Infomatrix. Acesta avea mai multe categorii: programming, computer art, robotics, hardware control şi desigur short movie, categoria la care am şi ales să participam. La categoria scurt metraj tema era impusă: Ce schimbări am face în sistemul educaţional şi ce probleme credem că există în ţara noastră în educaţie?

Prima dată când eu şi colega mea de echipă Alexandra Vîlceanu ne-am întălnit să lucrăm pentru filmuleţ am vrut să ne facem un plan, să identificăm problemele pe care le găsim în sistemul educaţional, dar în acelaşi timp să şi oferim soluţii la aceste probleme, şi uite aşa s-au născut două tabere, The Resistance reprezentând elevii interesaţi de problemele pe care le are sistemul educaţional si încearcă să îl schimbe, iar a doua tabară a fost denumită Brainwash din aceasta categorie facând parte elevii dezinteresaţi de ce se întamplă în jurul lor, fiind într-un cuvânt ignoranţi.

Următorul pas a fost să ne gândim ce imagini ar reprezenta cel mai bine cele trei probleme şi trei soluţii pe care le-am găsit. Şi ne-am apucat să filmăm în parc, la şcoală, acasă, am filmat colegii, pe noi. Tema a fost destul de uşor de ilustrat cu puţină imaginaţie. Am filmat cu un aparat foto Nikon Coolpix, nu e o cameră profesională, dar filma HD şi a fost mai mult decat suficient.

Montajul filmului a fost destul de complicat, pentru că l-am realizat la limită înainte de data înscrierii. Filmuleţele au fost prima dată tăiate şi lipite în MovieMaker acolo am pus şi efecte de tranziţie de la un cadru la altul. În Adobe After Effects am pus unele efecte imagini asfel încât aceasta să pară tremurată, înceţoşată şi cadrul să se mişte. Pentru adăugarea vocilor, muzici şi lipirea finală a filmuleţului am folosit Studio Pinnacle care a fost destul de uşor de folosit volumul şi durata muzici şi vocilor care fuseseră înregistrate anterior, dar am descoperit că înregistrarea putea fi făcută şi direct în program, puteau fi ajustate acolo. Acesta ne oferea şi nişte efecte drăguţe pentru text şi imagine. Acestea fiind realizate aveam scurt metrajul!!

41

Filmul a fost înscris în concurs în ultima zi. Peste o săptămână fiind anunţate că filmuleţul s-a calificat la etapa naţională a concursului şi că trebuie să mergem la Bucureşti la Universitatea de Sud-Est Lumina, cea care organiza consursul să ne prezentam filmuleţul în faţa juriului în data de 5-6 aprilie. Pentru faza natională trebuiau îndeplinite anumite cerinţe, cum ar fi realizarea unui poster format A1 care să prezinte idea proiectului şi pentru care urma să fim punctaţi.

La Universitate am găsit standuri pentru poster exact pe măsura care ne-a fost indicată. Apoi am aşteptat ca filmuleţul să fie proiectat şi să răspundem la întrebările juriului. Au fost în total un număr de 33 de echipe din toată ţara dintre care trei au reprezentat Colegiul Naţional “Tudor Vladimirescu”: Starry eyed formată din Anca Dobrescu şi Patricia Taşcau care au obţinut locul trei, The Believers formată din Darius Dubreu si Ileana Popescu care au obţinut locul doi şi echipa The Resistance reprezentată de Alexandra Vîlceanu şi Diana Stănciulescu care au obţinut de asemenea locul doi. Realizarea unui scurt metraj poate fi facută de oricine şi este o activitate creativă, utilă şi distractivă în acelaşi timp. Sper că v-am convins să încercaţi să faceţi un scurt metraj şi de ce nu să vă înscrieţi, la anul, la concursul Infomatrix. BAFTĂ!

Stănciulescu Diana, clasa a XII-a D

Ce este Cinema 4D ? Cum sa explic?... Aţi văzut vreodata reclame sau filme care folosesc modele 3D? Ei bine acele

modele au fost realizate folosind programe de acest gen. Deci, Cinema 4D reprezintă un program de modelare tridimensionala. Un domeniu foarte interesant pentru cei ce doresc sa experimenteze cu modele 3D.

- De ce C- 4D? Poate ca aţi auzit de alte programe care folosesc acelaşi concept (Maya,3D-Max etc.) dar eu

recomand folosirea “Cinema-ului” deoarece aduce o interfaţa mai prietenoasa cu utilizatorii, nu eşti bulversat de multitudinea de butoane si funcţii pe care alte programe “le etalează”in meniu, ca în cele din urma să ajungi doar cu o durere de cap.

Interfaţa este minimalistă prezentandu-ţi doar strictul necesar. Daca eşti începator Cinema 4D asigura un mediu mai simplu de lucru fara a afecta calitatea produsului final.

In 2013 Cinema 4D a ajuns la versiunea R14 care introduce posibilitatea de a folosi “sculpting” o îmbunătăţire semnificativă deoarece nu mai ai nevoie de programe separate pentru sculptura cum ar fi Z-Brush, economisind bani și timp. (La ora actuală R15 a ieşit dar sunt prea leneş să scriu şi despre el)

Cinema 4D este disponibil în 4 variante:

Cinema 4D Prime este varianta cea mai ieftina care se bazeaza doar pe modelare 3D acesta poate fi achiziţionat direct de pe site-ul celor de la Maxon la “doar” 995$ sau gratis în versiunea Demo pentru 30 de zile.

Cinema 4D Broadcast este o varianta mai avansata aceasta permiţand crearea obiectelor dinamice şi dispune de setari pentru randare mai avansate. Când vine vorba despre preţ acesta creşte considerabil, această versiune fiind acesibilă pentru 1.695$, deasemenea este gratis pentru Demo.

42

Cinema 4D Visualize este aşa cum sugereaza şi numele varianta pentru cei ce doresc să creeze modele realiste, gradul de realism depinzănd doar de placa video şi timpul pe care eşti dispus sa îl investeşti în proiect. Pentru aşa performanţe ce mai contează 2.295 $!

Cinema 4D Studio reprezintă tot ceea ce Maxon poate să ofere, destinată profesioniştilor această variantă dispune de toate posibilitaţile din variantele anterioare aducand în plus character tools, generarea de păr şi un phyzics engine care va mări gradul de realism al proiectelor tale. Fiind varianta supremă aceasta costa 3.695$ adică aproape 12000 RON!

Dacă preţurile te-au descurajat află că Cinema 4D a pregătit o versiune gratis Cinema 4D Student aceasta poate fi descărcată şi folosită pentru 18 luni. În cea ce priveşte acomodarea cu programul, cel mai simplu mod în care poti învaţa secretele “Cinema-ului” este să vizitezi “GrayScaleGorilla”, un site foarte util. Avand numeroase videoclipuri de gen tutorial dar şi multe plugin-uri şi tool-uri care te ajută să-ţi aduci la viaţă ideile. Multitudinea de posibilităţi pe care le poţi experimenta e limitată doar de imaginaţia ta.

Timpul pe care îl investeşti într-un proiect depinde de complexitatea proiectului, placa video de care dispui şi setarile pentru randare, acestea putând să în crească pauza de ieşit în oraş de la câteva secunde la câteva ore bune sau chiar zile în cazul în care foloseşti efecte speciale cum ar fi Global Ilumination, Ambient Oclusion şi setezi Anti-Aliasing la ceva decent cum ar fi 4X. Desigur vei avea un produs finit incredibil.

În cea ce priveste cerinţele de sistem Cinema 4D nu este mofturos, acesta poate funcţiona şi pe un aparat ce dispune de Windows XP procesor Intel Pentium 4 şi o placă video cu OpenGL 2.1 acestea fiind cerinţele minime.

Nu ai nevoie de un monstru de calculator. Eu rulez Cinema 4D Studio R14 pe un Acer Aspire 5742G cu 4G RAM, procesor Intel Core i5 2.8 GHz şi placa video ATI Mobility Radeon HD 5470 de 512 Mb 64 bitzi şi vreau să spun că merge impecabil, reuşind să creez câteva clipuri video şi proiecte:

“Alien” sculpting tool în încercarea de a crea un

extraterestru

“Speakers” folosind light kit pro a celor de la

Grayscalegorilla şi sound tool

“My logo” folosind Motext

“Alex” includerea unui element grafic în poza fratelui meu

“Timex” folosind poligoane complexe

„Robot”

Andrei Florin Popescu, clasa a X-a C

43

VII. Mici programatori ...viitori (posibil!) mari

programatori Books (clasa a X-a) Timp maxim de execuţie: 0.6 s

Memoria totală disponibilă: 4 MB

O bibliotecă a cumpărat N cărţi, iar acum bibliotecarul trebuie să le sorteze şi să le aranjeze pe rafturi. Acesta a făcut o lista cu N rânduri, câte unul pentru fiecare carte, pe baza căreia face sortarea. Un rând conține în această ordine: titlul, autorul, editura, anul apariţiei şi numărul de pagini, separate de caracterul minus (-). Acesta a făcut o lista şi cu cele M edituri ale celor N cărţi, prima editura din lista fiind cea mai consacrată. Se doreşte că primele cărţi aşezate să aibă editurile cele mai consacrate. Cărţile care au aceeaşi editura sunt ordonate alfabetic (fără a face diferenţa între literele mari şi mici) după titlu, cele care au acelaşi titlu după autor, iar cele care au acelaşi autor după anul apariţiei. După sortare cărţile sunt puse pe un dulap, în ordine, de la 1 la N, câte K pe un raft, de la stânga la dreapta, începând cu raftul de sus. Dacă două cărţi vecine au acelaşi număr de pagini ele fac parte din aceeaşi zona.

Cerinţă Cunoscând numărul de cărţi, numărul de edituri, conţinutul listelor bibliotecarului şi numărul de cărţi aşezate pe un raft, să se determine numărul de cărţi din cea mai numeroasă zona.

Date de intrare Fişierul de intrare books.in conţine pe prima linie două numere naturale N şi M, separate printr-un singur spaţiu, cu semnificaţia din enunţ. Pe următoarele N linii sunt informațiile despre cărţi aşa cum apar în lista bibliotecarului, iar pe următoarele M linii sunt, în ordinea descrescătoare a consacrării lor, numele editurilor. Ultima linie conţine un număr natural K, cu semnificaţia din enunţ.

Date de ieşire Fişierul de ieşire books.out va conţine o singură linie pe care va fi afişat numărul de cărţi din cea mai numeroasă zona.

Restricţii 1 ≤ N ≤ 30000

1 ≤ M ≤ 300, 10 ≤ K ≤ 100

1 ≤ anul apariţiei ≤2014, 1 ≤ numărul de pagini ≤ 100 Titlul, autorul şi editura conţin cel mult 20 de caractere fiecare (litere mari şi mici ale alfabetului

englez). Nu există două cărţi care au editura, titlul, autorul şi anul apariţiei identice. Se consideră că toate cărţile au aceeaşi grosime. Două cărţi sunt vecine dacă au cel puţin un punct comun.

Exemplu

books.in books.out

4 2

Informatica-Ionescu-Corint-2003-200

TIC-Popescu-ALL-2000-200

Informatica-Luca-ALL-2006-250

TIC-Mihai-ALL-2013-200

ALL

Corint

2

3

Descrierea soluţiei

Soluţia 1 (30 puncte): Citim listele bibliotecarului şi sortăm cărţile folosind o funcţie de comparare. Aceasta determină dintre 2 cărţi care are prioritate, prin parcurgerea listei cu edituri, compararea titlului şi autorului cu o funtie predefinită, ultimul criteriu fiind anul apariţiei. Folosim o metodă de sortare „clasică” în care determinăm poziţia finală a unui element, ce ne permite să construim simultan şi matricea în care memorăm numărul de pagini. Pentru determinarea numărului maxim de cărţi din aceeaşi zona folosim un algoritm fill.

44

Soluţia 2 (100 puncte): Folosim aceeaşi funcție de sortare, dar folosind o metodă mai rapidă. Aceasta nu permite construirea matricei simultan cu sortarea, însă eficientă sortării permite construirea matricei separat. Aplicăm apoi acelaşi algoritm fill.

Soluţia 3 (100 puncte): Folosim aceeaşi metodă rapidă de sortare, dar fără construirea efectivă a matricei şi adaptarea algoritmului fill pe vector. Deşi pare mai eficientă ca timp decât soluţia 2, deoarece nu mai construim matricea, eficiența este diminuată de verificările făcute în algoritmul fill. Este însă mai eficientă ca memorie (o soluţie în care tipurile de date sunt folosite optim nu foloseşte mai mult de 2 MB memorie totala). Solutia 2 (100 puncte) # include <fstream>

# include <cstring>

# include <cstdlib>



ifstream f("books.in");

ofstream g("books.out");

struct book{

char tit[21],aut[21],edit[21];

short an,nr;} a[30001];

short n,m,i,j,k,x,y,z,maxi,i;

short b[3001][101];

short dx[]={-1,-1,0,1,1,1,0,-1},

dy[]={0,1,1,1,0,-1,-1,-1};

char ed[301][21],s[72],*p;

void read()

{

f>>n>>m;f.get();

for(i=1;i<=n;i++){

f.getline(s,72);

p=strtok(s,"-");

strcpy(a[i].tit,p);

p=strtok(NULL,"-");

strcpy(a[i].aut,p);

p=strtok(NULL,"-");

strcpy(a[i].edit,p);

p=strtok(NULL,"-");

a[i].an=atoi(p);

p=strtok(NULL,"-");

a[i].nr=atoi(p);

}

for(i=1;i<=m;i++)

f.getline(ed[i],21);

f>>k;

}

short search(char a[],char b[])

{

short i; char x,y;

for(i=1;i<=m;i++){

x=strcmp(ed[i],a);

y=strcmp(ed[i],b);

if(!x && !y)return 0;

else if(!x) return 1;

else if(!y) return -1;

}

}

bool cmp(book x,book y)

{

short z=search(x.edit,y.edit);

if(z==-1)return 0;

else

if(!z){

z=stricmp(x.tit,y.tit);

if(z==1)return 0;

else if(!z){

z=stricmp(x.aut,y.aut);

if(z==1)return 0;

else if(!z)

if(x.an>y.an)return 0;

}

}

return 1;

}

void fill(short i,short j)

{

short l,kx,ky,val=b[i][j];

z++; b[i][j]=0;

for(l=0;l<8;l++){

kx=i+dx[l];

ky=j+dy[l];

if(kx&&ky&&kx<=x&&ky<=y&&

b[kx][ky]==val) fill(kx,ky);

}

}

int main()

{

read(); sort(a+1,a+n+1,cmp); x=i=1;

while(i<=n){

y++;

if(y>k){ x++; y=1;}

b[x][y]=a[i++].nr;

}

for(i=1;i<=x;i++)

for(j=1;j<=y;j++)

if(b[i][j]){

z=0; fill(i,j);

if(z>maxi) maxi=z;

}

g<<maxi; f.close();

g.close();return 0;

}

Toma Alexandru, clasa a X-a C

45

VIII. Informatică DAR ... nu numai! Algoritmii imaginației

sau Matematica îndrăgostitului

uite în plan un logaritm nefericit, din vechile necazuri ce s-au tot înmulțit. îl vezi? vreau să–i schimbăm starea de spirit. hai s-adunăm doi logaritmi mai fericiți și … să speram. că, dacă aș vrea să-ți fac un compliment, ți-as zice scurt și la obiect: ești exponențială! constantă nu și clar nu liniară. ești genială. te văd urcând mereu, tu nu cobori nici când toți dau de greu. învață-mă! arată-mi asimptotele urcării tale și nu vei mai fi singură, că vin și eu agale pe urmă de matrice. oricine orice-ar zice, orice-aș determina,

cu Sarrus aș pleda. iar eu, m-aș ridica doar la puterea ta… de ințelegere. nu-i o alegere, ci o prelegere. căci eu sunt baza, iar tu ești exponentul, reînmulțindu-mă pe mine, îmi fac antrenamentul! mă străduiesc, m-arunc în gol, că fac antrenament de zburător cu DELTAplanul printre ecuații. cu cifrele mă am ca frații sari, că te voi prinde-ntr-un modul imens, unul destul să ajungi jos, dar nu mai treci de nul, ești in modul!

Radu Stochițoiu, clasa a XII-a B

Informatică … cu rimă!

Tudor Vladimirescu, acesta este liceul

Cu standarde la nivele înalte ca zmeul

Buni programatori ai ţării au plecat de aici

Căci profesorii educă elevii din clasele mici… Vrei reţeta succesului, îţi servim un algoritm,

Ajungi să-l înţelegi în funcţie de al tău ritm.

Dacă dorești să inveți nu trebuie să te simți exclus,

Ai timp oricând să înveți limbajul C++.

Îți poți exprima ideile într-un mod original, fără probleme,

Alegând un program dintre CSS sau HTML

MMAATTEE--IINNFFOO NNUU--II DDOOAARR UUNN ŞŞIIRR DDEE CCAARRAACCTTEERREE,,

EESSTTEE UUNN PPRROOFFIILL CCOOMMPPLLEEXX DDIINN TTOOAATTEE PPUUNNCCTTEELLEE DDEE VVEEDDEERREE..

Vlad Olaru, clasa a X-a C

46

De la GOOGLE citire ...

Numele de Google este o greşeala de ortografie. Iniţial trebuia să se numească Googol, un termen din matematică, care reprezintă un numar mare, egal cu 10100, adică 1 urmat de 100 de zerouri. Termenul a fost inventat de Milton Sirotta, nepotul de 9 ani al matematicianului american Edward Kasner. Motorul de căutare urma să primească acest nume datorită rolului pe care-l are: de a organiza cantitatea imensă de informaţie disponibilă pe web.

Google a început ca un proiect de cercetare al lui Larry Page şi al lui Sergey Brin, când aceştia aveau 24 şi respectiv 23 de ani. Site-ul Google îşi propune să organizeze informaţiile din toată lumea şi să le facă accesibile si folositoare. Primul birou al companiei a fost într-un garaj, in Menlo Park, California. Primul angajat a fost Craig Silverstein, acum Director Tehnologie.

Google primeşte in 2007 peste 20 de milioane de cereri în fiecare zi, din toată lumea, inclusiv Antarctica si Vatican. Pagina de început apare in 116 limbi diferite, inclusiv în latină, urdu si yoruba. De fapt, Google are cea mai mare reţea de traducători din lume.

În anul 2007, ar dura 5.707 ani ca o persoana să caute în toate cele 3 miliarde de pagini ale motorului de căutare Google. Software-ul Google o face în 0.5 secunde.

Proiectat de către japonezi ca o noua minune a tehnicii moderne cel mai mic calculator din lume se prezintă sub forma unui cub cu latura de aproximativ 5cm şi a fost botezat inspirat de către creatorii săi cu numele Space Cube. Cube vine bineînţeles de la forma sa, iar Space trimite la destinaţia pentru care a fost creat acest mini-computer, respectiv funcţionarea în spaţiul cosmic.

Logo-urile care apar pe pagina de start în timpul unor zile şi date marcante sau evenimente importante se numesc Google Doodle. Compania a creat şi un muzeu online în care se găsesc toate logourile care au fost puse până acum, cu anumite ocazii. Ele au fost create de Dennis Hwang, un artist de origine coreana stabilit în USA.

Selectate de Ana Grecu, clasa a XII-a D

Certificări C.N.T.V. în domeniul Informaticii

https://sites.google.com/site/cntvtgjiu/

Autorii articolelelor sunt profesori, actuali și foști elevi ai Colegiului Național „Tudor Vladimirescu”. La tipărirea revistei au contribuit financiar prof. Elena Goga, prof. Gabriela Nodea,prof. Oana

Dabelea, prof. Eugen Nodea.

https://sites.google.com/site/cntvtgjiu/

Revista Informatica CNTV - Nr. 1

Documents

Transcript of Revista Informatica CNTV - Nr. 1