lecțiide& pregăre &la informacă & admitere2017...cuprinsul&lecțieide&...

Lecții de pregă,re la informa,că Admitere 2017

Tema: Discutarea problemelor date la ul,mele sesiuni de admitere

Bogdan Alexe

Echipa ACM în 2017 a Facultății

Probleme ACM 2017: hHps://icpc.baylor.edu/#worldfinals Rezultate ACM 2017: hHps://icpc.baylor.edu/worldfinals/results

Cuprinsul lecției de azi

1.  Subiect INFO 2016 2.  Subiect MATE 2016 3.  Subiect INFO 2015 4.  Subiect MATE 2015 5.  Subiect INFO 2014 6.  Subiect MATE 2014 7.  Subiect INFO 2013 8.  Subiect MATE 2013 9.  Subiect INFO 2012 10. Subiect MATE 2012 11. Subiect INFO 2011 12. Subiect MATE 2011

Enunțuri și rezolvări pentru:

Subiect INFO 2016

Enunț subiect INFO 2016

Rezolvare subiect INFO 2016

1 2

3

4

5


1 2

3

4

5

Grad varf 1 = 3 Grad varf 2 = 2 Grad varf 3 = 1 Grad varf 4 = 2 Grad varf 5 = 2


1 2

3

4

5


1 2

3

4

5

Grad varf 1 = 3 Grad varf 2 = 2 Grad varf 3 = 1 Grad varf 4 = 2 Grad varf 5 = 2


1 2

3

4

5 6

7 8

9

10 11


1 2

3

4

5 6

7 8

9

10 11 Grad varf 1 = 3

Grad varf 2 = 4 Grad varf 3 = 3 Grad varf 4 = 2 Grad varf 5 = 2 Grad varf 6 = 4 Grad varf 7 = 4 Grad varf 8 = 4 Grad varf 9 = 3 Grad varf 10 = 3 Grad varf 11 = 4


1 2

3

4

5 6

7 8

9

10 11 {6, 7, 10, 11}

indeplineste condi?ile. E cea mai mare submul?me?


1 2

3

4

5 6

7 8

9

10 11 {2, 3, 8, 9}

indeplineste condi?ile. E cea mai mare submul?me?


1 2

3

4

5 6

7 8

9

10 11 {2, 3, 6, 7, 8, 9, 10,

11} indeplineste condi?ile si e cea mai mare submul?me

Barem subiect INFO 2016

Rezolvare subiect INFO 2016 – punctul a Reprezint problema ca graf si aflu gradul fiecarui varf (gradul unui varf = ca, prieteni are)

Rezolvare subiect INFO 2016 – punctul a

Rezolvare subiect INFO 2016 – punctul b Reprezint problema ca graf si rela,a de pretenie prin liste de adiacenta (alterna,va: matrice de adiacenta). Elimin toate varfurile cu grad mai mic decat k si muchiile lor din graf. Toate varfurile care raman fac parte din submul,mea dorita.

1 2

3

4

56

78

9

10 11

Grad varf 1 = 3 Grad varf 2 = 4 Grad varf 3 = 3 Grad varf 4 = 2 Grad varf 5 = 2 Grad varf 6 = 4 Grad varf 7 = 4 Grad varf 8 = 4 Grad varf 9 = 3 Grad varf 10 = 3 Grad varf 11 = 4

Rezolvare subiect INFO 2016 – punctul b

v[1]

1 8 2 4

Lista de adiacenta pentru varful 1

Rezolvare subiect INFO 2016 – punctul b Reprezint problema ca graf si rela,a de pretenie prin liste de adiacenta.

Rezolvare subiect INFO 2016 – punctul b Elimin toate varfurile cu grad mai mic decat k si muchiile lor din graf – parcurgere in adancime a grafului si marcare ca vizitat a nodului care se elimina

1 2

3

4

56

78

9

10 11

Rezolvare subiect INFO 2016 – punctul b v[4]

4 7 1

1 2

3

4

56

78

9

10 11

Rezolvare subiect INFO 2016 – punctul b v[4]

4 7 1

v[1]

1 8 2 4

Rezolvare subiect INFO 2016 – punctul b Reprezint problema ca graf si rela,a de pretenie prin liste de adiacenta. Elimin toate varfurile cu grad mai mic decat k si muchiile lor din graf. Toate varfurile care raman fac parte din submul,mea dorita.

Subiect MATE 2016

Enunț subiect MATE 2016

Barem subiect MATE 2016

Rezolvare subiect MATE 2016

Subiect INFO 2015


O(n2)


O(n · log2(n))


O(n)

Subiect MATE 2015

Rezolvare subiect MATE 2015 – punctul a 1. Existenta:

2. Unicitate: scrierea e unica

∃ k1 > k2 > . . . > kn ≥ 0

m = 2k1 + 2k2 + . . . 2kn

Rezolvare subiect MATE 2015 – punctul b

Subiect INFO 2014

Subiect MATE 2014

Rezolvare subiect MATE 2014

Subiect INFO 2013

Rezolvare subiect INFO 2013 – punctul a Șterge elementele consecu,ve din șir pornind de la prima componentă. Verifica la fiecare pas dacă nu e deja șters.

Rezolvare subiect INFO 2013 – punctul b Șterge elementele din șir care sunt mijloacele intervalelor (deplasează +1,-‐1 în funcție de poziția lui p) la fiecare pas, aslel încât să fie îndeplinită condiția. Găsește mijloacele intervalelor la fiecare pas folosind două cozi, ce rețin capetele intervalelor (stânga și dreapta);

Subiect MATE 2013

Rezolvare subiect MATE 2013 – punctul a

Rezolvare subiect MATE 2013 – punctul b

Secvența op,mă de mutări este dată de y (y[0], y[1], y[2], …) : încercăm succesiv toate cele n posibilități pornind de la cea cu numărul minim de mutări (y[0]).

Subiect INFO 2012

Subiect MATE 2012

Subiect INFO 2011

Subiect MATE 2011

lecțiide& pregăre &la informacă & admitere2017...cuprinsul&lecțieide&...

Documents