Mistrzostwa Polski Szkół Średnich w Programowaniu Zespołowym 2024
Problem description
Jasio, nudząc się na lekcji matematyki, wymyślił następujące zadanie algorytmiczne.
“Dla danego zbioru liczb, ile co najmniej ciągów arytmetycznych o różnicy niemniejszej niż 10 jest potrzebnych, żeby każdy element zbioru występował w którymś z ciągów. Ciągi mogą być dowolnie długie.”
Niestety nie potrafi go rozwiązać. Napisz program, który rozwiąże zadanie Jasia.
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, określająca moc zbioru, który należy pokryć. W drugim wierszu wejścia znajduje się rosnący ciąg N liczb naturalnych Ai, pooddzielanych pojedynczymi odstępami. Są to elementy zbioru.
Wyjście
W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba naturalna – minimalna liczba ciągów arytmetycznych o różnicy co najmniej 10, które są potrzebne do pokrycia zbioru podanego na wejściu.
Możesz założyć, że dane są dobrane tak, że ta liczba nie przekracza 5.
Ograniczenia
1 ≤ N ≤ 500, 1 ≤ Ai ≤ 1 000 000.
Przykład
| Wejście |
|
| Wyjście |
|
| Wyjaśnienie |
W tym przykładzie możliwe jest pokrycie zbioru następującymi ciągami:
|