Matrice4 De Pe Campion.edu.ro

[Courage]

Salut. Enunţul este aici: http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=953
 

Se dă o matrice cu n linii şi m coloane, conţinând numere naturale nenule. Asupra elementelor acestei matrice se fac următoarele transformări:
În prima rundă sunt eliminate toate numerele prime. În a doua rundă, dacă au mai rămas numere neeliminate, acestea sunt mărite cu 1, iar numerele prime nou-apărute sunt eliminate. Procedeul continuă până sunt eliminate toate numerele din matrice. Sunt declarate câştigătoare numerele prime eliminate în ultima rundă.

Cerinţă

Realizaţi un program care, pentru o matrice dată, afişează numarul de runde necesare, numărul numerelor declarate câstigătoare, precum şi numerele câştigătoare.

Date de intrare

Datele de intrare se citesc din fişierul matrice4.in care are următoarea structură:
n m - numărul de linii şi numărul de coloane ale matricei (0< n <=50)
a₁₁ a₁₂ ... a_1m - elementele matricei
a₂₁ a₂₂ ... a_2m
...
a_n1 a_n2 ... a_nm

Date de ieşire

În fişierul de ieşire matrice4.out veţi afişa pe prima linie numărul total de runde necesare şi numărul de numere declarate câştigătoare, iar pe linia a doua linie numerele câştigătoare, ordonate crescător:
r k
c₁ c₂ … c_k

Restricţii

• 2<=n, m<=50
• elementele matricei sunt numere naturale nenule <= 32767

Exemple

matrice4.in
3 5
122 41 32 81 99
20 54 77 23 1
80 14 74 4 7

matrice4.out
6 4 37 59 79 127

 

Ce am făcut eu arată cam aşa:

#include <iostream>
#include <cmath>
#include <vector>
#include <fstream>
#include <algorithm>

#define DIM 50

std::ifstream in("intrare.txt");
std::ofstream out("iesire.txt");

int este_prim(int numar)
{
    if (numar % 2 == 0 || numar < 3)
    {
        return (numar == 2);
    }

    int divizor, radical = (int) sqrt((double) numar);

    for (divizor = 3; divizor <= radical; divizor += 2)
    {
        if (numar % divizor == 0)
        {
            return 0;
        }
    }
    return 1;
}

int finish(int linii, int coloane, int matrice[DIM][DIM])
{
     for (int i = 0; i < linii; ++i)
     {
        for (int j=0; j < coloane; ++j)
        {
            if (matrice[i][j] != -1)
            {
                return 0;
            }
        }
     }
     return 1;
}

void rezolvare(int linii, int coloane,  int matrice[DIM][DIM], int &numar_runde, std::vector<int> &runde)
{
    runde.clear();
    numar_runde++;
    for (int i = 0; i < linii; ++i)
    {
        for (int j=0; j < coloane; ++j)
        {
            if (este_prim(matrice[i][j]))
            {
                runde.push_back(matrice[i][j]);
                matrice[i][j] = -1;
            }
            else
            {
                if (matrice[i][j] != -1)
                {
                    matrice[i][j]++;
                }
            }
        }
    }
    if (!finish(linii, coloane, matrice))
    {
        rezolvare(linii, coloane, matrice, numar_runde, runde);
    }
}

int main()
{
    int matrice[DIM][DIM] = {{0}}, linii, coloane, numar_runde = 0;

    std::vector<int> runde;

    in >> linii >> coloane;

    for (int i=0; i < linii; ++i)
    {
        for (int j = 0; j < coloane; ++j)
        {
            in >> matrice[i][j];
        }
    }

    rezolvare(linii, coloane, matrice, numar_runde, runde);

    std::sort(runde.begin(), runde.end());

    out << numar_runde << " " << runde.size() << 'n';

    for (std::vector<int>::iterator it = runde.begin(); it != runde.end(); ++it)
    {
        out << *it << " ";
    }

    return 0;
}

Se poate ceva mai simplu?