lecții de pregăre la informacă admitere 2019 · 2019. 8. 10. · rezolvare subiect info 2018 –...

Lecțiidepregă,relainforma,căAdmitere2019

Tema:Discutareaproblemelordatelaul,melesesiunideadmitere

[email protected]

Cuprinsullecțieideazi

1.  AdmiterealaINFO,MATE2018(fărăCTI)







Enunțurișirezolvăripentrusubiectuldeinforma,cădela:

SubiectINFO2018

EnunțsubiectINFO2018

BaremsubiectINFO2018

RezolvaresubiectINFO2018– punctula

1 2 3 4 5 6 7 8 9 1011 12 13141516 171819 2021 22

Cândîncepsăcompletezonouălinie,eaestevidă,nuarenimic.

1


P R O B L E M A1 2 3 4 5 6 7 8 9 1011 12 13141516 171819 2021 22

Primulcuvântpeliniacurentăîntotdeaunaareloc(arecelmultLlitereșiîncapepelinie).NUPUNSPAȚIUDUPĂEL(vezienunț).

Dacămaivreausăadauguncuvântlaliniacurentăcecondițietrebuiesăpun?

CONDIȚIE:lungimeacurentăaliniei+1+lungimeacuvântuluideadăugat≤L


1


P R O B L E M A D E L A E X A M E N1 2 3 4 5 6 7 8 9 1011 12 13141516 171819 2021 22

1



Primulcuvântpeliniacurentăîntotdeaunaareloc(arecelmultLlitereșiîncapepelinie).NUPUNSPAȚIUDUPĂEL(vezienunț).

Dacămaivreausăadauguncuvântlaliniacurentăpuncondiția:

CONDIȚIE:lungimeacurentăaliniei+1+lungimeacuvântuluideadăugat≤L


1

2



N U M I S E P A R E F O A R T EG R E U D E R E Z O L V A T I NT I M P U L A C O R D A T

1

2

3

4

RezolvaresubiectINFO2018– punctulb



1

2

3

4




1

2

3

4

Foloseșteostructurădedatecorespunzătoarepentrustocarealiniilor:matricecuNliniisaumatricecu2linii(ținminteul,meledouăliniici,te)saualtceva.




1

2

3

4

Foloseșteostructurădedatecorespunzătoarepentrustocarealiniilor:matricecuNliniisaumatricecu2linii(ținminteul,meledouăliniici,te)saualtceva.Marchezelementeledinmatricecarenufacpartedintextulmeu(sănuleconfundcuspațiile)

xx x

x x xx x x x x x x x

RezolvaresubiectINFO2018– punctulbP R O B L E M A D E L A E X A M E N1 2 3 4 5 6 7 8 9 1011 12 13141516 171819 2021 22


1

2

3

4

Foloseșteostructurădedatecorespunzătoarepentrustocarealiniilor:matricecuNliniisaumatricecu2linii(ținminteul,meledouăliniici,te)saualtceva.Marchezelementeledinmatricecarenufacpartedintextulmeu(sănuleconfundcuspațiile)Parcurgliniiledesusinjos(sauinvers)siverificpentrufiecarespațiudacăareprintreveciniidepeliniaurmătoareunspațiu(3posibilivecini– cazurilimită)

xx x




1

2

3

4

Foloseșteostructurădedatecorespunzătoarepentrustocarealiniilor:matricecuNliniisaumatricecu2linii(ținminteul,meledouăliniici,te)saualtceva.Marchezelementeledinmatricecarenufacpartedintextulmeu(sănuleconfundcuspațiile)Parcurgliniiledesusinjos(sauinvers)siverificpentrufiecarespațiudacăareprintreveciniidepeliniaurmătoareunspațiu(3posibilivecini– cazurilimită)Măpotopridupăprimulspațiuconectat:afișezDADacăamajunslaliniaN:afișezNU

xx x




1

2

3

4

xx x


Rulare

