W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Bajtockie tygrysy to niezwykłe zwierzęta, a ich nietypowe zwyczaje od zawsze fascynowały zoologów i matematyków. Ustalono niedawno, że dzielą się one na specyficzne gatunki. Tygrysa nazwiemy -tygrysem, jeśli spotkawszy tygrysa mniejszego co najmniej razy od siebie, zaatakuje go i zje, jednak nie odważy się tknąć żadnego większego tygrysa.
W bajtockim ZOO żyje tygrysów. Niestety miejsce w ZOO jest ograniczone, dlatego też dyrektor stwierdził, że trzeba tak przydzielić zwierzęta do wybiegów, aby zająć ich jak najmniej. Oczywiście nie można przy tym dopuścić, by jakikolwiek tygrys został pożarty. Dyrektor ma wyraźne problemy z zakwaterowaniem tygrysów, zwrócił się więc do Ciebie po pomoc.
Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą () - liczbę tygrysów w ZOO. Każdy z kolejnych wierszy zawiera opis jednego tygrysa. Opis taki składa się z dwóch liczb całkowitych oraz (, ), oddzielonych pojedynczym odstępem. Oznaczają one, że -ty tygrys jest -tygrysem i ma rozmiar .
Możesz założyć, że w przynajmniej przypadków testowych występują jedynie -tygrysy.
Twój program powinien wypisać na standardowe wyjście dokładnie jedną liczbę całkowitą - najmniejszą liczbę wybiegów, do których można bezpiecznie przydzielić tygrysy.
Dla danych wejściowych:
5 8 3 10 2 15 2 18 2 28 3
poprawną odpowiedzią jest:
2
Wyjaśnienie do przykładu: W powyższym przykładzie tygrysy o rozmiarach , , mogą występować na wybiegu number , zaś tygrysy o rozmiarach , mogą zostać pokazane na wybiegu numer .
Autor zadania: Michał Włodarczyk.