In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
Psst... Ruszyły zawody olimpiady informatycznej dla uczniów szkół podstawowych i średnich. Zadania na tych konkursach są bardzo podobne do zadań, które rozwiązujesz, tutaj, na Szkopule. Zobacz więcej:
- dla uczniów szkół podstawowych: oij.edu.pl/start/
- dla uczniów szkół średnich: oi.edu.pl/l/jak_zaczac/
Na każdym polu kartki w kratkę, składającej się z kwadratów jednostkowych, zapisano jedną liczbę całkowitą.
W tym zadaniu interesują nas prostokąty arytmetyczne położone na tej kartce,
czyli takie prostokąty złożone z kwadratów jednostkowych, że liczby w każdym wierszu i w każdej kolumnie tworzą ciągi arytmetyczne.
Przypomnijmy, że ciąg arytmetyczny to ciąg liczbowy, w którym każde dwa kolejne wyrazy różnią się o tę samą liczbę.
Na danej kartce w kratkę poszukujemy największego prostokąta arytmetycznego, tj. obejmującego najwięcej kwadratów jednostkowych.
Przykładowo, największy prostokąt arytmetyczny na poniższej kartce składa się z dziewięciu kwadratów jednostkowych:
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita ()
oznaczająca liczbę zestawów testowych opisanych w dalszej części wejścia.
Opis każdego zestawu rozpoczyna się od wiersza z dwiema liczbami całkowitymi i ().
W każdym z kolejnych wierszy znajduje się liczb całkowitych z zakresu od do .
Są to liczby wpisane w poszczególne kwadraty jednostkowe kartki w kratkę.
Rozmiar każdego pliku wejściowego będzie nie większy niż 20 MB.
Wyjście
Należy wypisać wierszy z odpowiedziami dla kolejnych zestawów testowych.
Odpowiedzią dla jednego zestawu jest jedna liczba całkowita równa liczbie kwadratów jednostkowych zawartych w największym
prostokącie arytmetycznym na kartce opisanej w danym zestawie.