Admitere Informatică Iași 2017 – Subiecte și rezolvări

Mai sunt vreo două luni până la examenul de admitere la Facultatea de Informatică din Iași, așa că m-am gândit să adaug și rezolvările subiectelor date în anul 2017. Pe cele din 2018 le puteți găsi aici.

Subiectul I. Problema 1.

Fie $x$ o variabilă întreagă care conține cel mai mic număr natural nenul, multiplu de $36$ divizibil cu toate numerele prime mai mici decât $10$ Precizați care dintre expresiile C++ de mai jos este adevărată.

1. (x < 1000) && (x % 27 == 0)
2. (x > 1000) && ((x * x * x) % 1000 == 0)
3. ((x * x) / 16) % 2 == 0
4. (x % 100 == 0) || (x / 100 == 0)

Numerele prime mai mici decât $10$ sunt $2$ $3$ $5$ și $7$ deci variabila $x$ este egală cu $\cmmmc(2, 3, 5, 7, 36) = 1260$ Acum trebuie să evaluăm fiecare expresie dată în parte. A este falsă deoarece 1260 > 1000. B este adevărată pentru că 1260 > 1000 și x * x * x este divizibil cu 1000, căci se termină în trei zerouri. C este falsă deoarece (x * x) / 16 == 99225, care este impar. D este falsă pentru că nici x % 100 == 0 și nici x / 100 == 0 nu sunt adevărate. Așadar, varianta corectă este B.

Subiectul I. Problema 2.

Se consideră subprogramul $F$ de mai jos, descris în pseudocod. Subprogramul primește un număr natural nenul în parametrul $u$ și întoarce un număr natural când se oprește.

subprogram F(u)
  (u - număr natural nenul)
    count <- 0
    cât timp u != 1
        dacă u este par atunci
            u <- u / 2
        altfel
            u <- u * 3 + 1
        count <- count + 1
    returnează count

a) Care este valoarea returnată de subprogram pentru parametrul $u = 10$

Iată valorile variabilelor $u$ și $\mathit{count}$ inițiale și după fiecare intrare în while:

Răspunsul este $6$

b) Dați exemplu de un număr natural $u$ astfel încât $F(u)$ să returneze $7$

Trebuie să găsim un număr pentru care se efectuează $7$ operații. Cel mai simplu ar fi să-l facem să treacă mereu prin prima ramură a if-ului, pentru a-i afla ușor valoarea. Observăm că $F(2^n)$ returnează $n$ deoarece $2^n$ va trebui să se înjumătățească de $n$ ori pentru a deveni $1$ Deci, un răspuns posibil este $2^7$ adică $128$

c) Scrieți în pseudocod un subprogram recursiv, echivalent cu $F$ care nu folosește instrucțiuni repetitive.

Privim fiecare intrare în while a lui u ca pe un apel recursiv ce îl are ca parametru pe noul u. Subprogramul recursiv cerut va arăta cam așa:

subprogram F(u)
  (u - număr natural nenul)
    dacă u = 1 atunci
        returnează 0
    dacă u este par atunci
        returnează 1 + F(u / 2)
    returnează 1 + F(u * 3 + 1)

d) Scrieți o funcție C++ care implementează subprogramul $F$ dat.

Un răspuns posibil este:

int F(int u) {
    int count = 0;
    while (u != 1) {
        if (u % 2 == 0)
            u /= 2;
        else
            u = u * 3 + 1;
        count++;
    }
    return count;
}

Subiectul II. Problema 1.

O matrice cu $8$ linii, formată doar din $0$ și $1$ are următoarele trei proprietăți:

1. Prima linie conține un singur element cu valoarea $1$
2. Linia $j$ conține de două ori mai multe elemente nenule decât linia $j - 1$ pentru orice $j \in \{2, 3, \ldots, 8\}$
3. Ultima linie conține un singur element cu valoarea $0$

Care este numărul total de elemente cu valoarea $0$ din matrice?

1. $777$
2. $769$
3. $528$
4. Nu există o astfel de matrice

