Rezolvare Bacalaureat Informatica 2019 C++ olimpici

Data: sesiunea speciala (olimpici) 2019
Profil: Matematica-Informatica
Limbaj: C++

Tutoriale Recomandate:

Subiectul I.

1. Variabilele x și y sunt întregi. Indicați expresia C/C++ echivalentă cu (x<3)&&(y>=5) cea alăturată.

Daca analizam expresia data in enunt aceasta determina un numar x din intervalul (-oo, 3) si un numar y din intervalul [5, oo). Daca analizam variantele de raspuns de mai sus, observam faptul ca varianta c este negarea unei negatii – drept urmare, daca transpunem pe rand negarea, obtinem !(x >= 3) || (y < 5) – mai schimbam inca o data semnele si obtinem (x < 3) && (y >= 5) – exact expresia din enunt.

2. Subprogramul f este incomplet definit alăturat. Indicați expresia cu care pot fi înlocuite punctele de suspensie, astfel încât, în urma apelului de mai jos, să se afișeze cel mai mare divizor comun al numerelor nenule memorate în variabilele întregi x și y.
f(x,y,x);

void f(int m, int n, int d)
{
    if(n%d==0 && m%d==0)
        cout << d;
    else
        f(...);
 }

Avem doua numere x si y pentru care dorim sa aflam cel mai mare divizor comun. Functia noastra primeste ca si parametrii doua numere “m”, “n” si un divizor “d”. Observam faptul ca este apelata cu parametrii (x, y, x).

Pentru ca functia sa verifice pe rand divizori, trebuie ca “d” sa scada succesiv, asadar singura varianta de raspuns corecta este varianta b.

3. Utilizând metoda backtracking, se generează toate băuturile obținute amestecând sucurile a cel puțin două fructe distincte din mulţimea {afine, caise, lămâi, mere, pere}. Primele cinci soluţii obţinute sunt, în această ordine: (afine, caise), (afine, caise, lămâi), (afine, caise, lămâi, mere), (afine, caise, lămâi, mere, pere) şi (afine, caise, lămâi, pere). A șasea soluţie este:

Codificam raspunsurile noastre:
1 – afine
2 – caise
3 – lamai
4- mere
5 – pere

Variantele de raspuns devin: (1, 2), (1, 2, 3), (1, 2, 3, 4) (1, 2, 3, 4, 5) (1, 2, 3, 5).
Observam faptul ca am epuizat toate variantele care au “radacina” (1, 2, 3) – asadar trecem la (1, 2, 4) – aceasta fiind varianta a de raspuns.

4. Indicați un lanț elementar în graful neorientat cu 5 noduri, numerotate de la 1 la 5, reprezentat alăturat.

Definitia lantului elementar o gasiti in acest tutorial: Teoria Grafurilor – Lant. Ciclu. Arbore

Luam toate variantele de raspuns si aplicam definitia.

a – (1, 2, 3, 1) – acesta este un lant neelementar, deoarece trecem de doua ori prin nodul 1
b – (1, 2, 3, 4) – aceste este un lant elementar
c – (1, 2, 3, 4, 5) – aceste nu este un lant – deoarece nu avem muchia (4 – 5) in figura
d – (1, 3, 2, 1, 5) – acesta este un lant neelementar, deoarece trecem de doua ori prin nodul 1

5. Indicați valorile ce pot reprezenta numărul de fii ai fiecăruia dintre cele șase noduri ale unui arbore cu radacina

Analizand variantele de raspuns ajungem la concluzia ca doar varianta b poate produce un arbore precum cel descris in enunt.

Subiectul II.

1. S-a notat cu a%b restul împărţirii numărului natural a la numărul natural nenul b şi cu [c] partea întreagă a numărului real c.

citeşte n,k (numere naturale, k număr prim)
p <- 0; i <- 1
cât timp i <= n execută
--- x <- i
--- cât timp x%k=0 execută
------ x <-[x/k]; p <- p+1
--- i <- i+1
scrie p

a) Scrieţi valoarea afişată dacă se citesc, în această ordine, numerele 10 și 3.

Urmarim pe rand valorile ce se vor forma pe masura ce algoritmul se desfasoara.

b) Dacă pentru k se citeşte numărul 5, scrieţi trei numere care pot fi citite pentru n astfel încât, în urma executării algoritmului, pentru fiecare dintre acestea, valoarea afişată să fie 10.

Pentru a rezolva acest subpunct trebuie sa scriem multiplii lui 5, deoarece am observat mai devreme faptul ca “p” se modifica in momentul cand x e multiplu de “k”. Asadar, dupa ce generam primii 9 multiplii (5 – 10 – 15 – 20 – … – 45) observam faptul ca p = 10 (deoarece 25 este numarat de doua ori).