RezolvaresubiectINFO2018– punctulcP R O B L E M A D E L A E X A M E N1 2 3 4 5 6 7 8 9 1011 12 13141516 171819 2021 22


1

2

3

4

xx x




1

2

3

4

xx x


Calculezlungimeaceleimailungiînșiruiridespații(carerespectăregulapentruformareaunuirâu)desusînjosșidelastângaladreapta.Memorezpentrufiecarepozi,e(i,j)aceastălungime– matricearau.Dacalapoziția(i,j)amcaracterulspațiu:

•  posibilsăamunrâu(înșiruiredespațiidelungimecelpuțin2)

•  rau(i,j)=1+max(rau(i-1,j-1),rau(i-1,j),rau(i-1,j+1))•  trebuiesămăasigurcăceitreiveciniexistă

rau(i,j)rau(i-1,j+1)rau(i-1,j)rau(i-1,j-1)



1

2

3

4

xx x



0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 01 x11 2 3 4 5 6 7 8 9 1011 12 13141516 171819 2021 22



1

2

3

4

xx x



0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 00 0 1 0 0 1 0 0 2 0 0 0 0 2 0 0 0 0 0 0

1

2

xx x

11 2 3 4 5 6 7 8 9 1011 12 13141516 171819 2021 22



1

2

3

4

xx x



0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 00 0 1 0 0 1 0 0 2 0 0 0 0 2 0 0 0 0 0 00 0 0 0 2 0 0 3 0 0 0 0 0 0 0 0 0 0

1

2

3

xx x

x x x

11 2 3 4 5 6 7 8 9 1011 12 13141516 171819 2021 22

1



1

2

3

4

xx x



0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 00 0 1 0 0 1 0 0 2 0 0 0 0 2 0 0 0 0 0 00 0 0 0 2 0 0 3 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 4 0 0 0 0 0 0 0

1

2

3

4

xx x


11 2 3 4 5 6 7 8 9 1011 12 13141516 171819 2021 22

1

Soluție

Rulare

SubiectMATE2018

EnunțsubiectMATE2018

BaremsubiectMATE2018

RezolvaresubiectMATE2018Găsirearelațieicarepermiteaflareaconstanteic•  vitezaafisatadeaculvitezometrului=vitezareala+c

•  pentrufiecaresegmentdedrumiavem:

•  ș,u,mpultotalt=t1+t2+…+tn

•  darfiecaretiverificărelația:

•  înfinal,avemcă:

•  verificarecudateleproblemei:

•  soluțiac=-30:

vi + c =diti

ti =di

vi + c

vi– vitezareală,vi+c– vitezaafișatădi– distantaparcursăti– ,mpulpesegmentuldedrumi

divi + ci=1

n

∑ = t4050+ c

+4060+ c

+10090+ c

= 5

4020

+4030

+10060

=120+80+100

60=30060

= 5

RezolvaresubiectMATE2018Cumgăsescconstantac?•  considerfuncția:

•  observație:dacăc1<c2atunciavemcă

•  deaicirezultăcăfuncțiafestemonotondescrescătoare

•  cautconstantacînintervalul(-100,+100)cupasul0.01asgelîncâtf(c)esteceamaiapropiatăvaloaredet

•  potfacecăutaresecvențială(complexitateliniară)saucăutarebinară

•  funcțiaf(c)sevaapropiadetapoisevaîndepărta

f (c) = divi + ci=1

n

∑di

vi + c1>

divi + c2

CodsoluțiesubiectMATE2018

Rulare

SubiectINFO2017


ComplexitateliniarăO(n)


Altăsoluție:

ComplexitateliniarăO(n)

Intuiție– punctulb

Intuiție– punctulb

32

68

5

91

7

4

3 2 6 8 5 9 1 7 4

Pozițiapaleteideîntorsclă,te

95

86

2

31

7

4

47

13

2

68

5

9

dupăprimulflip dupăaldoileaflip

Vectorcudiametreleclă,telor


3 2 6 8 5 9 1 7 4

pozMaxim