Din primele două proprietăți, rezultă că linia $j$ are $2^{j - 1}$ elemente nenule. Cum ultima linie conține un singur element cu valoarea $0$ deducem că numărul de coloane ale matricei este $2^7 + 1 = 129$ (numărul de elemente de pe ultima linie). Putem calcula numărul de zerouri din matrice scăzând numărul de elemente nenule din numărul total de elemente. Obținem:

Deci, răspunsul corect este A.

Subiectul II. Problema 2.

Fie $T$ un arbore și $v$ un nod al acestuia. Construim un graf $G$ astfel: creăm $11$ copii distincte $T_1, T_2, \ldots, T_{11}$ ale arborelui $T$ și adăugăm toate muchiile posibile între nodurile $v_1, v_2, \ldots, v_{11}$ unde $v_i$ este copia din arborele $T_i$ corespunzătoare nodului ales $v$ În graful rezultat, numărul de muchii este dublul numărului de noduri. Câte noduri are arborele inițial $T$

1. $6$
2. $5$
3. $4$
4. Niciuna dintre variantele A, B, C

Notăm cu $x$ numărul de noduri din arborele inițial $T$ Nodurile $v_1, v_2, \ldots, v_{11}$ vor forma un subgraf complet (o clică), deci contribuie cu $11 \cdot 10 / 2 = 55$ de muchii la graful final. La acestea se adaugă muchiile celor $11$ arbori, deci $11 \cdot (x - 1)$ muchii. (Se știe că un arbore cu $x$ noduri are $x - 1$ muchii.) Numărul de noduri ale grafului este $11 \cdot x$ Știind că graful rezultat are de două ori mai multe muchii decât noduri, obținem: $55 + 11 \cdot (x - 1) = 22 \cdot x$ de unde $x = 4$ Varianta corectă este C.

Subiectul II. Problema 3.

Considerăm un alfabet $A$ format dintr-o mulțime finită de caractere. Un cuvânt este o secvență nevidă de caractere distincte din $A$ Lungimea unui cuvânt este numărul de caractere din care acesta este format. Un $p$sistem $\htmlClass{katexified}{(} p \ge 1$ este definit ca o mulțime $S$ de cuvinte, toate de lungime $p$ având proprietățile:

• P1. Oricare două cuvinte din $S$ au exact un caracter comun.
• P2. Orice caracter din alfabetul $A$ apare în cel puțin un cuvânt din $S$

Exemplu: Pentru $A = \{\texttt{'a'}, \texttt{'b'}, \texttt{'c'}\}$ mulțimea $S = \{\texttt{"ab"}, \texttt{"ac"}\}$ este un $2$sistem.

a) Scrieți un $3$sistem peste alfabetul $A = \{\texttt{'a'}, \texttt{'b'}, \texttt{'c'}, \texttt{'d'}, \texttt{'e'}, \texttt{'f'}\}$

Glumesc.

$S = \{\texttt{"abc"}, \texttt{"ade"}, \texttt{"bdf"}\}$

b) Scrieți un program C++ care:

• b1) Citește de la tastatură un întreg $m$ $1 \le m \le 26$ și construiește alfabetul $A$ format din primele $m$ caractere ale alfabetului $\{\texttt{'a'}, \texttt{'b'}, \ldots, \texttt{'z'}\}$
• b2) Citește de la tastatură un întreg $n \ge 1$ și o secvență de $n$ șiruri de caractere. Se presupune că fiecare șir citit este format din caractere distincte din $A$ (este un cuvânt). Nu este necesară validarea datelor citite.
• b3) Verifică dacă există un $p$ astfel încât mulțimea de cuvinte citite reprezintă un $p$sistem. În caz afirmativ, va fi afișat mesajul "DA", în caz contrar "NU".

