FRAKTAL - konkurs programistyczny

Prawo Moore'a mówi, że co dwa lata podwaja się gęstość upakowania tranzystorów na powierzchni układów scalonych. Ten sam trend można zauważyć dla dysków twardych i ich pojemności. Ten postęp oczywiście nie dzieje się sam z siebie. Wynika to z ciężkiej pracy i pomysłowości inżynierów pracujących w danej dziedzinie.

Dysk twardy to urządzenie, w którym gęsto upakowane komórki pamięci mogą być namagnesowane w orientacji góra (G) lub dół (D). Niestety im mniejsza jest pojedyncza komórka, tym trudniej dokładnie odczytać jej wartość. Zakłócenia powodują m. in. inne komórki leżące obok. Okazuje się dużo łatwiej odczytać różnicę w namagnesowaniu sąsiadujących komórek, niż same ich wartości. Zbudujmy dysk działający na tej zasadzie!

Zamiast zapisywać 1-kę bitową poprzez namagnesowanie komórki pamięci w orientacji góra, a 0 - w orientacji dół, w naszym dysku 1-ka bitowa będzie zakodowana jako przeciwne namagnesowanie dwóch sąsiadujących komórek. Czyli GD lub DG oznacza 1-kę bitową. Brak zmiany w sąsiadujących komórkach (DD lub GG) oznacza 0 bitowe.

Może się wydawać, że w ten sposób potrzebujemy dwa razy więcej komórek do zapisania tych samych danych. Tak nie jest, ponieważ każda komórka należy do dwóch par. I tak naprawdę potrzebujemy jedną komórkę więcej, niż w standardowym podejściu do zapisu danych.

Napisz program, który będzie zapisywał i odczytywał dane z tak działającego dysku.

Zapis

Mając do zapisania ciąg bitów, najpierw musimy przygotować sektor do zapisu. Robimy to ustawiając cztery pierwsze komórki w orientacji dół. Następnie zaczynając od 5 komórki zapisujemy dane. Jeśli zapisujemy 1-kę bitową, to komórka musi być namagnesowana przeciwnie do wczesniejszej. Jeśli zapisujemy 0 to namagnsowanie musi być takie samo jak w poprzedniej komórce.

Odczyt

Odczytując dane, pamiętamy o pierwszych czterech komórkach kontrolnych. Kolejne bity odczytujemy porówując piątą komórkę z czwartą, szóstą z piątą itd.

Wejście

Na wejściu pojawi się jeden z dwóch możliwych ciągów składający się albo z samych znaków 1 i 0 albo G i D (ciąg ma maksymalnie 1000 znaków w pierwszym przypadku i 1004 w drugim). Jeśli na wejściu pojawi się ciąg zero-jedynkowy, to należy dokonać zapisu danych na dysk. W przeciwnym razie musimy odkodować bity z danych odczytanych z dysku.

Wyjście

W zależności od typu ciągu na wejściu, na wyjściu należy wyświetlić odpowiedni ciąg.

Przykład 1

Wejście:

1011110100

Wyjście:

DDDDGGDGDGGDDD

Przykład 2

Wejście:

DDDDGGDGDGGDDD

Wyjście:

1011110100