POLSKI SPOJ

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.

Zadanie w systemie SPOJ (srednie)

8736. Arka Noego

Kod zadania: NOE

Cofnąłeś się w czasie do czasów Noego używając najnowszego wehikułu czasu (był drogi, ale raz się żyje!).

Udało Ci się zdążyć w sam raz przed potopem. Gdy podszedłeś do Noego spytać o to i owo, okazało się, że nie ma dla Ciebie czasu, bo musi wpuścić wszystkie zwierzęta na pokład. W związku z nadchodzącym kataklizmem zwierzęta ogarnęła panika i wszystkie się wymieszały. Noe zaznacza je na liście (przypisując numery od 1 do n) wpuszczając pojedynczo na arkę. Otrzymawszy kompletną listę, Noe zorientował się, że jednego zwierzęcia brakuje! Niestety zwierząt jest tak dużo, że nie jest on z stanie sprawdzić, którego.

Jako życzliwy człowiek (wierzący czy nie) zaoferowałeś swoją pomoc. W podróż zaopatrzyłeś się bowiem w laptopa, z którym nigdy się nie rozstajesz, i jesteś w stanie za pomocą programu OCR skonwertować listę Noego na plik tekstowy. Pozostało tylko wypisać numer zwierzęcia, którego brakuje. Pamiętaj tylko, że Twój laptop jest bezprzewodowy, a bateria w tamtym klimacie szybko się rozładowuje, więc masz bardzo, bardzo, bardzo mało czasu!

Wypadało by również wspomnieć, że nie wszystkie zwierzęta dotarły na miejsce zbiórki (nazw nie podam, jako że nie przetrwały one do dziś, w związku z czym nie zostały nazwane), więc nie wszystkie numery są użyte. Nimi się jednak nie przejmujesz - zależy Ci tylko na wyznaczeniu numeru brakującej jednostki, aby jej partner/partnerka nie był(a) samotny/a.

Wejście

Wejście składa się z nieznanej ilości numerów (która nie przekracza 5*105). Każdy z nich należy z kolei do przedziału <1;109>.

Wyjście

Jedna liczba, oznaczająca numer brakującego zwierzęcia.

Przykład

Wejście:
3
17
6
17
3
Wyjście:
6

Dodane przez:Piotr Kąkol
Data dodania:2011-04-17
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Języki programowania:All

ukryj komentarze
2011-08-17 14:06:38 Piotr Kąkol
@Kamil Magryta - Dobry, gratulacje. :-)
No a co do cin vs scanf to też się dziwiłem jak to zobaczyłem. :O
2011-08-17 12:10:02 Kamil Magryta
oh yea! Nareszcie wyrobiłem się w czasie, jeżeli dobry algorytm napisałem to rzeczywiście ciekawy ;). Jedno mnie tylko dziwi... na strumieniach mam szybszy program niż scanf/printf 0.o
2011-06-22 19:28:43 Piotr Kąkol
@KRzysztof Lewko - Wiem, zorientowałem się drugiego dnia. Nie wpadłem na ten n log n algorytm. Ale chyba na tym etapie niesprawiedliwe byłoby dawać TLE połowie userów (bo w końcu to moja wina, a nie ich).
2011-06-22 16:17:29 Krzysztof Lewko
Btw limit czasowy powinien być obniżony bo zwykły sort wchodzi.
2011-06-22 16:16:33 Krzysztof Lewko
https://www.spoj.pl/problems/OLOLO/
2011-05-15 18:49:16 Michał Bentkowski
Nareszcie! Po długiej walce udało się zrobić rozwiązanie w Pythonie :D.

Ostatnio edytowany: 2011-05-15 19:07:54
2011-05-04 14:49:14 Piotr Kąkol
@Mysizwierz - Dzięki. :-)

@Adam Folwarczny - Tak, da się. Jak już napisałem gdzieś tutaj najszybszy jest fread_unlocked (jednak między nim a freadem nie ma takiej różnicy jak między np. fgetc_unlocked i zwykłym fgetcem). Tak więc polecam wszystkie funkcje, które operują na plikach (czyli z przedrostkiem 'f'), a w szczególności ww.
2011-05-04 12:32:57 Adam Folwarczny
Ok, liniowo mam ale jakim cudem udało się wam zejść poniżej 0.2s ?
do in/out uzywam gets/puts, da sie to jeszcze jakos przyspieszyc ?
2011-05-02 00:46:35 Michał Janiec
O kurka wodna! Ale fajne zadanko :)
SPOJ System © 2012 Sphere Research Labs | Projekty informatyczne i aplikacje na zamówienie. All Rights Reserved.