Jeśli jesteś właścicielem tej strony, możesz wyłączyć reklamę poniżej zmieniając pakiet na PRO lub VIP w panelu naszego hostingu już od 4zł!
2016-02-19    Programowanie, Spoj, C++, Algorytmy, Zadania

Postanowiłem dodać długo zapowiadany już post o Spoju. Sporo czasu wahałem się jaką ma on przyjąć formę. Początkowo planowałem dokładny opis każdego rozwiązania, jednakże doszedłem do wniosku, że takie podejście przyniosłoby więcej złego niż korzyści. Dlatego też skupię się jedynie na udzieleniu paru wskazówek, niż na dokładnym kodzie, linijka po linijce.

Wybrałem parę, moim zdaniem ciekawszych zadań, których będę chciał omówić mój sposób rozwiązania.

1. Stonogi
Zadanie to można bardzo prosto rozwiązać korzystając z ogólnego równania prostej. Równanie kierunkowe jest tu nie wystarczające, ponieważ ruch stonóg może być prostopadły do osi OX. Po jego wyznaczeniu, można obliczyć punkt przecięcia się kierunków ruchu obu stonóg(o ile taki istnieje) oraz sprawdzić czy leży on wewnątrz planszy. Kolejno obliczyć czasy uzyskania tego punktu przez głowę i ogon pierwszej jak i drugiej stonogi, a następnie wykorzystując otrzymane dane odpowiedzieć: TAK albo NIE.

2. Tanie hotele
To zadanie jet bardzo przyjemne, aż dziwię się, że jest tak mało poprawnych rozwiązań. Tutuj wystarczy użyć jednego z magicznych słów: rekurencja, a rozwiązanie zaraz przyjdzie do głowy.

3. Kwadracik
W tym zadaniu należy dostrzeć jedną kluczową rzecz tzn. górne ograniczenie sumy w czterech komórkach. Wówczas ilość przypadków dla których mamy obliczyć ilość możliwości gwałtowanie się zmniejsza. Można też pokusić się o napisanie najpierw generatora, a wyniki zapisac w tablicy. Dzięki czemu będziemy mogli odpowiadać w czasie O(1).

4. Jesienne porządki
W tym przypadku dam tylko jedną wskazówkę: mediana.

5. Całkowite pierwiastki wielomianu
Zadanie to należy rozwiązać wykorzystując twierdzenie Bézout. Dzięki skorzystaniu również ze schematu Hornera można uzyskać bardzo dobry czas.
Dodaj komentarz:
Nick:
URL(opcjonalnie):