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

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

Problema Cadouri:

Inaintea vacantei de Paste la scoala s-au primit cadouri pentru elevii din clasa a V-a. Sunt N cutii cu bomboane si se cunoaste numarul de bomboane din fiecare cutie. Numarul de cutii de bomboane primite de fiecare copil trebuie sa fie acelasi. Acest numar trebuie sa fie mai mare sau egal cu 2.
Cutiile cu bomboane vor fi oferite ın ordinea primirii primele cutii primului copil urmatoarele cutii celui de al doilea copil urmatoarele cutii celui de al treilea copil etc.
Se doreste sa se ımparta cutiile cu bomboane unui numar cat mai mare de copii. De asemenea mai este o conditie: sa se ımparta copiilor toate cutiile sau cel mult una dintre cutii sa ramana neoferita.
In cazul ca se ia decizia ca o cutie sa nu fie data copiilor aceasta se pastreaza de catre doamna diriginta pentru a-i servi pe acestia la ıntoarcerea la scoala iar restul cutiilor cu bomboane se pun pe catedra ın ordinea ın care au fost primite fara ca elevii sa stie despre cea pastrata.
Alegerea acestei cutii trebuie facuta astfel incat numarul total de bomboane care se ımpart sa fie cat mai mare.

Cerinte:

1. Care este numarul maxim de copii care vor primi cadouri?
2. Care este numarul maxim posibil de bomboane pe care le poate primi un copil in conditiile descrise mai sus?

Pentru ambele cerinte trebuie determinat si numarul de bomboane din cutia care eventual se pastreaza.

Date de intrare:

Fisierul de intrare cadouri.in contine pe prima linie un numar C, indicand cerinta.
Pe linia a doua se afla un numar N, reprezentand numarul de cutii de bomboane primite la scoala. Pe linia a treia se afla N numere, separate prin cate un spatiu, reprezentand numarul de bomboane din fiecare cutie, in ordinea in care acestea au fost primite.

Date de iesire: 

Fisierul de iesire cadouri.out contine doua numere naturale, separate printr-un singur spatiu liber, cu urmatoarea semnificatie: pentru C = 1 prima valoare este numarul maxim de copii care primesc cadouri iar a doua este numarul de bomboane din cutia pastrata; pentru C = 2 prima valoare este numarul maxim de bomboane primite de un copil iar a doua reprezinta numarul de bomboane din cutia pastrata.
Daca nu se pastreaza nicio cutie, in fisierul de iesire a doua valoare scrisa va fi 0 (atat in cazul cerintei 1 cat si in cazul cerintei 2).

Restrictii si precizari:

1. 2 <= N <= 100000.
2. Numerele de pe linia a treia sunt naturale, nenule, formate din cel mult 9 cifre.

Exemplul 1:

cadouri.in:
1
5
2 7 4 1 2

cadouri.out:
2 1

Explicatii:

Se rezolva cerinta 1.

Doi copii primesc cadouri. Cutia cu o bomboana nu este data niciunui copil.

Exemplul 2:

cadouri.in:
2
5
2 7 4 1 2

cadouri.out:
9 1

Explicatii:

Se rezolva cerinta 2.

Doi copii primesc cadouri, primul copil primeste cutiile cu 2 si 7 bomboane, iar al doilea copil primeste cutiile cu 4 si 2 bomboane. Deci primul copil primeste numar maxim de bomboane, 9. Cutia cu o bomboana nu este data nici unui copil.

Mai jos veti gasi metoda mea de rezolvare a problemei:

#include <fstream>

#define maximum_value INT_MAX
#define minimum_value INT_MIN

using namespace std;

ifstream fin("cadouri.in");
ofstream fout("cadouri.out");
int task, numberOfGifts, gifts[100000];

int min_element(int[], int);

int max_element(int[], int);

int main() {
    fin >> task >> numberOfGifts;
    int sums[numberOfGifts / 2 + 1], jump = 0;
    for (int i = 0; i < numberOfGifts; i++) {
       fin >> gifts[i];
    }
    switch (task) {
       case 1:
          fout << numberOfGifts / 2 << " " << (numberOfGifts % 2) ? min_element(gifts, numberOfGifts) : 0;
          break;
       case 2:
          
          switch (!(numberOfGifts % 2)) {
             case 1:
                for (int i = 0; i < numberOfGifts / 2; i++) {
                   sums[i] = gifts[i * 2 - 1] + gifts[i * 2];
                }
                fout << max_element(sums, numberOfGifts / 2) << " " << 0;
                break;
             case 0:
                for (int i = 0; i < numberOfGifts / 2; i++) {
                   if (gifts[i * 2 - 1] == min_element(gifts, numberOfGifts)) {
                      jump = 1;
                   }
                   sums[i] = gifts[i * 2 - 1 + jump] + gifts[i * 2 + jump];
                }
                fout << max_element(sums, numberOfGifts / 2) << " " << min_element(gifts, numberOfGifts);
                break;
             
             default:
                nullptr;
          }
          break;
       default:
          nullptr;
    }
    return 0;
}


int min_element(int array[], int n) {
    int min = maximum_value;
    for (int i = 0; i < n; i++) {
       if (array[i] < min) {
          min = array[i];
       }
    }
    return min;
}

int max_element(int array[], int n) {
    int max = minimum_value;
    for (int i = 0; i < n; i++) {
       if (array[i] > max) {
          max = array[i];
       }
    }
    return max;
}