Gigel a găsit o matrice cu n linii și m coloane și elemente numere naturale. El își propune să determine, pentru fiecare linie, cea mai mică valoare care se poate obține adunând elementele de pe linie, cu excepția unuia. Do that with a[100][100]

Problema pe care o propune Gigel este cunoscută sub numele de "Excluderea minimă a unui element dintr-o sumă". Acesta este un exemplu clasic de problemă din domeniul programării dinamică.

Aici este o soluție în C++:

```cpp
#include <iostream>
#include <vector>
#include <algorithm>

// Functie pentru a calcula suma minimă a unui vector
int sumaMinima(const std::vector<int>& v, int indexExclus) {
    int suma = 0;
    for (int i = 0; i < v.size(); i++) {
        if (i != indexExclus) {
            suma += v[i];
        }
    }
    return suma;
}

// Functie pentru a rezolva problema
void rezolvaProblem(int n, int m, std::vector<std::vector<int>>& a) {
    for (int i = 0; i < n; i++) {
        int minSuma = INT_MAX;
        for (int j = 0; j < m; j++) {
            int suma = sumaMinima(a[i], j);
            minSuma = std::min(minSuma, suma);
        }
        std::cout << "Linia " << i + 1 << ": " << minSuma << std::endl;
    }
}

int main() {
    int n = 100;
    int m = 100;
    std::vector<std::vector<int>> a(n, std::vector<int>(m));

    // Inlocuim valorile din matrice cu numere naturale aleatoare
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            a[i][j] = rand() % 100 + 1;
        }
    }

    rezolvaProblem(n, m, a);

    return 0;
}
```

Această soluție folosește o abordare dinamică pentru a rezolva problema. Pentru fiecare linie a matricei, se calculează suma minimă a elementelor de pe linie, cu excepția unuia. Aceasta se face prin a compara suma tuturor elementelor de pe linie, cu suma tuturor elementelor de pe linie, cu excepția celui de pe pozitia j.

Este important de menționat că această soluție are o complexitate de O(n \* m^2), unde n este numărul de linii și m este numărul de coloane. Aceasta se datorează faptului că pentru fiecare linie, se calculează suma minimă a elementelor de pe linie, cu excepția unuia, ceea ce implică o iterare a tuturor elementelor de pe linie.