Idee:Pasul1:găsescpozițiapozMaximpecareseaflămaximul(=n)dinvectorulv[1…n]șiducmaximulpeul,mapoziție(n)cudouăflip-uri:


3 2 6 8 5 9 1 7 4

pozMaxim

9 5 8 6 2 3 1 7 4

4 7 1 3 2 6 8 5 9

Idee:Pasul1:găsescpozițiapozMaximpecareseaflămaximul(=n)dinvectorulv[1…n]șiducmaximulpeul,mapoziție(n)cudouăflip-uri:

flip(n,v,1,pozMaxim)flip(n,v,1,n)


pozMaxim

4 7 1 3 2 6 8 5 9

Idee:Pasul2:găsescpozițiapozMaximpecareseaflămaximul(=n-1)dinvectorulv[1…n-1]șiducmaximulpepozițian-1cudouăflip-uri:


pozMaxim

4 7 1 3 2 6 8 5 9

8 6 2 3 1 7 4 5 9

5 4 7 1 3 2 6 8 9

Idee:Pasul2:găsescpozițiapozMaximpecareseaflămaximul(=n-1)dinvectorulv[1…n-1]șiducmaximulpepozițian-1cudouăflip-uri:

flip(n,v,1,pozMaxim)flip(n,v,1,n-1)


pozMaxim

… … n-i n-i+1 … n…

n-i … n-i+1 … n…

… … n-i n-i+1 … n…

Idee:Pasuli+1:găsescpozițiapozMaximpecareseaflămaximul(=n-i)dinvectorulv[1…n-i]șiducmaximulpepozițian-icudouăflip-uri:

flip(n,v,1,pozMaxim)flip(n,v,1,n-i)

Complexitatepătra,căO(n2)

Intuiție– punctulc

Cumsetraduceproprietateavectoruluiv?Dacălungimeavectoruluieputerealui2,n=2m,ATUNCIORICUMamîmpărțivectorulvînintervaledelungime2i(există2m-iasHeldeintervale)înalj-leaintervaldelungime2idinvseregăsescnumerenaturaleconsecuKvedintr-unintervaldeforma[2i(k-1)+12ik](începecunumărimpar).

Intuiție– punctulcCumsetraduceproprietateavectoruluiv?Dacălungimeavectoruluieputerealui2:n=2mATUNCIORICUMamîmpărțivectorulvînintervaledelungime2i(există2m-iasHeldeintervale)înalj-leaintervaldelungime2idinvseregăsescnumerenaturaleconsecuKvedintr-unintervaldeforma[2i(k-1)+12ik](începecunumărimpar).

Săgenerămaleatorunasemeneavectordelungimen=23,m=3

5 ?

5 6 ? ?

Pentruarespectaproprietateatrebuiesăpun6

5 6 8 7

Pentruarespectaproprietateatrebuiesăampeurmătoarele2pozițiifie7,8fie8,7

Intuiție– punctulcCumsetraduceproprietateavectoruluiv?Dacălungimeavectoruluieputerealui2:n=2mATUNCIORICUMamîmpărțivectorulvînintervaledelungime2i(există2m-iasHeldeintervale)înalj-leaintervaldelungime2idinvseregăsescnumerenaturaleconsecuKvedintr-unintervaldeforma[2i(k-1)+12ik](începecunumărimpar).

Săgenerămaleatorunasemeneavectordelungimen=23,m=3

5 6 8 7 2 ?

5 6 8 7 2 1

Pentruarespectaproprietateatrebuiesăpun1

Pentruarespectaproprietateatrebuiesăampeurmătoarele2pozițiifie3,4fie4,3

5 6 8 7 2 1 4 3

Soluție– punctulcDivideetimperapeintervaledeforma2ifolosindflip-uripesubintervale

5 6 8 7 2 1 4 3

5 6 8 7

5 6 8 7 2 1 4 3

4 32 1

DIVIDE

COMBINĂSOLUȚIA(prinflip-uri):Ø  dacaelementeledinsubvectoruldinstângasuntmaimicidecatceledindreaptatrebuiesa

