Pamięć doskonała (omówienie)
03.05.2011
Rozważmy parę odpowiadających sobie (w sensie opisanym w treści zadania) pozycji x i y. Zauważmy, że wartości poszukiwanych ciągów P i A na tych pozycjach można ustalić na podstawie wartości zadanego ciągu S na pozycjach x i y. Innymi słowy - każda para odpowiadających sobie pozycji może być rozpatrywana w oderwaniu od pozostałych par. Jeśli wartości zadanego ciągu S na pozycjach x i y oznaczymy jako Sx i Sy (i analogicznie dla ciągów P i A), to warunki, które muszą spełnić poszukiwane ciągi można zapisać jako układ dwóch równań:
(co odpowiada temu, że ciągi P i A mają się sumować do S) Zauważmy jednak, że z palindromiczności ciągu P wynika, że Py jest równe Px. Podobnie z antypalindromiczności ciągu A wynika, że Ay jest równe -Ax. W takim razie z układu można wyeliminować te dwie zmienne.
Ponieważ wartości ciągu S są znane, otrzymujemy układ dwóch równań z dwoma niewiadomymi, który można rozwiązać standardowymi metodami, otrzymując wzór opisujący dokładnie jedną parę liczb rzeczywistych spełniającą dany układ. W tym wypadku będzie to:
Jeśli otrzymane liczby rzeczywiste są także całkowite (co zależy od parzystości odpowiedniej sumy/różnicy), to stanowią poprawne rozwiązanie dla danej pary, w przeciwnym wypadku rozwiązanie nie istnieje. |
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com