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

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

Problema Tai:

Un numar este prim daca are exact doi divizori naturali. Prin taierea unui numar in p parti intelegem impartirea acestuia in p numere, fiecare de cel putin o cifra, astfel incat prin alipirea numerelor obtinute de la stanga la dreapta obtinem numarul initial.
De exemplu, daca impartim numarul 12045 in doua parti avem patru variante de taiere obtinandu-se numerele: 1 si 2045; 12 si 045; 120 si 45; 1204 si 5. Daca il impartim in trei parti avem sase variante de taiere obtinandu-se numerele 1, 2 si 045; 1, 20 si 45; 1, 204 si 5; 12, 0 si 45; 12, 04 si 5; 120, 4 si 5.

Cerinte:

Se considera un sir format din N numere naturale.

1. Determinati cel mai mare numar prim din sirul celor N numere.
2. Determinati cel mai mare numar prim dintre cele obtinute prin taierea in doua parti a fiecarui numar din sirul celor N.
3. Determinati cel mai mare numar prim dintre cele obtinute prin taierea in trei parti a fiecarui numar din sirul celor N.

Date de intrare:

Pe prima linie a fisierului tai.in se gaseste numarul C care poate avea doar valorile 1, 2 sau 3 si reprezinta cerinta care urmeaza a fi rezolvata. Pe a doua linie se gaseste N, cu semnificatia din enunt, iar pe a treia linie se gaseste sirul celor N numere naturale despartite prin cate un spatiu.

Date de iesire: 

In fisierul de iesire tai.out pe prima linie se va afisa un numar natural reprezentand raspunsul la cerinta specificata.

Restrictii si precizari:

1. 1 <= N <= 100
2. 0 <= orice numar din sir & 1 000 000 000
3. Pentru cerintele 2 si 3 se garanteaza ca pentru toate numerele din sir se poate efectua taierea
4. Pentru cerinta 1 daca sirul nu contine numere prime se va afisa 0
5. Pentru cerintele 2 si 3 daca in urma taierilor nu se obtine niciun numar prim, se va afisa 0
6. Pentru rezolvarea fiecarei cerinte se obtin 30 de puncte.

Exemplul 1:

tai.in:
1
5
2 13 21 17 1

tai.out:
17

Explicatii:

Numere prime din sir sunt 2, 13 si 17, iar maximul este 17.

Exemplul 2:

tai.in:
2
3
23 196 27

tai.out:
19

Explicatii:

Din 23 se obtin doua numere 2 si 3, din 196 se pot obtine numerele 1 si 96 sau 19 si 6, iar din 27 se obtin numerele 2 si 7.
Cel mai mare numar prim care se poate obtine este 19.

Exemplul 3:

tai.in:
3
3
1234 17119 5678

tai.out:
71

Explicatii:

Din numarul 1234 se pot obtine numerele: 1, 2, 34 sau 1, 23, 4 sau 12, 3, 4.
Din numarul 17119 se pot obtine numerele: 1, 7 si 119 sau 1, 71 si 19 sau 1, 711 si 9 sau 17, 1 si 19 sau 17, 11 si 9.
Din numarul 5678 se pot obtine numerele: 5, 6 si 78 sau 5, 67 si 8 sau 56, 7 si 8.
Cel mai mare numar prim care se poate obtine este 71.

Mai jos veti gasi metoda mea de rezolvare a problemei:

#include <fstream>

using namespace std;

ifstream fin("tai.in");
ofstream fout("tai.out");
unsigned int task, numberonumbers, task1 = 0, task2 = 0, task3 = 0, n;

bool isPrime(int number)
   for (int d = 2; d <= number / 2; d++) {
      if (number % d == 0) return false;
   }
   return true;
}

inline int pow(short x, short y) {
   int p = 1;
   for (int i = 0; i < y; i++)
      p *= x;
   return p;
}

inline int lastNDigits(int n, int number) {
   return number % pow(10, n);
}

inline short numberODigits(int number) {
   short result = 0;
   while (number) {
      number /= 10;
      result++;
   }
}

int main() {
   fin >> task >> numberonumbers;
   if (task == 1) {
      for (int i = 0; i < numberonumbers; i++) {
         fin >> n;
         if (n > task1 && isPrime(n)) task1 = n;
      }
      fout << task1;
   } else if (task == 2) {
      for (int i = 0; i < numberonumbers; i++) {
         fin >> n;
         for (int x = 1; x < numberODigits(n) - 1; x++) {
            int first, second = lastNDigits(x, n);
            first = n;
            first /= pow(10, x);
            if (first > task2 && isPrime(first)) task2 = first;
            if (second > task2 && isPrime(second)) task2 = second;
         }
      }
      fout << task2;
   } else {
      for (int i = 0; i < numberonumbers; i++) {
         fin >> n;
         for (int x = 1; x <= numberODigits(n); x++) {
            for (int y = 1; y <= numberODigits(n) - x; y++) {
               int first, second, third = lastNDigits(y, n);
               n /= pow(10, y);
               second = lastNDigits(x, n);
               n /= pow(10, x);
               first = n;
               fout << "*** " << first << " " << second << " " << third << endl;
               if (first > task3 && isPrime(first)) task3 = first;
               if (second > task3 && isPrime(second)) task3 = second;
               if (third > task3 && isPrime(third)) task3 = third;
            }
         }
      }
      fout << task3;
   }
   fin.close();
   fout.close();
   return 0;
}

Sper sa va fie de folos. 😉

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