Zadania - Dwa markety

Question

Witam. Dopiero zaczynam swoją przygodę z programowaniem. Dostałam poniższe zadanie do rozwiązania i nie mam żadnego pomysłu jak się za nie zabrać. Proszę o jakieś wskazówki.

Zadanie:

Chcesz zrobić zakupy. Wiesz dokładnie, jakie produkty chcesz kupić. Sprawdziłeś już w Internecie ceny każdego z produktów we wszystkich okolicznych marketach. Masz czas pojechać do co najwyżej dwóch marketów i łącznie chcesz w nich kupić po jednym egzemplarzu każdego produktu. Jak to zrobić najtaniej?

Wejście

Pierwszy wiersz wejścia zawiera dwie liczby całkowite n oraz m (2≤n, m≤100) oddzielone spacją, oznaczające liczbę marketów oraz liczbę produktów, które chcesz kupić. Każdy z kolejnych n wierszy zawiera po m liczb całkowitych z zakresu od 1 do 1000. Pierwszy wiersz zawiera ceny kolejnych produktów w pierwszym markecie, drugi – ceny kolejnych produktów w drugim markecie itd.

Wyjście

Twój program powinien wypisać jedną liczbę całkowitą: minimalny koszt zakupu wszystkich potrzebnych produktów w co najwyżej dwóch marketach.

Przykład

Dla danych wejściowych:

3 4

7 3 7 9

2 20 10 6

8 8 8 8

poprawnym wynikiem jest:

18

Wyjaśnienie do przykładu:

Najlepiej pojechać do pierwszego i drugiego marketu. W pierwszym kupujemy drugi i trzeci produkt (koszt 3 + 7), a w drugim pierwszy i czwarty (koszt 2 + 6).

Answer 1

W związku z tym, że limity są baardzo małe poprawne będzie rozwiązanie brutalne (brute force), czyli sprawdzenie wszystkich możliwości. Będziemy sprawdzać każdą parę sklepów i porównywać z najlepszym wynikiem dotychczasowych par. Sprawdzanie pary sklepow, to przegladanie cen kazdego produktu w tych dwoch sklepach i branie zawsze tanszego.
Mała podpowiedź w C++ co do najtrudniejszej części kodu, czyli jak napisać fory, które przejrzą pary
(mając na uwadze, że para (a, b), to to samo co (b, a), oraz, że nie możemy porównać sklepu samego ze sobą)
 

int tab[101][101]; // tab[nr_sklepu][cena_itego_produktu]

for ( int i = 0; i < 101; ++i )
 for ( int j = i  + 1; j < 101; ++j )
{
  // porownanie i-tego i j-tego sklepu ze soba
}