Question

Cerința
Pentru traversarea unui râu se folosește un pod, alcătuit din n*m sectoare, dispuse pe n linii și m coloane. Datorită vechimii, fiecare sector al podului are un factor de siguranță cunoscut, exprimat printr-un număr natural, care scade cu o unitate de fiecare dată când o persoană pășește pe acel sector. Sectoarele cu factorul de siguranță nul nu sunt accesibile.

Traversarea podului constă în parcurgerea unei anumite coloane de la prima linie spre ultima. Nu este posibilă, din motive de siguranță, schimbarea coloanei în timpul traversării.

Administratorul podului, Gigel, vă cere să determinați numărul de persoane care vor putea traversa podul până la degradarea lui totală, pentru a argumenta cererea de finanțare pentru refacerea acestuia.

Date de intrare
Programul citește de la tastatură numerele n m, iar apoi n șiruri cu câte m numere naturale, care descriu podul.

Date de ieșire
Programul va afișa pe ecran numărul C, reprezentând valoarea cerută.

Restricții și precizări
1 ≤ n, m ≤ 1000
pentru fiecare sector, factorul de siguranță este cel mult 10000

Exemplu
Intrare

4 5
5 3 6 2 1
4 4 0 4 3
6 2 2 3 4
3 4 4 5 1
Ieșire

8

Answer 1

N-ai ce face, daca se spune in conditie ca deodata ce intri o coloana nu mai poti iesi.
Daca pe o coloana este 0, atunci nu mai are sens sa mearga pe aceasta. Daca pe o coloana este 1, atunci doar un om ar putea merge, pentru ca dupa ce va merge, aceasta va fi transformata in 0.
Deci la caz general, pe o coloana trebuie gasit n_min, astfel ca pe acea coloana vor putea merge n_min persoane.

#include <iostream>

using namespace std;

int n,m,a[1001][1001],nr;

int main()
{

    cin >> n >> m;
    for(int i=1;i<=n;i++)    
        for(int j=1;j<=m;j++)        
            cin >> a[i][j];         

    for(int i=1;i<=m;i++)
    {
        int min=10001;
        for(int j=1;j<=n;j++)    
                if(a[j][i]<min)        
                        min=a[j][i];
        nr+=min;
    }

    cout << nr;

    return 0;

}

Complexitatea este O(n*m) si intra in intervalul de 1.5 secunde, ne mai spunand de limita de memorie.