Raspunsul final este 45, 46, 47.

c) Scrieţi programul C/C++ corespunzător algoritmului dat.

#include    <iostream>

using namespace std;

int main()
{
    unsigned int n, k;
    unsigned int p = 0, i = 1;
    unsigned int x;

    cin >> n >> k;
    while(i <= n)
    {
        x = i;
        while(x % k == 0)
        {
            x = x / k;
            p = p + 1;
        }
        i = i + 1;
    }
    cout << p;
    return 0;
}

d) Scrieţi în pseudocod un algoritm, echivalent cu cel dat, înlocuind prima structură cât timp…execută cu o structură de tip pentru…execută.

citeşte n,k (numere naturale, k număr prim)
p <- 0
pentru i <- 1, n executa
--- x <- i
--- cât timp x%k=0 execută
------ x <-[x/k]; p <- p+1
scrie p

2. Variabila e, declarată alăturat, memorează informații despre un eveniment din anul 2019 (numărul de ordine și data desfășurării sale), iar variabila d memorează o dată calendaristică din același an. Scrieți o expresie care are valoarea 1 dacă și numai dacă data memorată în variabila d este anterioară datei desfășurării evenimentului corespunzător variabilei e.

struct tdata
{  
    int zi,luna;
} d;
struct eveniment
{  
    int nr;
    struct tdata dev;
} e;

if( (d.luna < e.dev.luna) || (d.luna == e.dev.luna && d.zi < e.dev.zi) )

3. Variabilele i şi j sunt de tip întreg, iar variabila a memorează un tablou bidimensional cu 5 linii şi 5 coloane, numerotate de la 1 la 5, având iniţial toate elementele nule.
Fără a utiliza alte variabile decât cele menționate, scrieţi secvenţa de instrucţiuni de mai jos, înlocuind punctele de suspensie astfel încât, în urma executării secvenţei obţinute, variabila a să memoreze tabloul alăturat.

Analizam putin poza si ajungem la urmatoarea concluzie: de fiecare data cand parcurgem a[i][j] si ii setam o valoare, ar trebuii sa facem acelasi lucru si pentru a[j][i].

Singura problema care ar intervenii ar fi suprascrierea unei valori. Ne folosim de mentiunea “avand initial toate elementele nule” si rezolvam aceasta problema.

for(i = 1; i <= 5; i++)
    for(j = 1; j <= 5; j++)
        if(a[i][j] == 0) 
        {
            a[i][j] = 5 - i;
            a[j][i] = 5 - i;
        }

Subiectul III.

1. Subprogramul Egal are un parametru, n, prin care primeşte un număr natural cu cel puțin o cifră impară (n∈[10,10⁹]). Subprogramul returnează valoarea 1 dacă toate cifrele impare ale lui n sunt egale între ele sau valoarea 0 în caz contrar. Scrieți definiția completă a subprogramului.
Exemplu: dacă n=7727470 sau n=7240 atunci subprogramul returnează 1, iar dacă n=7921470 atunci subprogramul returnează 0.

int Egal(unsigned int n)
{
    unsigned int cifra;
    unsigned int cifraImpara = 0;
    while(n)
    {
        cifra = n % 10;
        n = n / 10;
        if(cifra % 2 == 1 && cifraImpara == 0)
            cifraImpara = cifra;
        if(cifra % 2 == 1 && cifraImpara != 0 && cifraImpara != cifra)
            return 0;
    }
    return 1;
}

Folosim Algoritmul pentru descompunerea unui numar in cifre C++ pentru a extrage cifra curenta a numarului. Analizam in problema noastra doar cifrele impare (cifra % 2 == 1) si pentru a rezolva problema ne mai luam o variabila “cifraImpara” ce o initializam cu 0.

In momentul cand am gasit prima cifra impara, o salvam in cifraImpara. Continuam parcurgerea cifrelor impare si analizam daca cifra curenta este diferita de cifra salvata de noi. In cazul in care este diferita, inchidem functia – returnand 0.

In caz ca nu se intampla conditia de mai sus, inseamna ca totul este in-regula, asa ca returnam 1.

2. Într-un text cu cel mult 100 de caractere cuvintele sunt formate numai din litere mari și mici ale alfabetului englez și sunt separate prin câte un spațiu. Scrieţi un program C/C++ care citeşte de la tastatură un text de tipul precizat, apoi un număr natural, n (n∈[1,10²)), şi afişează pe ecran, pe linii separate, cuvintele din text care au exact n litere. Cuvintele sunt afişate în ordinea apariţiei lor în text, iar dacă nu există niciun astfel de cuvânt, se afișează pe ecran mesajul nu exista.
Exemplu: dacă se citește textul Fat Frumos este cel mai viteaz
iar n=6, se afişează pe ecran:
Frumos
viteaz

