Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

FR_09_12 - Kolumny mrówek

Kolumny mrówek

Jeśli myślicie, że mrówki poruszają się w chaotyczny sposób, nic bardziej mylnego. Na mrówczych drogach panuje ład i porządek. Nie ma tam zjawiska wyprzedzania. Jeśli szybsza mrówka napotka mrówkę wolniejszą, zwalnia i dotrzymuje jej kroku. W ten sposób powstają kolumny mrówek, poruszających się z jednakową prędkością. Dzięki temu mrówki poruszają się względnie szybko.

A teraz zadanie. Jest n pracowitych mrówek. Mrówki przemieszczają się po szlaku w jednym kierunku. Każda mrówka rozpoczyna w innym punkcie szlaku, ale niektóre mrówki poruszają się z różnymi prędkościami. Kiedy szybsza mrówka napotka mrówkę wolniejszą, zwalnia i dotrzymuje jej kroku, stając się częścią tej samej kolumny mrówek. Po pewnym czasie liczebność takich kolumn będzie niezmienna. No i to właśnie jest przedmiotem tego problemu. Ile kolumn mrówek powstanie?
Zakładamy, że jedna samotnie maszerująca mrówka to także kolumna.

Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita n (1 ≤ n ≤ 100 000) oznaczająca liczbę mrówek. Kolejne n wierszy zawiera początkową pozycję i prędkość pojedynczej mrówki. Pozycja jest nieujemną liczbą całkowitą, a prędkość to liczba całkowita dodatnia. Obie wartości nie przekraczają 109. Wszystkie mrówki rozpoczynają wędrówkę z innej pozycji, które są podane w porządku rosnącym na wejściu. Zakładamy, że szlak jest tak długi, że ho, ho.

Wyjście
Na wyjściu należy podać liczbę powstałych kolumn mrówek.

 

Przykład

Wejście
5
0 1
1 2
4 3
7 2
9 1

Wyjście
2


Dodane przez:Mariusz Śliwiński
Data dodania:2018-05-21
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
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

ukryj komentarze
2018-05-27 09:28:46
W sumie nieważne, okazuje się, że jednak wtedy mrówki liczone są jako 2 osobne kolumny
2018-05-27 08:56:58
Co jeśli 2 mrówki mają np. pozycje 2 i 3 oraz takie same prędkości? Liczone są wtedy jako ta sama kolumna?
2018-05-27 06:58:52 Mariusz ¦liwiñski
wejście:
5
0 2
1 3
2 4
3 5
4 6
wyjście: 5

wejście:
5
0 6
1 5
2 4
3 3
4 2
wyjście: 1
2018-05-26 22:15:58 Sebastian Toton
Czy mogę prosić o odpowiedź do testu:

5
0 6
1 5
2 4
3 3
4 2
2018-05-26 14:51:30 Mariusz ¦liwiñski
W kierunku rosnących wartości.

Ostatnio edytowany: 2018-05-26 22:05:47
2018-05-26 13:48:51 Maciej Boniecki
A w jakim kierunku poruszają się mrówki? W kierunku rosnących wartości pozycji czy malejących? Bo akurat dla testu przykładowego wynik jest taki sam niezależnie od kierunku :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.