Ca să ne ușurăm munca, am folosit operații pe biți. Recomand citirea acestui articol înainte de a continua. Pentru reprezentarea cuvintelor și a „vectorilor caracteristici” am reținut bitmask-uri în care bitul de pe poziția $i$ este $1$ dacă a $i$a literă din alfabet este inclusă în acea submulțime (numerotarea făcându-se de la $0$ Probabil că se acorda punctaj maxim și pentru un program fără operații pe biți, dar soluția aceea e prea directă și plictisitoare. Și mai puțin eficientă.

Pentru prima cerință, am reținut alfabetul într-un bitmask cu 1 pe biții 0, 1, …, m - 1. Acest mod de reprezentare ne va ajuta mai încolo. Pentru a doua cerință, am definit un struct String (pentru reținerea cuvintelor) cu două câmpuri: len (lungimea) și mask (bitmask cu literele incluse în cuvânt). Am reținut cuvintele într-un vector s cu elemente de tip String.

Pentru a treia cerință, am parcurs vectorul s verificând dacă lungimile tuturor cuvintelor sunt egale (condiție necesară pentru a forma un $p$sistem). În același timp, am reținut într-un bitmask mask literele care apar în cel puțin un cuvânt. Acest număr se calculează efectuând sau pe biți între toate bitmask-urile cuvintelor. Înainte de a continua, verificăm dacă toate literele din alfabet au fost găsite, adică dacă mask == a. La final, pentru fiecare două cuvinte din s, testăm dacă intersecția lor (x.mask & y.mask) are un singur element. Asta se face ușor cu operații pe biți, testând dacă numărul respectiv este o putere a lui 2.

#include <cstring>
#include <iostream>

using namespace std;

const int SMAX = 27; // lungimea maximă a unui șir este 26 + 1 de la '\0'
const int NMAX = 100; // (NMAX - 1) = valoarea maximă pe care o poate lua n

// Un struct pentru reținerea cuvintelor:
struct String {
    int len; // lungimea cuvântului
    int mask; // submulțimea de litere din cuvânt
};

int n, m, a; // n, m, alfabetul
String s[NMAX]; // vectorul de cuvinte

// O funcție care calculează mask-ul pentru un șir dat:
int getMask(char* str) {
    int mask = 0; // Inițial nu avem nicio literă în cuvânt.
    for (int i = 0; str[i]; i++) // Parcurgem șirul.
        mask |= 1 << (str[i] - 'a'); // Setăm bitul literei str[i] la 1.
    return mask;
}

// O funcție care testează dacă x este o putere a lui 2,
// adică dacă x are exact un bit 1.
bool isPowOf2(int x) { // Considerăm că x este nenul.
    return !(x & (x - 1));
}

int main() {
    char str[SMAX];

    // Cerința b1:
    cin >> m;
    a = (1 << m) - 1; // Construim alfabetul.

    // Cerința b2:
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> str;
        s[i].len = strlen(str);
        s[i].mask = getMask(str);
    }

    // Cerința b3:
    int mask = s[1].mask; // mask reține submulțimea literelor care se regăsesc în cel puțin un cuvânt:
    for (int i = 2; i <= n; i++) {
        mask |= s[i].mask; // Actualizăm mask cu mask-ul curent.
        if (s[i].len != s[1].len) { // Testăm dacă s[i] (nu) are aceeași lungime ca șirurile precedente.
            cout << "NU\n";
            return 0;
        }
    }

    if (mask != a) { // Testăm dacă mask nu cuprinde toate literele din a.
        cout << "NU\n";
        return 0;
    }

    // Luăm câte două cuvinte
    for (int i = 1; i < n; i++)
        for (int j = i + 1; j <= n; j++)
            if (!isPowOf2(s[i].mask & s[j].mask)) { // și testăm dacă (nu) au exact o literă în comun.
                cout << "NU\n";
                return 0;
            }

    cout << "DA\n";
    return 0;
}

Subiectul II. Problema 4.

