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. |
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com