Runda 13 - Ślimaki
28.12.2009 - Damian Rusak
Zawody stałe, runda 13. Limit czasowy: 1s; Limit pamięciowy: 32MB; ŚlimakiGrupa ślimaków odpoczywała sobie w rządku pewnego słonecznego poranka na wielkim liściu sałaty. Umówmy się, że ślimaki zajmują w rzędzie miejsca numerowane kolejnymi liczbami naturalnymi. Co pewnie czas nad polem sałaty przelatują ptaki i rzucają swe cienie nad naszym liściem. Cień ptaka pokrywa pewien kawałek liścia. Ślimaki jako istoty bojaźliwe i ciekawskie zarazem zachowują się w nietypowy sposób - jeśli jakiś ślimak nie chowa się w swojej skorupie, po czym padnie na niego cień ptaka, natychmiast chowa się do środka ze strachu. Jeśli zaś znajduje się w skorupie i przelatuje powyżej niego ptak, rzucając cień, ślimak z ciekawości wypełza ze swojego domu. Zaciekawiło Cię to, które ślimaki zakończą dzień wewnątrz swych skorup, a które będą o wieczorze wygrzewać się na dogasającym słońcu. Zdobywszy od miejscowych ornitologów plany przelotu ptaków nad polem sałaty, postanawiasz napisać program, który Ci pomoże. Zadanie: Znając ilość ślimaków na liściu sałaty, oraz pozycje ślimaków, które zakrywają kolejne cienie ptaków, odpowiedz dla każdego ślimaka na pytanie, czy po przelocie ostatniego ptaka będzie się znajdował w skorupce czy na zewnątrz. Wejście: Pierwsza linia wejścia zawiera dwie liczby - i - - oznaczające kolejno ilość ślimaków na liściu sałaty oraz ilość przelatujących ptaków. W kolejnych liniach znajdują się pary liczb naturalnych oznaczające pozycje ślimaków - rozpoczynającą i kończącą kawałek liścia, pokryty przez cień -tego ptaka (włącznie). Rozumiemy to tak, że cień padł na ślimaki . Przyjmij, że na początku wszystkie ślimaki są poza skorupami. Wyjście: Wyjście powinno składać się z jednej linii, w której powinny znajdować się kolejno liczby . Jeśli -ty ślimak jest w środku skorupy po przelocie ostatniego ptaka, to . W przeciwnym razie . Przykład: 8 6 1 4 1 8 2 3 5 6 5 6 8 8 Wyjście: 0 1 1 0 1 1 1 0 Wyjaśnienie: Np. ślimak nr 1 chowa się, gdy przelatuje pierwszy ptak, po czym wychodzi ze skorupy po przelocie drugiego ptaka i już więcej żaden cień go nie niepokoi. Za to ślimak nr 3 chowa się przy pierwszym ptaku, wychodzi przy drugim i znów chowa się przy trzecim.
Przykład 2: 8 4 2 2 4 4 7 8 2 4 Wynik: 0 0 1 0 0 0 1 1
Ostatni przelot ptaka na rysunku poniżej:
Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
(4 ocen) |
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com