Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
FR_08_20 - Lider w macierzy |
Def. Lider w zbiorze, to taka wartość, która występuje więcej razy niż połowa wszystkich jego elementów. Np. dla liczb 1, 1, 2, 1 liderem jest liczba 1, natomiast zbiór 1, 2, 2, 1, 3, 1 nie posiada lidera.
Wyobraźmy sobie macierz prostokątną n x m wypełnioną liczbami całkowitymi. Twoim zadaniem jest odpowiedzenie na pytanie, czy w podmacierzy kwadratowej o wymarach p x p znajduje się lider (0 < p ≤ min(n, m)).
Wejście
W pierwszym wierszu trzy liczby całkowite n, m i p, określające wymiary macierzy. Liczby n i m mieszczą się w przedziale [2..1000].
W kolejnych n wierszach po m liczb całkowitych. Każda mieści się w przedziale [1..1 000 000].
Następnie jedna liczba q określająca liczbę zapytań (nie więcej niż 105).
Każde zapytanie składa się z dwóch liczb x i y, wyznaczające współrzędne lewego górnego rogu podmacierzy (0 < x ≤ n - x, 0 < y ≤ m - y)
Wyjście
Dla każdego zapytania liczba, która jest liderem, jeśli lider istnieje w podmacierzy lub 0, gdy lidera nie ma.
Przykład
Wejście: 4 6 2 1 2 1 2 1 2 1 1 1 1 1 1 2 2 2 2 2 2 1 2 2 2 3 3 3 1 1 3 5 3 4 Wyjście: 1 0 2
Dodane przez: | Marcin Kasprowicz |
Data dodania: | 2017-11-27 |
Limit czasu wykonania programu: | 1s |
Limit długości kodu źródłowego | 50000B |
Limit pamięci: | 1536MB |
Cluster: | Cube (Intel G860) |
Języki programowania: | All except: ASM32-GCC COBOL D-CLANG D-DMD ELIXIR FANTOM GOSU GRV JS-MONKEY NIM OBJC OBJC-CLANG PICO RUST SCM qobi CHICKEN VB.NET |