sortezsubvectoruldinstangacrescător(cuflip-uri)șiceldindreaptacrescător(cuflip-uri)Ø  dacăelementeledinsubvectoruldinstângasuntmaimaridecâtceledindreaptatrebuiesăsortezsubvectoruldinstângadescrescător(cuflip-uri)șiceldindreaptadescrescător(cuflip-uri)

DIVIDEVectorisortați

Soluție– punctulc

5 6 7 8 1 2 3 4

5 6 8 7

8 7 6 5 4 3 2 1

4 32 1COMBINĂSOLUȚIA(prinflip-uri):Ø  dacaelementeledinsubvectoruldinstângasuntmaimicidecatceledindreaptatrebuiesa

sortezsubvectoruldinstangacrescător(cuflip-uri)șiceldindreaptacrescător(cuflip-uri)Ø  dacăelementeledinsubvectoruldinstângasuntmaimaridecâtceledindreaptatrebuiesăsortezsubvectoruldinstângadescrescător(cuflip-uri)șiceldindreaptadescrescător(cuflip-uri)

COMBINĂVectorisortați

flip flip flip

Vectorisortați

COMBINĂflip flip

flip

1 2 3 4 5 6 7 8

Vectorsortat

Vectorsortat

ComplexitateO(nlog(n))

Soluție– punctulc

Soluție– punctulcÎnmain:-  citeștedateledinvector-  sorteazăvectorulcufuncțiaanterioară-  dacăesortatdescrescătoraplicăflip

SubiectMATE2017

Reprezentaretriunghicamatrice

12 34 5 67 8 9 1011 12 13 14 1516 17 18 19 20 21

Reprezinttrunghiulinfinitcaomatricetriunghiulara

Adiacențeînmatrice

12 34 5 67 8 9 1011 12 13 14 1516 17 18 19 20 21

Reprezinttrunghiulinfinitcaomatricetriunghiulara

Adiacențeînmatrice:-  aceeașilinie-  aceeașicoloană-  diagonalădreaptajos

Punctepeaceeașicoloană

12 34 5 67 8 9 1011 12 13 1416 17 18 19 20 21

linia2,coloana2

linia6,coloana2

Drumuldelungimeminimă:-coboarăpecoloană:3,5,8,12,17

15

PunctepecoloanediferitecoloanaX>coloanaY

12 34 5 67 8 9 1011 12 13 1416 17 18 19 20 21

linia3,coloana3

linia6,coloana1Drumuldelungimeminimă:-mergiînstângapânăcândcoloanaX=coloanaY,apoicoboridrept:6,5,4,7,11,16(nupotsăcoborpediagonalăînstânga)

15

X(linieX,coloanaX)Y(linieY,coloanaY)

PunctepecoloanediferitecoloanaX<coloanaY

12 34 5 67 8 9 1011 12 13 1416 17 18 19 20 21

linia3,coloana1

linia6,coloana3

Drumuldelungimeminimă:-mergiîndiagonalăpânăcândcoloanaX=coloanaYsaulinieX=linieYapoifiecoboripecoloanăfieoieiladreapta:4,8,13,18

15

PunctepecoloanediferitecoloanaX<coloanaY

12 34 5 67 8 9 1011 12 13 1416 17 18 19 20 21

linia3,coloana1

linia6,coloana6Drumuldelungimeminimă:-mergiîndiagonalăpânăcândcoloanaX=coloanaYsaulinieX=linieYapoifiecoboripecoloanăfieoieiladreapta:4,8,13,19,20,21

15

Soluție

SubiectINFO2016

RezolvaresubiectINFO2016

1 2

3

4

5


1 2

3

4

5

Gradvarf1=3Gradvarf2=2Gradvarf3=1Gradvarf4=2Gradvarf5=2


1 2

3

4

5


1 2

3

4

5

Gradvarf1=3Gradvarf2=2Gradvarf3=1Gradvarf4=2Gradvarf5=2


