Olimpiada Judeteana de Informatica 2022. Rezolvare problema „Sume si secvente” in C++, clasa a V-a

Mai jos veti gasi problema “Sume si secvente” sau “sss” data la Olimpiada Judeteana de Informatica in anul 2022 la clasa a V-a, iar dupa textul problemei veti gasi si rezolvarea mea.

Problema sss:

Se da un numar N, si un sir de N numere naturale nenule.

Cerinte:

1. Determinati suma valorilor aflate pe ultimele K pozitii ın sir (unde K reprezinta valoarea celei mai din dreapta cifre nenule a primei valori din sir).
2. Ne imaginam ımpartirea sirului ın secvente ın urmatorul mod: prima secventa este formata din primele L elemente, a doua este formata din urmatoarele L – 1 elemente, a treia este formata din urmatoarele L – 2 elemente si asa mai departe, ultima secventa este formata dintr-un singur element si acesta coincide cu ultimul element din sir. Considerand suma valorilor fiecarei secvente, sa se determine cea mai mare dintre aceste sume.

Date de intrare:

Pe prima linie a fisierului sss.in se afla doua valori C si N separate printr-un spatiu. Pe linia a doua se afla N numere naturale separate prin cate un spatiu. Pentru C = 1 se rezolva doar cerinta 1 iar pentru C = 2 se rezolva doar cerinta 2.

Date de iesire: 

Fisierul sss.out contine un singur numar care reprezinta valoarea calculata conform cerintei.

Restrictii si precizari:

1. 1 <= N <= 100.000
2. Valorile din sir sunt numere naturale nenule 100.000;
3. Se garanteaza ca pentru testele ın care C = 1 sirul are cel putin K elemente;
4. Se garanteaza ca valoarea lui N permite descompunerea conform descrierii, pentru testele care au C = 2;
5. Pentru teste ın valoare de 51 de puncte avem C=1;
6. Pentru 27 de puncte dintre testele ın care C=1 primul numar din sir are o cifra;
7. Pentru teste ın valoare de 49 de puncte avem C=2;
8. Pentru teste ın valoare de 22 de puncte dintre cele care au C=2, valoarea lui N este mai mica sau egala cu 10;
9. Denumirea problemei este o prescurtare de la ”sume si secvente”

Exemplul 1:

sss.in:
1 6
120 4 21 5 31 6

sss.out:
37

Explicatii:

Ultima cifra nenula a primului element din sir este 2. Suma ultimelor doua valori din sir este 37.

Exemplul 2:

sss.in:
2 10
1 4 2 1 3 6 1 6 5 3

sss.out:
11

Explicatii:

Descompunerea se poate realiza ın secvente de lungimile 4, 3, 2 si 1. Sumele obtinute pentru fiecare sunt: 8, 10, 11, 3.

Mai jos veti gasi metoda mea de rezolvare a problemei:

#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("sss.in");
ofstream fout("sss.out");
int task = 0, n = 0, l = 0, s = 0, smax = 0, nr = 0, task1$ = 0, task2$ = 0;

void task1() {
   int i, dig;
   fin >> nr;
   
   while(nr%10 == 0) nr /= 10;
   dig = nr%10;
   
   for (i = 2; i<=n; i++) {
      fin >> nr;
      if(i >= (n-dig+1)) task1$ += nr;
   }
   
   fout << task1$;
}

void task2() {
   int i;
   
   if (n == 1) {
      fin >> nr;
      task1$ = nr;
      fout << task2$;
      return;
   }
   
   if (n == 3) {
      fin >> nr;
      s = nr;
      fin >> nr;
      s += nr;
      smax = s;
      fin >> nr;
      s = nr;
      if (s > smax) smax = s;
      task2$ = smax;
      fout << task2$;
      return;
   }
   
   while (s < n) {
      l++;
      s+=l;
   }
   
   smax = 0;
   
   for (i = l; i > 0; i--) {
      s = 0;
      for (int k = 0; k < i; k++) {
         fin >> nr;
         s += nr;
      }
      if (s > smax) smax = s;
   }
   task2$ = smax;
   fout << task2$;
}

int main() {
   fin >> task >> n;
   
   switch (task) {
      case 1: task1(); break;
      case 2: task2();
      default:;
   }
   
   return 0;
}

Sper sa va fie de folos. 😉

Daca aveti intrebari, va rog sa lasati un mesaj mai jos in comentarii.