Simulare OJI 2024, ediția 2 · Clasa a IX-aMatrice (tablouri bidimensionale)Algoritmi avansați pe matrice
Problema Nefotografiat
După ultima sa experiență umilitoare la club în care a fost prins în flagrant dansând foarte ciudat pe melodiile sale preferate, Dani a decis că nu mai vrea să apară în nicio fotografie pe ringul de dans în viitor. N-ar fi fost problema dacă pozele erau făcute de prietenii săi sau de alți oameni necunoscuți, însă pozele în care apare Dani au fost realizate chiar de către fotografii angajați ai clubului și au fost distribuite pe rețelele de socializare, făcându-l astfel pe săracul băiat vedetă peste noapte.
După ce s-a jurat că nu mai calcă în niciun club în viața sa, Dani a fost totuși lăsat dus de ispită și a decis că merge astăzi cu prietenii pentru a-și recâștiga reputația. Pentru a rezolva problema sa legată de fotografiat, Dani se asigură că nicio persoană din jurul său nu este angajat al clubului.
Cu puțin alcool la bord (Dani este major) și în era sa de iubire intensă pentru matematică, flăcăul analizează foarte interesant ringul de dans al clubului. Acesta se poate reprezenta drept un dreptunghi de n × m metri, unde în fiecare metru pătrat se află câte o singură persoană. Pentru fiecare persoană, Dani a atribuit câte un număr natural, însă într-un mod un pic mai dubios: dacă persoana sigur nu este fotograf, atunci acesteia i se atribuie un număr compus (adică care nu este prim), altfel, un număr prim.
Dani știe cu siguranță că un fotograf aflat pe linia i, coloana j face fotografii capturând doar persoanele aflate pe direcțiile N, S, E, V față de punctul (i, j) din ringul de dans (adică, din matricea noastră, doar persoanele aflate fie pe linia i, fie pe coloana j, fie ambele — poziția fotografului). Cum persoanele din club nu se mișcă de pe o poziție pe alta, Dani trebuie să evite aceste locuri în care ar putea fi fotografiat, pentru a putea dansa în liniște și pace.
Cerință
Se dau numerele naturale n, m și valorile atribuite fiecărei poziții din club. Dani te roagă pe tine să găsești astfel numărul de poziții în care acesta ar putea să stea, știind cu certitudine că nu va fi fotografiat de către angajații clubului.
Date de intrare
Fișierul de intrare nefotografiat.in conține pe prima linie numerele naturale n și m separate printr-un spațiu. Pe următoarele n linii se află câte m valori naturale, separate prin spații, reprezentând numerele naturale atribuite de către Dani pentru fiecare persoană (și implicit poziție din club).
Date de ieșire
Fișierul de ieșire nefotografiat.out conține un singur număr natural, reprezentând numărul de poziții din matrice în care Dani știe cu siguranță că nu va fi fotografiat.
Restricții și precizări
1 ≤ n, m ≤ 10001 ≤ valorile atribuite de către Dani ≤ 1.000.000- Testele sunt progresiv mai grele, astfel soluții mai ineficiente pot obține punctaj parțial
- Dani este major
Exemplu
3 4 14 18 14 10 26 13 44 17 27 30 55 23
2
Explicația exemplului
Numerele prime din matrice sunt 13, 17, 23. Astfel, toate elementele de pe liniile 2 și 3 și/sau coloanele 2 și 4 devin automat neferite de blițul aspru al fotografilor, deci Dani nu poate să se afle pe aceste poziții. Singurele 2 locații în care Dani poate să rămână sunt (1, 1) și (1, 3) (cele două valori de 14).
Problemă adăugată pe InfoAs de 
cout << "Suma este " << s;