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

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

Problema Patinaj:

Clubul Sportiv SEPI are si o sectie de patinaj artistic. Conducerea clubului si-a propus sa participe la proba de perechi a urmatoarei olimpiade si are de luat unele decizii privind echipele pe care le poate inscrie.

Fiecare echipa participanta la olimpiada trebuie sa fie formata dintr-o pereche de patinatori (o fata si un baiat) si un antrenor. In plus, valorile membrilor unei echipe trebuie sa fie cat mai apropiate.

Valoarea unui sportiv si respectiv a unui antrenor este calculata pe baza rezultatelor obtinute la competitiile anterioare. Acestea sunt codificate sub forma unui singur numar cu cel mult 9 cifre.

Fiecare cifra a numarului reprezinta un rezultat anterior, iar suma cifrelor reprezinta valoarea sportivului, respectiv antrenorului.

De exemplu, numarul 18305 codifica rezultatele 1, 8, 3, 0, 5, obtinute la ultimele 5 concursuri, ceea ce corespunde valorii 17 (= 1 + 8 + 3 + 0 + 5).

La olimpiada fiecare sportiv si fiecare antrenor poate sa faca parte din cel mult o echipa inscrisa. In plus, pentru fiecare echipa, daca notam cu VM maximul dintre valorile antrenorului, fetei si baiatului si cu Vm minimul dintre valorile antrenorului, fetei si baiatului, inscrierea in concurs este permisa doar daca VM – Vm <= 1.

Cerinte:

Cunoscand numerele care codifica rezultatele antrenorilor, fetelor si baietilor, scrieti un program care sa determine:

1. Numarul maxim de echipe, NP , pe care le poate inscrie Clubul Sportiv SEPI la olimpiada astfel incat acestea sa respecte regulile de mai sus.
2. Valoarea maxima, V , a unui antrenor al clubului care poate antrena o pereche de patinatori (fata, baiat), ce poate fi inscrisa la olimpiada conform regulilor de mai sus si numarul de variante NV in care se poate alege o echipa care poate fi pregatita de un antrenor de valoare V.

Date de intrare:

Fisierul text patinaj.in contine:

1. pe prima linie numarul natural C care reprezinta numarul cerintei si poate avea una dintre valorile 1 sau 2;
2. pe cea de-a doua linie, un numar natural N, care reprezinta atat numarul antrenorilor angajati, cat si al fetelor si al baietilor legitimati la club;
3. pe fiecare dintre urmatoarele trei linii cate N valori, despartite prin cate un spatiu.

Pe cea de-a treia linie, acestea reprezinta codificarile rezultatelor anterioare ale celor N antrenori, pe cea de-a patra linie ele reprezinta codificarile rezultatelor anterioare ale celor N fete, iar valorile de pe cea de-a cincea linie reprezinta codificarile rezultatelor anterioare ale celor N baieti.

Date de iesire: 

In fisierul text patinaj.out se va afisa:

1. pentru cerinta 1: numarul maxim de echipe NP care pot fi ınscrise la olimpiada conform regulilor precizate mai sus;
2. pentru cerinta 2: doua numere naturale, V si NV , separate printr-un spatiu, reprezentand valoarea maxima a unui antrenor al clubului pentru care exista cel putin o pereche pe care o poate antrena si respectiv numarul variantelor ın care clubul poate alege o echipa care poate fi pregatita de un antrenor cu valoarea V , daca se rezolva cerinta 2.

In cazul ın care clubul nu poate ınscrie nicio pereche, se va afisa un singur numar: -1.

Restrictii si precizari:

1. 1 <= N <= 100000.
2. fiecare dintre numerele citite de pe a treia, a patra si a cincea linie e fisierului este un numar natural cu cel mult 9 cifre.

Exemplul 1:

patinaj.in:
1
4
8093 18305 20009 188
1803 3303331 909 91995
8017 20009 0 8017

patinaj.out:
2

Explicatii:

Se pot forma cel mult 2 echipe.
Prima ar putea fi formata din fata cu codificarea 1803 si baiatul cu codificarea 20009 si pregatita de antrenorul cu codificarea 20009. A doua poate fi formata din fata 3303331, baiatul 8017 si pregatita de antrenorul 18305.

Exemplul 2:

patinaj.in:
2
4
8093 18305 20009 188
1803 3303331 909 91995
8017 20009 0 8017

patinaj.out:
17 4

Explicatii:

