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

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

Problema Sir:

Se da un sir format din n numere naturale nenule. Elementele sirului sunt numerotate de la stanga la dreapta ıncepand cu pozitia 1.

Cerinte:

Scrieti un program care sa determine raspunsul pentru ıntrebari de urmatoarele tipuri:

1. Care este cea mai din stanga pozitie care contine o valoare strict mai mare decat toate cele din dreapta sa? – ıntrebare de tipul 1
2. Care sunt pozitiile care contin valori strict mai mari decat toate cele din stanga lor? – ıntrebare de tipul 2
3. Daca fiecarui element aflat ıntre prima si ultima aparitie a maximului i-am mari valoarea pentru a ajunge egal cu maximul, care este suma totala a valorilor adaugate? – ıntrebare de tipul 3

Date de intrare:

Fisierul de intrare sir.in contine pe prima linie un numar C (care poate fi 1, 2 sau 3), indicand tipul ıntrebarii. Pe linia a doua se afla un numar natural N, reprezentand numarul de elemente din sir. Pe a treia linie a fisierului de intrare se afla N numere naturale, reprezentand elementele sirului, date de la stanga la dreapta (cel mai din stanga are pozitia 1 si cel mai din dreapta are pozitia N). Numerele de pe aceasta linie sunt separate prin cate un spatiu.

Date de iesire: 

1. Daca C = 1, fisierul de iesire sir.out trebuie sa contina un numar natural ce reprezinta raspunsul la o ıntrebare de tipul 1.
2. Daca C = 2, fisierul de iesire trebuie sa contina, separati prin cate un spatiu si ın ordine crescatoare, indicii determinati ca raspuns la o ıntrebare de tipul 2.
3. Daca C = 3, fisierul de iesire trebuie sa contina un numar ce reprezinta raspunsul la o ıntrebare de tipul 3.

Restrictii si precizari:

1. 1 <= C <= 3.
2. 1 <= N <= 100.000.
3. Numerele din sirul dat sunt cuprinse ıntre 1 si 10.000, inclusiv.
4. Pentru teste ın valoare de 24 de puncte avem C = 1.
5. Pentru teste ın valoare de 32 de puncte avem C = 2.
6. Pentru teste ın valoare de 44 de puncte avem C = 3.

Exemplul 1:

sir.in:
1
7
3 2 2 5 3 5 4

sir.out:
6

Explicatii:

Pentru exemplul 1, Cea mai din stanga pozitie a unei valori care este mai mare decat toate cele din dreapta sa este 6 (acolo unde se afla valoarea 5).

Exemplul 2:

sir.in:
2
7
3 2 2 5 3 5 4

sir.out:
1 4

Explicatii:

Pentru exemplul 2, 1 si 4 sunt pozitiile unde se afla valori mai mari decat toate cele din stanga lor.

Exemplul 3:

sir.in:
3
8
3 2 2 5 3 1 5
4

sir.out:
6

Explicatii:

Pentru exemplul 3, maximul fiiind 5, conform explicatiei dela ıntrebarea de tipul 3, trebuie marite doua elemente pentru a ajunge egale cu 5. Acestea sunt cel aflat pe pozitia 5 (de marit cu 2) precum si cel de pe pozitia 6 (de marit cu 4). Suma valorilor cu care avem de marit este 2 + 4 = 6.

Exemplul 4:

sir.in:
3
5
3 2 7 5 3

sir.out:
0

Explicatii:

Pentru exemplul 4, maximul este 7 si apare o singura data, deci nu se mai mareste nicio valoare.

Mai jos veti gasi metoda mea de rezolvare a problemei:

#include <fstream>

using namespace std;
int task, n, x, maximum, maximumIndex, i, sum, maximumSum;
ifstream fin("sir.in");
ofstream fout("sir.out");
int main() {
   fin >> task >> n;
   if (task == 1) {
      for (i = 1; i <= n; i++) {
         fin >> x;
         if (x >= maximum) {
            maximum = x;
            maximumIndex = i;
         }
      }
      fout << maximumIndex << endl;
   } else if (task == 2) {
      for (i = 1; i <= n; i++) {
         fin >> x;
         if (x > maximum) {
            maximum = x;
            fout << i << " ";
         }
      }
      fout << endl;
   } else {
      for (i = 1; i <= n; i++) {
         fin >> x;
         if (x > maximum) {
            maximum = x;
            sum = 0;
         } else {
            sum += maximum - x;
            if (x == maximum) maximumSum = sum;
         }
      }
      fout << maximumSum << endl;
   }
   fin.close();
   fout.close();
   return 0;
}