Buonasera, ho un problema, wrong output nell’ultimo testcase (021).
Il ragionamento mi sembra immediato, trovo il minimo valore per rendere una riga/colonna piena di numeri primi.
(procedendo come nel mio codice la differenza tra ogni valore della matrice e il primo superiore viene calcolata 2 volte, una per la riga e una per la colonna, ma siccome sarei comunque rientrato nei limiti di tempo non ci ho dato peso)
#include <bits/stdc++.h>
using namespace std;
int h, w, mat[500][500];
bool primo[100001];
void crivello(){
for (int i=0; i<100001; i++) primo[i] = 1;
primo[0] = primo[1] = 0;
for (int i=2; i*i<100001; i++){
if (primo[i]){
for (int j=i*i; j<100001; j+=i)
primo[j] = 0;
}
}
return;
}
int riga(int i){
int sum = 0;
for (int j=0; j<w; j++){
int tmp = mat[i][j];
while(!primo[tmp]){
if (tmp == 100000) return INT_MAX;
sum++, tmp++;
}
}
return sum;
}
int colonna(int j){
int sum = 0;
for (int i=0; i<h; i++){
int tmp = mat[i][j];
while(!primo[tmp]){
if (tmp == 100000) return INT_MAX;
sum++, tmp++;
}
}
return sum;
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
ios_base::sync_with_stdio(0);
crivello();
cin >> h >> w;
for (int i=0; i<h; i++)
for (int j=0; j<w; j++)
cin >> mat[i][j];
int res = INT_MAX;
for (int i=0; i<h; i++)
res = min(res, riga(i));
for (int j=0; j<w; j++)
res = min(res, colonna(j));
cout << res;
return 0;
}
