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  

Enunț  subiect  INFO  2016  

Rezolvare  subiect  INFO  2016  

1   2  

3  

4  

5  

Rezolvare  subiect  INFO  2016  

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  

Rezolvare  subiect  INFO  2016  

1   2  

3  

4  

5  

Rezolvare  subiect  INFO  2016  

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  

Rezolvare  subiect  INFO  2016  

1  2  

3  

4  

5  6  

7  8  

9  

10  11  

Rezolvare  subiect  INFO  2016  

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        

Rezolvare  subiect  INFO  2016  

1  2  

3  

4  

5  6  

7  8  

9  

10  11   {6,  7,  10,  11}  

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

Rezolvare  subiect  INFO  2016  

1  2  

3  

4  

5  6  

7  8  

9  

10  11   {2,  3,  8,  9}  

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

Rezolvare  subiect  INFO  2016  

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  

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  

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  

Enunț  subiect  INFO  2015  

Barem  subiect  INFO  2015  

Rezolvare  subiect  INFO  2015  –  punctul  a    

O(n2)

Rezolvare  subiect  INFO  2015  –  punctul  b    

O(n · log2(n))

Rezolvare  subiect  INFO  2015  –  punctul  b    

Rezolvare  subiect  INFO  2015  –  punctul  b    

O(n)

Subiect  MATE  2015  

Enunț  subiect  MATE  2015  

Barem  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    

Rezolvare  subiect  MATE  2015  –  punctul  b    

Subiect  INFO  2014  

Enunț  subiect  INFO  2014  

Barem  subiect  INFO  2014  

Rezolvare  subiect  INFO  2014  –  punctul  a    

Rezolvare  subiect  INFO  2014  –  punctul  a    

Rezolvare  subiect  INFO  2014  –  punctul  b    

Subiect  MATE  2014  

Enunț  subiect  MATE  2014  

Barem  subiect  MATE  2014  

Rezolvare  subiect  MATE  2014  

Subiect  INFO  2013  

Enunț  subiect  INFO  2013  

Barem  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  a    

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);      

Rezolvare  subiect  INFO  2013  –  punctul  b    

Subiect  MATE  2013  

Enunț  subiect  MATE  2013  

Barem  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  

Enunț  subiect  INFO  2012  

Barem  subiect  INFO  2012  

Subiect  MATE  2012  

Enunț  subiect  MATE  2012  

Barem  subiect  MATE  2012  

Subiect  INFO  2011  

Enunț  subiect  INFO  2011  

Barem  subiect  INFO  2011  

Subiect  MATE  2011  

Enunț  subiect  MATE  2011  

Barem  subiect  MATE  2011