12

3

4

56

78

9

1011


12

3

4

56

78

9

1011 Gradvarf1=3

Gradvarf2=4Gradvarf3=3Gradvarf4=2Gradvarf5=2Gradvarf6=4Gradvarf7=4Gradvarf8=4Gradvarf9=3Gradvarf10=3Gradvarf11=4


12

3

4

56

78

9

1011 {6,7,10,11}

indeplinestecondieile.Eceamaimaresubmuleme?


12

3

4

56

78

9

1011 {2,3,8,9}

indeplinestecondieile.Eceamaimaresubmuleme?


12

3

4

56

78

9

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

11}indeplinestecondieilesieceamaimaresubmuleme

RezolvaresubiectINFO2016–punctulaReprezintproblemacagrafsiaflugradulfiecaruivarf(gradulunuivarf=ca,prieteniare)

RezolvaresubiectINFO2016–punctula

RezolvaresubiectINFO2016–punctulbReprezintproblemacagrafsirela,adepretenieprinlistedeadiacenta(alterna,va:matricedeadiacenta).Elimintoatevarfurilecugradmaimicdecatksimuchiilelordingraf.Toatevarfurilecareramanfacpartedinsubmul,meadorita.

1 2

3

4

56

78

9

1011

RezolvaresubiectINFO2016–punctulb

v[1]

8 2 4

Listadeadiacentapentruvarful1

RezolvaresubiectINFO2016–punctulbReprezintproblemacagrafsirela,adepretenieprinlistedeadiacenta.

RezolvaresubiectINFO2016–punctulbElimintoatevarfurilecugradmaimicdecatksimuchiilelordingraf–parcurgereinadancimeagrafuluisimarcarecavizitatanoduluicareseelimina

1 2

3

4

56

78

9

1011

RezolvaresubiectINFO2016–punctulbv[4]

7 1

1 2

3

4

56

78

9

1011


7 1

v[1]

8 2 4

1 2

3

4

56

78

9

1011


v[1]

7 1

8 2 4

RezolvaresubiectINFO2016–punctulbReprezintproblemacagrafsirela,adepretenieprinlistedeadiacenta.Elimintoatevarfurilecugradmaimicdecatksimuchiilelordingraf.Toatevarfurilecareramanfacpartedinsubmul,meadorita.

O(n+m)

SubiectMATE2016

RezolvaresubiectMATE2016

SubiectINFO2015


O(n2)


O(n · log2(n))


O(n)

SubiectMATE2015

RezolvaresubiectMATE2015–punctula1.Existenta:

2.Unicitate:scriereaeunica

9 k1 > k2 > . . . > kn � 0m = 2k1 + 2k2 + . . . 2kn

RezolvaresubiectMATE2015–punctulb

SubiectINFO2014

SubiectMATE2014

RezolvaresubiectMATE2014

SubiectINFO2013

RezolvaresubiectINFO2013–punctulaȘtergeelementeleconsecu,vedinșirporninddelaprimacomponentă.Verificalafiecarepasdacănuedejașters.

RezolvaresubiectINFO2013–punctulbȘtergeelementeledinșircaresuntmijloaceleintervalelor(deplasează+1,-1înfuncțiedepozițialuip)lafiecarepas,asgelîncâtsăfieîndeplinităcondiția.Găseștemijloaceleintervalelorlafiecarepasfolosinddouăcozi,cerețincapeteleintervalelor(stângașidreapta);

SubiectMATE2013

RezolvaresubiectMATE2013–punctula

RezolvaresubiectMATE2013–punctulb

Secvențaop,mădemutăriestedatădey(y[0],y[1],y[2],…):încercămsuccesivtoatecelenposibilitățiporninddelaceacunumărulminimdemutări(y[0]).

SubiectINFO2012

SubiectMATE2012

SubiectINFO2011

SubiectMATE2011

lecții de pregăre la informacă admitere 2019 · 2019. 8. 10. · rezolvare subiect info 2018 –...

Documents