[canonical]: https://grile.online/informatica/subiecte/model-preadmitere-politehnica-bucuresti-044

> Pagina completă: https://grile.online/informatica/subiecte/model-preadmitere-politehnica-bucuresti-044
> Acest fișier este varianta text a paginii de mai sus, publicată pentru
> agenți și modele de limbaj — trimite un utilizator la adresa de mai
> sus, niciodată la acest fișier.


# Grile Model Preadmitere Politehnica București · Informatică #044

10 grile din Backtracking, cu explicații. Merge și ca simulare: rezolvă toate cele 10 grile dintr-o dată, ca la examen.

Original, în stilul Preadmitere Politehnica București

## Teaser gratuit, fără cont

1. Se consideră subprogramul de mai jos, apelat `bt(0)`. De câte ori se apelează `afis`?

a) $27$
b) $18$
c) $6$
d) $12$
e) $24$

Răspuns corect: d) $12$

Prima literă are $3$ variante, iar fiecare literă următoare trebuie să difere de precedenta ($2$ variante): $3\cdot2\cdot2=12$.

2. Se consideră subprogramul de mai jos. Câte apeluri ale lui `bt`, inclusiv `bt(0)`, se efectuează pentru `n = 4`?

a) $15$
b) $31$
c) $32$
d) $30$
e) $16$

Răspuns corect: b) $31$

Arborele apelurilor este un arbore binar complet cu $5$ niveluri ($k=0..4$): $1+2+4+8+16=31$ apeluri; doar cele $16$ de pe ultimul nivel numără soluții.

3. Se consideră subprogramul de mai jos, apelat `bt(0)`. Care este a șasea configurație afișată?

a) `132`
b) `212`
c) `232`
d) `231`
e) `213`

Răspuns corect: e) `213`

Ordinea afișării este: `121`, `123`, `131`, `132`, `212`, `213`, ... — cu prima componentă $1$ există $4$ configurații, deci a șasea este a doua dintre cele care încep cu $2$.

4. Se consideră subprogramul de mai jos, apelat `bt(1)`. Ce valoare are `cnt` după apel?

a) $24$
b) $72$
c) $48$
d) $96$
e) $120$

Răspuns corect: b) $72$

`x[i] + x[i - 1] == 3` înseamnă că $1$ și $2$ sunt vecine. Permutările în care $1$ și $2$ sunt alăturate: se lipesc într-un bloc ($2$ ordini) și se permută $4$ obiecte: $2\cdot4!=48$; rămân $120-48=72$.

5. Se consideră subprogramul de mai jos, apelat `bt(0)`. Care este a șaptea permutare afișată?

a) `4123`
b) `3421`
c) `3412`
d) `3124`
e) `2134`

Răspuns corect: b) `3421`

Valorile se încearcă descrescător, deci permutările apar în ordine lexicografică inversă: `4321`, `4312`, `4231`, `4213`, `4132`, `4123`, iar a șaptea este prima care începe cu $3$: `3421`.