S .

#include    <iostream>
#include    <cstring>

using namespace std;

int main()
{
    char text[101];
    cin.getline(text, 101);

    unsigned int n;
    cin >> n;

    int OK = 0;
    char *cuvant = strtok(text, " ");
    while(cuvant != NULL)
    {
        if(strlen(cuvant) == n)
        {
            OK = 1;
            cout << cuvant << "\n";
        }
        cuvant = strtok(NULL, " ");
    }
    if(OK == 0)
        cout << "Nu exista";
    return 0;
}

3. Șirul f este definit astfel: f₁=x; f₂=y; f₃=z; f_i=f_i-1+f_i-2-f_i-3, unde x, y, z și i sunt numere naturale nenule, i>3.
De exemplu, dacă x=1, y=2 și z=4 șirul este: 1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, …
Se citesc de la tastatură un număr natural, n (n∈[1,10⁴]), apoi trei numere naturale din intervalul [1,10²), x, y și z, reprezentând, în această ordine, primii trei termeni ai șirului precizat mai sus. Se cere să se scrie în fișierul bac.txt primii n termeni ai șirului, separați prin câte un spațiu, în ordine inversă a apariției lor în șir. Proiectați un algoritm eficient din punctul de vedere al timpului de executare și al spațiului de memorie utilizat.
Exemplu: dacă n=10, x=1, y=2 și z=4 fișierul conține numerele: 14 13 11 10 8 7 5 4 2 1
a) Descrieți în limbaj natural algoritmul proiectat, justificând eficiența acestuia.
b) Scrieți programul C/C++ corespunzător algoritmului proiectat.

a) Aceasta problema se poate rezolva prin doua moduri. Primul mod este sa scriem o functie recursiva, iar cel de-al doilea mod este sa gasim formula generala a unui termen f_n in functie de x, y si z. Deoarece nu sunt deloc fanul functiilor recursive, o sa mergem pe gasirea unei formule generale.

Pentru a gasii formula termenului general, trebuie sa scriem mai intai cativa termeni, pentru a ne da seama cum functioneaza totul. Am facut calculele si las mai jos primii 11 termeni.

f₁ = x
f₂ = y
f₃ = z
f₄ = z – x + y
f₅ = 2z – x
f₆ = 2z – 2x + y
f₇ = 3z – 2z
f₈ = 3z – 3x + y
f₉ = 4z – 3x
f₁₀ = 4z – 4x + y
f₁₁ = 5z – 4x

Asadar, ajungem la concluzia ca f_n = (n / 2 – 1) * z – (n / 2 – 1) * x + y daca n este par si f_n = (n / 2) * z – (n / 2 – 1) * x daca n este impar. Odata ce am ajuns la aceasta formula, putem implementa algoritmul foarte simplu.

Algoritmul nostru preia numarul n si calculeaza termenii in functie de acesta. Are o complexitate liniara O(n) in timp. De asemenea complexitatea in spatiu este si ea redusa folosind in total doar 4 variabile pentru a rezolva problema.

Varianta iterativa:

#include    <iostream>

using namespace std;

int main()
{
    unsigned int n, x, y, z;
    cin >> n >> x >> y >> z;
    for(int i = n; i >= 4; i--)
    {
        if(i % 2 == 0)
            cout << (i / 2 - 1) * z - (i / 2 - 1) * x + y << " ";
        else
            cout << (i / 2) * z - (i / 2 - 1) * x << " ";
    }
    cout << z << " " << y << " " << x;
}

Varianta recursiva:

#include    <iostream>

using namespace std;

int n_termen(int n,int x,int y,int z)
{
    if(n > 3)
        return n_termen(n-1,x,y,z) + n_termen(n-2,x,y,z)-
               n_termen(n-3,x,y,z);
    if(n == 3) return z;
    if(n == 2) return y;
    if(n == 1) return x;
    if(n == 0) return 0;
}

int main()
{
    unsigned int n, x, y, z;
    cin >> n >> x >> y >> z;

    for(int i = n; i > 3; i--)
        cout << n_termen(i,x,y,z) << " ";
    cout << z << " " << y << " " << x;

    return 0;
}

Comentarii

2019 bac c++info informatica mate-info olimpici rezolvare rezolvare bacalaureat simulare subiecte subiecte bacalaureat subiecte olimpici

Rezolvare Bacalaureat Informatica 2019 C++ olimpici

Subiectul I.

Subiectul II.

Subiectul III.

Tipul struct in C# | Teorie si exemple

Tutorial Python – Invata in 10 minute

S-ar putea sa iti placa