Runda 8 [Hard] - Wypasione krowy

24.01.2011 - Damian Rusak
TrudnośćTrudność

 

Zadanie Tygodnia

Runda 8; kategoria Hard

Limit czasowy: 2s; Limit pamięciowy: 32MB


Wypasione krowy

W dalekiej krainie, w której mieszka farmer Andrzej właśnie skończyła się zima i czas wyprowadzić krowy na pastwisko. Andrzej posiada wiele cennych gatunków krów oraz dwa piękne pastwiska porośnięte nietypowymi rodzajami trawy.

Każda z krów należących do Andrzeja ma swoje własne preferencje co do chwili wypasu. Dla każdej z krów można określić dokładnie, w którym momencie może zostać wypasiona na pierwszym pastwisku i w którym można wyprowadzić ją na drugie z pastwisk. Preferencje te określa para liczb $ (a, b) $ oznaczająca, że jedynym momentem odpowiednim dla danej krowy na pierwszym pastwisku jest chwila $ a $, zaś na drugim chwila $ b $.

Andrzej ma swojego pomocnika, Ryszarda. On sam wyprowadza krowy na pierwsze pastwisko, Ryszard zaś na drugie. W danej chwili każdy z nich może zabrać na pastwisko dowolną liczbę krów, pod warunkiem, że każdej z nich ta chwila na tym pastwisku odpowiada (jak to było wspomniane powyżej). Ponieważ w gospodarstwie jest dużo pracy do wykonania, chcieliby aby łącznie było jak najmniej chwil w których muszą wychodzić z krowami. Znając preferencje krów, odpowiedz na pytanie, jaka jest najmniejsza liczba wyprowadzeń na wypas na obu pastwiskach, taka, aby każda z krów została wyprowadzona przynajmniej raz.

Wejście:

Pierwsza linia wejścia zawiera jedną liczbę $ n $ - liczbę krów, posiadanych przez Andrzeja. W kolejnych $ n $ liniach znajdują się pary liczb całkowitych $ (a_{i},b_{i}) $ - oznaczających, że $ i $-ta krowa może zostać wyprowadzona na pastwisko pierwsze w chwili $ a $ i na pastwisko drugie w chwili $ b $. ($ 1 \leq n \leq 1000, 0 \leq a,b \leq 100) $.

Wyjście:

Wyjście powinno zawierać jedną liczbę całkowitą $ k $ - najmniejszą liczbę wyjść na pastwisko, którą w sumie muszą poczynić Andrzej i Ryszard, aby każda z krów została wyprowadzona przynajmniej raz.

Przykład:

Wejście:

7
1 1
0 2
5 2
1 6
5 4
1 7
6 2

Wyjście:

3

Wyjaśnienie: Krowy o preferencjach $ (1,1) $, $ (1,6) $ i $ (1,7) $ można wyprowadzić na pierwsze pastwisko w chwili $ 1 $, krowy o preferencjach $ (0,2) $, $ (5,2) $ i $ (6,2) $ na drugie pastwisko w chwili 2, a krowę o preferencjach $ (5,4) $ na pierwsze pastwisko w chwili 5.

 

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
PozycjaImię i nazwiskoWynikCzasWypasione krowy
1Kamil Dębowski1004:17:2110
2Maciej Kisiel1005:27:3010
3Krzysztof Pszeniczny1005:43:3310
4Jakub Kołodziej1006:31:0710
5Maciej Urbanek1041:28:4710
6Piotr Bejda1081:57:1910
7Przemysław Derengowski10109:08:5010
8Adam Czapliński10124:43:4510
9Wojciech Staszkiewicz10274:31:3710
10Damian Straszak10611:25:0510
11Witold Długosz101370:35:0010
12Krzysztof Cirocki4128:40:314
13Krzysztof Katowicz Kowalewski156:18:091
14Bartek Dudek162:38:181
5
Twoja ocena: Brak Ocena: 5 (1 ocena)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com