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ń:

  • Px + AxSx
  • Py + AySy
(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.

  • Px + Ax = Sx
  • Px - AxSy
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:
  • Px = (Sx + Sy)/2
  • Py = (Sx - Sy)/2 

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.

Organizatorzy:

Wrocławski Portal Informatyczny Instytut Informatyki Uniwersytet Wrocławski Wrocław

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com