Clubul are 4 antrenori cu valorile 20 = 8 + 0 + 9 + 3, 17 = 1 + 8 + 3 + 0 + 5, 11 = 2 + 0 + 0 + 0 + 9 si 17 = 1 + 8 + 8.
Valoarea maxima este 20, dar nu exista o pereche pe care sa o poata pregati antrenorul cu valoarea 20 conform regulilor impuse. In schimb, un antrenor cu valoarea 17 ar putea pregati o pereche inscrisa la olimpiada.
Sunt 4 variante de alegere a unei echipe pregatite de un antrenor cu valoarea 17.
Acestea ar putea avea in componenta fata 3303331 si unul dintre cei doi baieticu codificarea rezultatelor anterioare 8017.
O astfel de pereche ar putea fi pregatita de antrenorul 18305 sau de 188.

Mai jos veti gasi metoda mea de rezolvare a problemei:

#include <fstream>
#include <bits/stdc++.h>

using namespace std;

ifstream fin("patinaj.in");
ofstream fout("patinaj.out");
int task, numberOfEach, task2;

int getScore(int code) {
    int score = 0;
    while (code) {
       score += code % 10;
       code /= 10;
    }
    return score;
}

void bubbleSort(int arr[], int n)
{
    bool swapped;
    for (int i = 0; i < n - 1; i++) {
       swapped = false;
       for (int j = 0; j < n - i - 1; j++) {
          if (arr[j] > arr[j + 1]) {
             swap(arr[j], arr[j + 1]);
             swapped = true;
          }
       }
       if (!swapped)
          break;
    }
}

int max_element(int array[], int n) {
    int sorted[n];
    for (int i = 0; i < n; i++) {
       sorted[i] = array[i];
    }
    bubbleSort(reinterpret_cast<int (&)[]>(sorted), n);
    return sorted[n - 1];
}

int min_element(int array[], int n) {
    int sorted[n];
    for (int i = 0; i < n; i++) {
       sorted[i] = array[i];
    }
    bubbleSort(reinterpret_cast<int (&)[]>(sorted), n);
    return sorted[0];
}

int numberOfPairs(int Trainers[], int Girls[], int Boys[]) {
    int result = 0;
    for (int i = 0; i < numberOfEach; i++) {
       fin >> Trainers[i];
    }
    for (int i = 0; i < numberOfEach; i++) {
       fin >> Girls[i];
    }
    for (int i = 0; i < numberOfEach; i++) {
       fin >> Boys[i];
    }
    for (int trainer = 0; trainer < numberOfEach; trainer++) {
       for (int girl = 0; girl < numberOfEach; girl++) {
          for (int boy = 0; boy < numberOfEach; boy++) {
             int scores[3] = {getScore(Trainers[trainer]), getScore(Girls[girl]), getScore(Boys[boy])};
             if (max_element(scores, 3) - min_element(scores, 3) < 2) result++;
          }
       }
    }
    return result + 2;
}

int main() {
    fin >> task >> numberOfEach;
    int Trainers[numberOfEach], Girls[numberOfEach], Boys[numberOfEach], trainers_xp[numberOfEach],
       found = 0, max = 0;
    switch (task) {
       case 1:
          fout << numberOfPairs(Trainers, Girls, Boys);
          break;
       case 2:
          for (int i = 0; i < numberOfEach; i++) {
             fin >> Trainers[i];
          }
          for (int i = 0; i < numberOfEach; i++) {
             fin >> Boys[i];
          }
          for (int i = 0; i < numberOfEach; i++) {
             fin >> Girls[i];
          }
          for (int i = 0; i < numberOfEach; i++) {
             trainers_xp[i] = getScore(Trainers[i]);
          }
          bubbleSort(reinterpret_cast<int (&)[]>(trainers_xp), numberOfEach);
          
          for (int i = numberOfEach - 1; i > -1 && !found; i--) {
             for (int x = 0; x < numberOfEach; x++) {
                for (int y = 0; y < numberOfEach; y++) {
                   int possible_team[] = {trainers_xp[i], getScore(Girls[x]), getScore(Boys[y])};
                   if (::max_element(possible_team, 3) - ::min_element(possible_team, 3) < 2)
                      // I used :: to not be confused with max_element
                      // and min_element from stl_algo.h
                   {
                      found ++;
                      max = trainers_xp[i];
                   }
                }
             }
          }
          fout << max << ' ' << found;
       
       default: nullptr;
    }
    return 0;
}