O rețea de comparatori de tip $n$ $\htmlClass{katexified}{(} n \ge 2$ și de dimensiune $m$ $\htmlClass{katexified}{(} m \ge 1$ este o secvență $(c_1, c_2, \ldots, c_m)$ în care fiecare element $c_i$ numit comparator, este o pereche de numere întregi $(j, k)$ cu proprietatea $1 \le j \lt k \le n$

Exemplu: Rețeaua $R = ((1, 2), (2, 3))$ are tipul $3$ și dimensiunea $2$

Dacă $a$ este un vector de $n$ numere întregi și $R$ este o rețea, notăm cu $R(a)$ vectorul obținut aplicând următoarele transformări lui $a$ Pentru fiecare comparator $c_i = (j, k)$ $1 \le i \le m$ din $R$ în ordinea în care aceștia apar în rețea, dacă $a[j] \gt a[k]$ atunci în vectorul $a$ interschimbăm valorile de la pozițiile $j$ și $k$

Exemplu: Pentru $R = ((1, 2), (2, 3))$ și $a = (30, 20, 10)$ avem $R(a) = (20, 10, 30)$

a) Fie $R = ((2, 4), (1, 2), (3, 4), (2, 3))$ și $a = (40, 30, 20, 10)$ Calculați $R(a)$ și scrieți valorile intermediare ale vectorului $a$ corespunzătoare transformărilor efectuate.

b) Dați exemplu de o rețea $R$ de tip $4$ cu proprietatea că pentru orice vector $a$ format din $4$ numere întregi distincte, $R(a)$ va avea elementele ordonate crescător. Justificare.

$R = ((1, 2), (2, 3), (3, 4), (1, 2), (2, 3), (1, 2))$ Această rețea de comparatori este practic o simulare a algoritmului Bubble Sort: După primele $3$ operații, elementul cel mai mare ajunge pe ultima poziție, după următoarele $2$ operații, al doilea cel mai mare element ajunge pe poziția $3$ iar la final și celelalte două elemente vor ajunge pe pozițiile corespunzătoare.

c) Scrieți o funcție C++ care primește ca parametri numerele naturale $n$ și $m$ o matrice $R$ cu $m$ linii și $2$ coloane, reprezentând o rețea de comparatori, și un vector $a$ de $n$ numere întregi. Funcția va calcula vectorul $R(a)$ și va returna valoarea $1$ dacă acesta are elementele ordonate crescător. În caz contrar, va returna valoarea $0$

Din nou, se cere scrierea un program destul de imediat. Pur și simplu efectuăm operațiile, iar la final parcurgem vectorul pentru a testa dacă este sortat.

bool R(int n, int m, int r[][2], int a[]) {
    // Efectuăm operațiile:
    for (int i = 1; i <= m; i++)
        if (a[r[i][0]] > a[r[i][1]]) {
            int aux = a[r[i][0]];
            a[r[i][0]] = a[r[i][1]];
            a[r[i][1]] = aux;
        }

    // Testăm dacă a este sortat:
    for (int i = 1; i < n; i++)
        if (a[i] > a[i + 1])
            return false;
    return true;
}

Subiectul III. Problema 1.

Se consideră toate șirurile de lungime $l \in \{1, 2, 3\}$ formate din litere din mulțimea $\{\texttt{'a'}, \texttt{'b'}, \texttt{'c'}, \texttt{'d'}, \texttt{'e'}\}$ Câte dintre aceste șiruri au un număr par de vocale? $\htmlClass{katexified}{(} \texttt{'a'}$ și $\texttt{'e'}$ sunt vocale)

1. $79$
2. $80$
3. $81$
4. $78$

Trebuie avută atenție că literele dintr-un cuvânt se pot repeta. Șirurile de lungime $1$ trebuie să conțină o consoană, deci numărul lor este $3$ Șirurile de lungime $2$ trebuie să conțină fie două consoane $\htmlClass{katexified}{(} 3^2$ variante), fie două vocale $\htmlClass{katexified}{(} 2^2$ variante). Șirurile de lungime $3$ pot conține trei consoane $\htmlClass{katexified}{(} 3^3$ variante), sau o consoană și două vocale $\htmlClass{katexified}{(} 3 \cdot 3^1 \cdot 2^2$ variante). Explicația pentru $3$ul din ultima formulă este că putem alege în $3$ moduri poziția unde punem consoana. Dacă avem fixată această poziție, știm că pe celelalte vom pune vocale, așa că nu mai înmulțim formula cu nimic. Adunând rezultatele obținem $79$ deci răspunsul este A.

