Matura 2017 (maj). Zadanie 1. Prostokąt

Dane są:

liczba całkowita n większa od 1
zbiór A zawierający n dodatnich, różnych liczb całkowitych
liczba pierwsza p

Zadanie 1.

Dla danych z każdego wiersza w tabeli oblicz największe pole powierzchni prostokąta, które nie jest podzielne przez p, a długości sąsiednich boków tego prostokąta są różne (nie może on być kwadratem) i należą do zbioru A. Zapisz pole tego prostokąta w kolumnie S. Jeżeli taki prostokąt nie istnieje, jako wynik podaj liczbę 0 (zero).

Zbiór A	p	S – pole szukanego prostokąta lub 0 (zero), jeśli nie można zbudować takiego prostokąta
7, 5, 11, 33	3	77
15, 12, 10, 6, 5, 1	5	72 (6*12)
6, 28, 7, 12, 10, 14, 5, 9, 4, 8, 18	7	216 (18*12)
4, 34, 16, 8, 6, 22, 14, 12, 2, 7	2	0

Rozwiązanie:

Krok 1. 

Szukając największe pole powierzchni prostokąta, które nie jest podzielne przez p rozpocząć należy od odrzucenia liczb podzielnych przez liczbę p.

15, 12, 10, 6, 5, 1
6, 28, 7, 12, 10, 14, 5, 9, 4, 8, 18
4, 34, 16, 8, 6, 22, 14, 12, 2, 7

Krok 2.

Wybieramy dwie największe liczby spośród pozostałych, wykonujemy iloczyn, wynik sprawdzamy czy nie est podzielny przez p.

12*6=72
18*12=216
7*—– brak drugiej liczby

Zadanie 2. 

Zapisz (w postaci pseudokodu, listy kroków lub w wybranym języku programowania) algorytm obliczający największe pole powierzchni prostokąta, które nie jest podzielne przez p, a długości sąsiednich boków tego prostokąta należą do zbioru A i są różne.
Przy ocenie brana będzie pod uwagę złożoność obliczeniowa Twojego algorytmu.

Uwaga:
W zapisie algorytmu możesz wykorzystywać tylko następujące operacje arytmetyczne: dodawanie, odejmowanie, mnożenie, dzielenie całkowite i obliczanie reszty z dzielenia.

Specyfikacja:

Dane:

n – liczba całkowita większa od 1
A[1..n] – tablica zawierająca n różnych, dodatnich liczb całkowitych
p – liczba pierwsza

Wynik:

S – największe pole powierzchni prostokąta, które nie jest podzielne przez p,
a długości sąsiednich boków tego prostokąta są różne i zawarte w tablicy A;
jeśli nie można zbudować takiego prostokąta, wynikiem powinno być 0 (zero)

Rozwiązanie:

#include <iostream>
#define N 11
#define P 7

using namespace std;

int main()
{
    int tab[N]={6, 28, 7, 12, 10, 14, 5, 9, 4, 8, 18};
    int x=0,y=0;
    for (int i=0; i<N; i++) {
        if (tab[i]%P!=0) {
            if (tab[i] > x ) x = tab[i];
        }
    }
    for (int i=0; i<N; i++) {
        if (tab[i]%P!=0) {
            if (tab[i] > y && tab[i] < x ) y = tab[i];
        }
    }
    if (x*y>0)
        cout << "Pole prostokata = " << x << " * " << y << " = " << x*y << endl;
    else
        cout << "Wynik = 0 " << endl;
    return 0;
}