Runda 11 [Basic] - Ciastka

14.02.2011 - Damian Rusak
Trudność

 

Zadanie Tygodnia

Runda 11; kategoria Basic

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


Ciastka

Mały Jasio ma brata Stasia. Obaj z wielką pasją zajmują się spożywaniem ciastek, z tym, że Jasio je tylko i wyłącznie ciasta z galaretką, podczas gdy Stasio takich ciastek nie tyka i woli okazy bez galaretki. Bracia ustalili między sobą sprytny i słuszny system - gdy otrzymują razem pewną porcję ciastek, dzielą się dokładnie wedle swoich upodobań - Jasio otrzymuje ciastka z galaretką, podczas gdy Stasio otrzymuje całą resztę.

Mama planuje wyprawić wielką uroczystość rodzinną i z tej okazji przygotować wiele ciastek dla dzieci i gości. Przygotowała sobie plan pieczenia, a w nim listę rodzajów ciastek, które zamierza przyrządzić. Nie wie jednak, które z ciastek przyozdobić galaretką. Aby ciastka nie wyglądały zbyt podobnie (Mamie zależy na różnorodności na stole) ustaliła, że pewne pary ciastek muszą się od siebie różnić obecnością galaretki - któreś z nich (ale dokładnie jedno!) musi być pokryte galaretką. Zatem niedopuszczalne są sytuacje, w których oba są pokryte galaretką, bądź oba są nią niepokryte.

Znając te zależności, odpowiedz na pytanie- ile ciastek spośród przygotowanych mógłby zjeść Jaś, a ile Staś? Zakładamy, że Mama zawsze stara się udekorować galaretką jak najwięcej ciastek.

Wejście:

Pierwsza linia wejścia zawiera dwie liczby całkowite $ n $ oraz $ m $ - kolejno liczbę ciastek oraz liczbę zależności pomiędzy nimi ($ 1 \leq n,m \leq 10^{6} $). W kolejnych $ m $ liniach znajdują się pary liczb całkowitych $ a $ $ b $ - oznaczające, że ciastka o owych numerach muszą różnić się obecnością galaretki. Ciastka numerowane są od $ 1 $ do $ n $. Możesz założyć, że dane będą tak dobrane, że zawsze możliwe będzie bezkonfliktowe przydzielenie galaretki do ciastek.

Wyjście:

Jedyna linia wejścia powinna zawierać dwie liczby - kolejno liczbę ciastek, które zjeść może Jaś i liczbę ciastek, które zjeść może Staś.

Przykład:

Wejście:

6 4
1 2
3 5
4 5
6 5

Wyjście:

4 2

Maksymalny wynik dla ciastek z galaretką uzyskamy, gdy Mama przyozdobi nią na przykład ciastka o numerach 1,3,4,6

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
PozycjaImię i nazwiskoWynikCzasCiastka
1Marcin Karpinski1004:46:5910
2Michał Zezyk1010:07:2210
3Mieszko Kamyczek1018:03:1310
4Aleksander Matusiak1022:58:2810
5Arek Wróbel1027:12:1210
6Piotr Bejda1030:46:2910
7Łukasz Hryniuk1057:12:5310
8Bartek Dudek10146:28:5810
9Przemysław Derengowski10171:00:4810
10Kamil Dębowski10171:47:4010
11Mateusz Wasylkiewicz10174:18:2010
12Andrzej Rumiński10175:31:1010
13Wojciech Dyżewski10435:59:2110
14Michał Majewski10562:52:2910
15Wojciech Szałapski10750:20:2410
16Witold Długosz10937:31:2910
17Damian Straszak895:03:468
18Maciej Foks678:57:176
19Aleksandra Hernik6124:14:246
20Krzysztof Kiljan2299:45:232
21Norbert Gregorek108:41:541
22Mateusz Witkowski123:11:131
23Krzysztof Drab1172:16:561
24Piotr Gawryluk1609:50:121
25Tymon Czarnota1968:21:141
26Artur Lazoryk11234:50:081
5
Twoja ocena: Brak Ocena: 5 (3 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com