Subiectul III. Problema 2.

Se consideră funcția recursivă $F$ de mai jos. Ce valoare va returna apelul $F(0, 63, 64)$

int F(int u, int v, int t) {
    int m = (u + v) / 2;
    if (u >= v) { return u; }
    else if (m * m > t) { return F(u, m - 1, t); }
    else if (m * m < t) { return F(m + 1, v, t); }
    else { return m; }
}

Trebuie doar să urmărim lanțul de apeluri recursive. Se observă că funcția dată calculează radicalul lui $t$ în timp logaritmic, folosind o tehnică asemănătoare căutării binare. Precizia este însă foarte proastă, fiind vorba de numere întregi.

Apelul #1: F(0, 63, 64)
m = (0 + 63) / 2 = 31
m * m = 961 > 64

Apelul #2: F(0, 30, 64)
m = (0 + 30) / 2 = 15
m * m = 225 > 64

Apelul #3: F(0, 14, 64)
m = (0 + 14) / 2 = 7
m * m = 49 < 64

Apelul #4: F(8, 14, 64)
m = (8 + 14) / 2 = 11
m * m = 121 > 64

Apelul #5: F(8, 10, 64)
m = (8 + 10) / 2 = 9
m * m = 81 > 64

Apelul #6: F(8, 9, 64)
m = (8 + 9) / 2 = 8
m * m = 64 = 64
Se returnează 8.

Subiectul III. Problema 3.

