[SMWP_115] Dzień Dziecka

0 Flares Twitter 0 Facebook 0 0 Flares ×

Link do zadania:
http://www.spoj.com/SMWP/problems/SMWP_115/

Opis problemu:
W zadaniu wcielamy się w rolę ojca/matki Jasia. Naszym zadaniem jest stworzyć aplikację dla syna, aby niezależnie od podanego N w zabawie zawsze wiedział na której pozycji w szeregu należy się ustawić, aby wygrać. Zabawa natomiast polega na podawaniu dokładnie i zawsze 4 liczb nieujemnych, których łączna suma wynosi N. Każde dziecko, gdy przychodzi jego kolej podaje swoje 4 liczby, które zakładamy że nie pojawiły się wcześniej w identycznym porządku (1,2,3,4 i 1,2,4,3 to dwa różne wyniki).

Rozwiązanie:
Rozwiązaniem do tego zadania jest przesunięty o wyraz ciąg ze strony oeis.org/ciag. Oczywiście musimy pamiętać o odpowiednim modulowaniu wyniku (10101), ponieważ tylko tyle dzieci bierze udział w zabawie. Należy pamiętać, że Jaś zawiera się w tej liczbie oraz, że w przypadku, gdy modulo wyniku jest równe 0 to zwycięską pozycją jest ostatnia pozycja w szeregu, czyli 10101 (miejsca liczymy od 1).

Problem z modulowaniem
Jest to niezwykle częsty problem spotykany w tego rodzaju zadań, ponieważ musimy pamiętać o zmodulowaniu częściowym wyniku gdyż zakres jest na tyle duży, że przemnażanie wszystkich elementów wzoru wykracza poza zakres unsigned long longa. Jak sobie z tym poradzić?
Widzimy, że we wzorze występuje dzielenie przez 6, więc aby liczba podzieliła się przez 6 bez reszty musi być ona podzielna przez 2 i 3. Nasz wzór składa się z 3 kolejnych liczb naturalnych, przeprowadzając testowe podstawienia różnych wartości możemy zauważyć, że jeśli n%3==1 to wówczas (n+1)(n+2) jest podzielne przez 6, natomiast w pozostałych przypadkach możemy przyjąć, że (n)(n+1) jest podzielne przez 6. Dzięki temu, że liczba jest podzielna nie musimy się martwić o poprawność modulowania wyniku. Następnie wystarczy iż przemnożymy zmodulowany wynik przez pozostały czynnik i cały wynik zmodulujemy 10101.
Innym rozwiązaniem tego problemu jest przyjęcie, że zawsze przemnażamy np dwa pierwsze czynniki natomiast przy dzieleniu przez 6 pamiętamy zarówno wynik całkowitoliczbowy jak i resztę z dzielenia, która niezbędna będzie do poprawnego przemnażania ostatniego czynnika.

Print Friendly

2 Komentarze

  1. Mam pytanie co do drugiego sposobu rozwiązania, gdzie przemnażamy dwa pierwsze czynniki. Jak wykorzystujemy resztę z dzielenia przez 6 do przemnożenia ostatniego czynnika? Byłbym wdzięczny za odpowiedź lub wskazówkę.

    • Aby wynik był poprawny musimy pamiętać o tej reszcie z dzielenia podczas przemnażania ostatniego czynnika, wygląda to mniej więcej tak:

      e=((n*(n+1))/6); //wartość dwóch czynników div 6
      mod=(n*(n+1))-6*e; //reszta z dzielenia % 6
      e%=m; //modulowanie m=10101
      e=(((n+2)*e)+((mod*(n+2))/6))%m; //przemnazanie przez ostatni czynnik i modulowanie, co daje gotowy wynik w zadaniu.

Dodaj komentarz

Wymagane pola są oznaczone *.