Olimpiada Judeteana de Informatica 2023. Rezolvare problema „Castel” in C++, clasa a V-a

Mai jos veti gasi problema „Castel” data la Olimpiada Judeteana de Informatica in anul 2023 la clasa a V-a, iar dupa textul problemei veti gasi si rezolvarea mea.

Problema Castel:

Un joc dispune de N cuburi galbene si N cuburi albastre, de dimensiuni identice; pe fiecare cub galben este scris un numar natural nenul, de cel mult 9 cifre.

Jocul urmareste construirea unui castel alcatuit din mai multe randuri de cuburi, ın care randul de sus este format dintr-un singur cub, de culoare galbena, iar fiecare dintre celelalte randuri ıncepsi se termina cu cate un cub de culoare galbena.

Oricare doua cuburi vecine pe acelasi rand au cate o latura comuna si fiecare cub, cu exceptia celor galbene de pe margine, are o latura comuna cu un cub care apartine randului de deasupra. Oricare doua cuburi cu o latura comuna au culori diferite.

Randurile de cuburi sunt numerotate de jos ın sus, ıncepand de la 1. Pentru constructia castelului se preiau cuburile galbene ın ordinea ın care acestea sunt date, iar cele albastre ıntr-o ordine oarecare, si sunt plasate pe randuri, de jos ın sus, si pe fiecare rand de la stanga la dreapta, astfel: primul cub se plaseaza pe randul de la baza (numerotat cu 1), apoi fiecare cub (galben sau albastru) se plaseaza fie ın continuare, pe randul curent, la dreapta, fie pe un rand nou, peste un cub al randului curent.

Dupa plasarea cubului din varful castelului, pe fiecare cub albastru se scrie un numar egal cu suma numerelor scrise pe cei doi vecini galbeni situati pe acelasi rand, ın stanga si ın dreapta sa. Pentru a castiga jocul, castelul obtinut trebuie sa aiba un numar maxim de randuri, chiar daca poate nu foloseste toate cuburile date.

Cerinte:

Cunoscand numerele scrise pe cele N cuburi galbene, ın ordinea data, scrieti un program care sa determine:

1. numarul cuburilor galbene, dintre cele N date, pe care sunt scrise valori de o singura cifra;
2. randul pe care se afla cubul din varful castelului si numarul scris pe acest cub;
3. numarul cuburilor albastre din care este alcatuit castelul si suma tuturor numerelor de pe acestea.

Date de intrare:

Fisierul castel.in contine:
– pe prima linie doua numere naturale C si N, ın aceasta ordine, despartite printr-un spatiu, unde C reprezinta numarul cerintei si poate avea valorile 1, 2 sau 3, iar N are semnificatia din enunt;
– pe a doua linie, N numere naturale despartite prin cate un spatiu, reprezentand numerele scrise pe cuburile galbene, ın ordinea ın care sunt preluate.

Date de iesire: 

Fisierul castel.out contine pe prima linie:
– un singur numar natural pentru rezolvarea cerintei 1, reprezentand valoarea determinata conform acestei cerinte;
– doua numere naturale despartite printr-un spatiu, ın cazul cerintelor 2 si 3. Pentru cerinta 2, primul numar reprezinta randul pe care se afla cubul din varful castelului iar cel de-al doilea numar reprezinta valoarea scrisa pe acest cub. Pentru cerinta 3, prima valoare reprezinta numarul de cuburi albastre care alcatuiesc castelul, iar a doua valoare reprezinta suma tuturor numerelor scrise pe aceste cuburi.

Restrictii si precizari:

– 3 <= N <= 5 000;

#    Punctaj       Restrictii
1           25                C=1
2          30                C=2
3          45                C=3

Exemplul 1:

castel.in:
1 12
17 5 11 2 17 17 4 2 2 5 34 88

castel.out:
6

Explicatii:

C=1 si sunt 6 cuburi pe care sunt scrise numere de o singura cifra.

Exemplul 2:

castel.in:
2 12
17 5 11 2 17 17 4 2 2 5 34 88

castel.out:
4 5

Explicatii:

Exemplul corespunde imaginii din enunt si C=2. Cubul din varful castelului este pe randul 4 si pe el este scris 5.

Exemplul 3:

castel.in:
3 12
17 5 11 2 17 17 4 2 2 5 34 88

castel.out:
6 110

Explicatii:

Exemplul corespunde imaginii din enunt, si C=3. Sunt 6 cuburi albastre ın castel si suma numerelor scrise pe acestea este 110.

Mai jos veti gasi metoda mea de rezolvare a problemei:

#include <fstream>
#include <math.h>
#include <vector>

#define NMAX 5001

using namespace std;

ifstream fin("castel.in");
ofstream fout("castel.out");

/// definim variabilele si functiile
short taskn, yellowsn; /// 5000 < 32767
int Yellows[NMAX], Blues[NMAX];
void task1(), task2(), task3(), read();
short ndig(int), usedyellows();
long rowsn(), lastn(), triang(int);

int main() {
    read();
    /// Rulam diferite programe in functie de numarul cerintei
    switch (taskn) {
        case 1: task1(); break;
        case 2: task2(); break;
        case 3: task3(); break;
        default: fout << "ERROR::~ The task number (the first number) must be 1, 2 or 3";
        /// numarul cerintei trebuie sa fie 1, 2 sau 3
    }
    return 0;
}

///citeste valorile
void read() {
    fin >> taskn >> yellowsn;
    for (int i = 0; i < yellowsn; i++) {
        fin >> Yellows[i];
    }
}

///prima cerinta
void task1() {
    int digits = 0;
    for (int i = 0; i < yellowsn; i++) {
        if (ndig(Yellows[i]) == 1) {
            digits++;
        }
        fout << "DEBUG::~ " << ndig(Yellows[i]) << endl;
    }
    fout << digits;
}

/// a doua cerinta
void task2() {
    short rows = rowsn(), last = lastn();
    fout << "DEBUG::~ " << rows << endl;
    fout << rows << " " << last;
}

/// a treia cerinta
void task3() {
    short rows = rowsn();
    long bluesn = triang(rows-1);
    for (int i = 1; i < bluesn; i++) {
        Blues[i] = Yellows[i-1] + Yellows[i];
    }
    long long result = 0;
    for (int i = 0; i < bluesn; i++) {
        result += Blues[i];
    }
    fout << bluesn << " " << result;
}

///numarul de cifre dintr-un numar
short ndig(int _number) {
    short k;
    while (_number) {
        _number /= 10;
        k++;
    }
    return k;
}

///cate randuri sunt
long rowsn() {
    short copy = yellowsn, k = 1;
    for (; k < yellowsn && copy > k; k++) {
        copy -= k;
    }
    return k - 1;
}

///numarul din ultimul rand (cel de sus)
long lastn() {
    short copy = yellowsn, k = 1, lasti = 0, last;
    for (; k < yellowsn && copy > k; (++k)++) {
        lasti += k;
        copy -= k;
    }
    last = Yellows[lasti];
    return last;
}

/// al n-lea numar triangular (1+2+3+...+n)
long triang(int n) {
    int k = 1; long result = 0;
    if (n <= 0) throw std::invalid_argument("argument shouldn't be under int::\"1\"");
    for (; k <= n; k++) {
        result += k;
    }
    return result;
}

///cuburi galbene folosite
short usedyellows() {
    return triang(rowsn());
}