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

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

Problema Forus:

La ora de educatie tehnologica a clasei a V-a profesorul Forus, pasionat de matematica, a adus pentru fiecare dintre cei N elevi cate un carton pe care este scris cate un numar natural nenul. Fiecare elev poate folosi cartonul asa cum l-a primit sau poate sa taie o singura data cartonul intre doua cifre si sa lipeasca partea stanga la finalul partii drepte. Elevul NU are voie sa faca o taietura in fata cifrei 0, deci niciunul dintre numerele obtinute NU poate sa inceap cu cifra 0. Dintre toate numerele pe care le poate obtine, elevul il alege pe cel care are numar minim de divizori, iar daca poate obtine mai multe astfel de numere, l alege pe cel mai mic dintre ele. La sfarsitul orei, profesorul strange cartoanele cu numerele alese, in ordinea distribuirii lor.

De exemplu, daca initial elevul primeste cartonul cu numarul 25082 atunci el are doar urmatoarele trei variante de taiere si lipire:

Cerinte:

Scrieti un program care citeste numarul natural N si cele N numere scrise pe cartoanele aduse de profesorul Forus, apoi rezolva urmatoarele doua cerinte:

1. determina numarul de cartoane pe care elevii au voie sa le taie de oriunde (NU contin cifre in fata carora NU au voie sa taie);
2. determina, ın ordinea strangerii cartoanelor, numerele preluate de catre profesorul Forus la finalul orei.

Date de intrare:

Fisierul de intrare forus.in contine pe prima linie un numar natural C reprezentand cerinta din problema care trebuie rezolvata (1 sau 2). A doua linie din fisier contine un numar natural N, reprezentand numarul de elevi, iar a treia linie din fisier contine N numere naturale, separate prin cate un spatiu, reprezentand numerele scrise pe cartoanele aduse de profesor, ın ordinea distribuirii lor.

Date de iesire: 

Daca C = 1, fisierul de iesire forus.out contine pe prima linie un numar natural reprezentand raspunsul la cerinta 1.
Daca C = 2, fisierul de iesire forus.out contine pe prima linie N numere naturale, separate prin cate un spatiu, reprezentand raspunsul la cerinta 2; numerele sunt scrise in ordinea in care au fost stranse.

Restrictii si precizari:

1. 2 <= N <= 30.
2. 1 <= numarul natural de pe carton $ 1000000000.
3. Pentru rezolvarea corecta a cerintei 1 se acorda 20 de puncte; pentru rezolvarea corecta a cerintei 2 se acorda 70 de puncte. Se acorda 10 puncte din oficiu.

Exemplul 1:

forus.in:
1
3
1234 25082 543 52 150

forus.out:
15 2341 25082 453 501

Explicatii:

Cerinta este 1.

Sunt 3 numere care pot fi taiate de oriunde: 1234, 543, 52.

Exemplul 2:

forus.in:
2
5
51 1234 50822 345 150

forus.out:
47

Explicatii:

Cerinta este 2.

Pentru cartonul cu numarul 51 se pot obtine numerele 15 si 51. Ambele numere au cate 4 divizori. Astfel, se va alege numarul 15, fiind cel mai mic.
Pentru cartonul cu numarul 1234 (4 divizori) pot fi obtinute numerele: 2341 (2 divizori), 3412 (6 divizori) si 4123 (8 divizori). Se va alege numarul 2341 pentru ca are numarul minim de divizori. Analog se va proceda pentru toate celelalte numere din sir.

Mai jos veti gasi metoda mea de rezolvare a problemei:

#include <fstream>
#include <math.h>
using namespace std;

ifstream fin("forus.in");
ofstream fout("forus.out");
int task, numberonumbers, number;

bool contains0(int number) {
    while (number) {
       if (number % 10 == 0) return true;
       number /= 10;
    }
    return false;
}

int numberOfDigits(int number) {
    int k = 0;
    while (number) {
       k++;
       number /= 10;
    }
    return k;
}

int remakeNumber(int number) {
    int posibilities[numberOfDigits(number)+1], numberonumbers = 0, minimumDivisors = INT_MAX, minimumDivisorsIndex =
          -1;
    for (int i = 1; i < numberOfDigits(number) - 1; i++) {
       int first = number, second;
       second = first % (int) pow(10, i);
       first /= pow(10, i);
       if (numberOfDigits(second) != i) continue;
       second *= pow(10, i);
       second += first;
       posibilities[i-1] = second;
       numberonumbers++;
    }
    for (int i = 0; i < numberonumbers; i++) {
       int posibility = posibilities[i];
       int divs = 2;
       for (int i = 2; i < posibility/2; i++) {
          if (posibility % i == 0) divs++;
       }
       if (divs < minimumDivisors) {
          minimumDivisors = divs;
          minimumDivisorsIndex = i;
       }
    }
    return posibilities[minimumDivisorsIndex];
}

int main() {
    fin >> task >> numberonumbers;
    if (task == 1) {
       int k;
       for (int i = 0; i < numberonumbers; i++) {
          fin >> number;
          if (!contains0(number)) k++;
       }
       fout << k;
    } else if (task == 2) {
       for (int i = 0; i < numberonumbers; i++) {
          fin >> number;
          fout << remakeNumber(number) << " ";
       }
    }
    return 0;
}

Sper sa va fie de folos. 😉

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