O casă are $n \times m$ camere $\htmlClass{katexified}{(} n, m \ge 2$ și este reprezentată ca o matrice cu $n$ linii (numerotate de la $0$ la $n - 1$ și $m$ coloane (numerotate de la $0$ la $m - 1$ Camera de la linia $i$ $\htmlClass{katexified}{(} 0 \le i \le n - 1$ și coloana $j$ $\htmlClass{katexified}{(} 0 \le j \le m - 1$ este identificată prin perechea de numere $(i, j)$ Toate camerele, cu excepția celor situate pe prima linie $\htmlClass{katexified}{(} i = 0$ și a celor situate pe prima coloană $\htmlClass{katexified}{(} j = 0$ au câte un comutator. Acționarea comutatorului din camera $(i, j)$ (unde $1 \le i \le n - 1$ $1 \le j \le m - 1$ conduce la următorul rezultat: În fiecare dintre camerele $(i, j)$ $(i - 1, j)$ $(i, j - 1)$ $(i - 1, j - 1)$ (camera cu comutatorul, cea de deasupra, cea de la stânga și cea de deasupra și la stânga), dacă lumina era aprinsă, ea se stinge, iar dacă era stinsă, se aprinde.

a) Matricea de mai jos reprezintă starea luminilor din fiecare cameră dintr-o casă cu $n = 5$ linii și $m = 4$ coloane. Pozițiile $(0, 1)$ $(0, 2)$ $(1, 1)$ $(1, 3)$ $(2, 2)$ $(2, 3)$ conțin valoarea $1$ reprezentând faptul că luminile sunt aprinse în camerele respective, iar celelalte poziții conțin valoarea $0$ reprezentând faptul că luminile sunt stinse. Comutatoarele din care camere trebuie acționate pentru a stinge luminile din toate camerele?

$$\begin{pmatrix} 0 & 1 & 1 & 0\\ 0 & 1 & 0 & 1\\ 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 \end{pmatrix}$$

Acționăm comutatoarele din camerele $(1, 2)$ și $(2, 3)$

b) Scrieți o funcție C++ care primește $5$ parametri de intrare: o matrice $A$ de $0$ și de $1$ reprezentând starea luminilor din camere, dimensiunile $n$ $\htmlClass{katexified}{(} n \ge 2$ și $m$ $\htmlClass{katexified}{(} m \ge 2$ ale acesteia, precum și două numere naturale $i$ $j$ $\htmlClass{katexified}{(} 1 \le i \le n - 1$ $1 \le j \le m - 1$ reprezentând o cameră $(i, j)$ cu comutator. Funcția trebuie să modifice matricea primită ca parametru, astfel încât aceasta să conțină starea luminilor după acționarea comutatorului din camera $(i, j)$ Nu este necesară validarea parametrilor de intrare.

// NMAX = numărul maxim de linii ale matricei
// MMAX = numărul maxim de coloane ale matricei
void change(bool A[NMAX][MMAX], int n, int m, int i, int j) {
    A[i][j] ^= true;
    A[i - 1][j] ^= true;
    A[i][j - 1] ^= true;
    A[i - 1][j - 1] ^= true;
}

Expresia x ^= true, unde x este de tip bool, îl schimbă pe x din 0 în 1, sau din 1 în 0. Desigur, în loc de x ^= true, puteam scrie x = !x, dar e mai drăguț cu XOR

c) Scrieți o funcție C++ care primește ca parametri de intrare o matrice $A$ de $0$ și de $1$ reprezentând starea luminilor din camere, precum și dimensiunile $n$ $\htmlClass{katexified}{(} n \ge 2$ și $m$ $\htmlClass{katexified}{(} m \ge 2$ ale acesteia. Funcția trebuie să returneze $1$ dacă există o mulțime de camere astfel încât, acționând comutatorul în fiecare cameră din mulțime o singură dată, să se obțină stingerea luminilor din toate camerele. Altfel, funcția va returna $0$ În rezolvare, puteți utiliza funcția de la punctul b). Nu este necesară validarea parametrilor de intrare. Se va folosi un algoritm cât mai eficient din punct de vedere al timpului de execuție; soluțiile de tip backtracking vor primi cel mult două puncte.

Observăm că nu contează ordinea în care acționăm comutatoarele, așa că vom alege una convenabilă: Parcurgem matricea de sus în jos și de la stânga la dreapta, începând de la linia $1$ și coloana $1$ Când ne aflăm la poziția $(i, j)$ acționăm comutatorul doar dacă poziția $(i - 1, j - 1)$ este setată la $1$ Asta pentru că acea poziție nu va mai fi vizitată niciodată, și nu are sens să o facem $0$ mai devreme, stricând eventual alte poziții deja vizitate.

Dacă poziția curentă $(i, j)$ se află pe ultima linie și poziția $(i, j - 1)$ a rămas setată la $1$ înseamnă că nu există soluție, căci nu ne vom mai putea atinge de poziția respectivă. Similar, dacă suntem pe ultima coloană și poziția $(i - 1, j)$ a rămas $1$ nu există soluție. Când ne aflăm la ultima poziție, adică $(n - 1, m - 1)$ testăm și dacă elementul de pe $(n - 1, m - 1)$ a rămas $1$ caz în care din nou nu avem soluție. Dacă matricea a trecut cu succes de toate aceste teste, înseamnă că există soluție, și vom returna true.

Complexitatea este $O(m \cdot n)$ și este optimă pentru că e egală cu dimensiunea input-ului. La început i-am făcut o copie matricei, și am lucrat pe ea, ca să nu modific matricea dată.

bool check(bool A[NMAX][MMAX], int n, int m) {
    bool a[NMAX][MMAX];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            a[i][j] = A[i][j];
    for (int i = 1; i < n; i++)
        for (int j = 1; j < m; j++) {
            if (a[i - 1][j - 1])
                change(a, n, m, i, j);
            if (i == n - 1 && a[i][j - 1])
                return false;
            if (j == m - 1 && a[i - 1][j])
                return false;
            if (i == n - 1 && j == m - 1 && a[i][j])
                return false;
        }
    return true;
}

Sfârșit! Dacă aveți vreo întrebare despre problemele din acest articol, sau vreți să postez și rezolvările subiectelor date în alți ani, nu ezitați să lăsați un comentariu mai jos