Runda 0 [Basic] - Skarpety

15.11.2010 - Damian Rusak
Trudność

 

 

Zadanie tygodnia

Runda 0; kategoria Basic

Limit czasowy: 1s; Limit pamięciowy: 64MB


Skarpety

Detektyw Hercules rzucił wyzwanie potężnej mafii. Podstępem i pod osłoną nocy dostał się do kwatery mafijnych bossów. Został jednak wyczuty przez psy strzegące rezydencji i musiał salwować się ucieczką. Udało mu się porwać ze sobą jedynie szufladę ze skarpetami. 

Hercules podejrzewa, że bossowie są na tyle zajęci swoją przestępczą działalnością, że z roztargnienia wszyscy korzystają z tej samej szuflady na skarpety (tej, którą uniósł w ucieczce detektyw!). Z pewnością więc skarpety są już dawno nie do pary i pomieszane. Hercules zastanawia się, ilu co najwyżej mafijnych bossów mogło zamieszkiwać rezydencję. Wie na pewno, że każdy z nich rano zakłada parę skarpet z szuflady. Każda skarpeta ma na sobie naniesiony zakres rozmiarów stóp, na jakie pasuje. Zatem skarpeta o rozmiarze 10-14 może być założona przez osobę, która ma rozmiar stóp od 10 do 14. Każdy boss z pewnością zakłada dwie skarpety, które dopuszczają jego rozmiar stóp, lecz nie muszą być one takie same (a więc boss o rozmiarze stopy 30 może na przykład założyć dwie skarpety o rozmiarach odpowiednio 14-40 i 30- 32).

Oczywiście jedna skarpeta może być założona tylko przez jednego bossa i każdy boss musi założyć dokładnie dwie skarpety.

Wejście:

Pierwsza linia wejścia zawiera jedną liczbę $ n $ ($ 1 \leq n \leq 10^{5} $) - liczbę pojedynczych skarpet z szuflady. W kolejnych $ n $ liniach znajdują się dwie liczby całkowite $ a $ i $ b $ ($ 0 \leq a \leq b \leq 10^{9} $), oznaczające, że dana skarpeta pasuje na stopę rozmiarów od $ a $ do $ b $ włącznie.

Wyjście:

Jedyna linia wyjścia powinna zawierać jedną liczbę całkowitą - największą liczbę bossów mafijnych, którzy mogliby założyć o poranku skarpety z szuflady.

Przykład 1:

Wejście:

5
2 5
0 1
4 7
2 3
0 7

Wyjście:

2

Jeden boss o rozmiarze stóp 2 mógłby założyć skarpety 2-5 i 2-3, a drugi o rozmiarze stóp 6 mógłby założyć skarpety 4-7 i 0-7.

 

 

 

PozycjaImię i nazwiskoWynikCzas
1Przemek Komosa1017:24:59
2Adam Czapliński10149:52:45
3Witold Długosz102657:22:57
4Przemysław Derengowski9185:43:02
5Tomasz Richert838:15:58
6Karol L82312:52:02
7Łukasz Hryniuk42139:52:35
8Marcin Skiba325:26:21
9Paweł Michalak31161:01:57
10Kamil Dębowski32670:52:03
11Jakub Sygnowski208:35:07
12Michał Robaszyński259:52:32
13Wojciech Janczewski2109:05:32
14Michał Kownacki2347:10:33
15Kamil Wawrzyczek2364:49:40
16Paweł Nowak2374:28:43
17Tomasz Gieniusz2449:02:41
18Krzysztof Cirocki23012:26:55
19Dariusz Michalski188:16:33
20Mateusz Piecuch1132:47:18
Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
0
Twoja ocena: Brak

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com