Szlaczek (omówienie)

24.08.2011

Do zadania można było podejść na kilka sposobów, poniżej opisujemy - naszym zdaniem - najprostszy.

Zauważmy, że niezależnie od tego jak wyglądał początkowy ciąg, po pierwszym kroku powstawania szlaczka Kornelia uzyskiwała palindrom, tj. ciąg który zawiera te same liczby w kolejności odczytywania od lewej do prawej, i w kolejności odwrotnej.

Oznaczmy ten (uzyskany po pierwszym kroku) ciąg jako P. Zauważmy, że w następnym kroku Kornelia dopisze do P, ten sam ciąg (gdyż P jest palindromem). Ciąg po drugim kroku będzie więc miał postać PP, a następnie PPPP, etc.

W takim razie szlaczek zapisywany przez Kornelię w istocie ma postać powtarzanego bez końca ciągu uzyskanego w drugim kroku.

Taki ciąg ma bardzo regularną postać - x-ta pozycja w nieskończonym ciągu zawiera tę samą liczbę co pozycja x modulo L, gdzie L oznacza długość P.

W takim razie wystarczyło zasymulować pierwszy krok powstawania szlaczka, a następnie wypisać liczbę na pozycji M modulo L.

Organizatorzy:

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com