Addım Addım İnkişaf
Yapon video oyun şirkəti Step Step Evolution adlı bir musiqi video oyunu hazırlayıb. Bu oyunun oynanışı olduqca sadədir. Oyunçular rəqs platformasında duraraq, ekranda göstərilən oxların ardıcıllığına uyğun olaraq panellərə addım atırlar.
Step Step Evolution oyununda səkkiz növ istiqamət oxu mövcuddur: YUXARI, YUXARI SAĞ, SAĞ, AŞAĞI SAĞ, AŞAĞI, AŞAĞI SOL, SOL və YUXARI SOL. Bu oxlar ekranın altından yuxarıya doğru hərəkət edir. İstiqamət oxu yuxarıdakı sabit oxla üst-üstə düşdüyü zaman, oyunçu rəqs platformasındakı müvafiq ox panelinə addım atmalıdır. Aşağıdakı şəkil rəqs platformasının necə göründüyünü göstərir.
Şəkil 1: Step Step Evolution üçün rəqs platforması
Oyunda aşağıdakı qaydalara riayət etməlisiniz:
Oyun başlanğıcı istisna olmaqla, redaktə məlumatına uyğun olmayan ox panelinə basmamalısınız.
Ayaq son dəfə basdığı paneldə qalmalı və növbəti ox panelinə basana qədər hərəkət etməməlidir.
Sol ayaq sağ ayağın dayandığı panelin sağında yerləşən panelə basmamalıdır. Eyni şəkildə, sağ ayaq sol ayağın dayandığı panelin solunda yerləşən panelə basmamalıdır.
Üçüncü şərtə gəldikdə, aşağıdakı şəkil düzgün və yanlış ayaq izlərinin nümunələrini göstərir.
Şəkil 2: Düzgün və yanlış ayaq izlərinin nümunələri
Birinci (sol ayaq SOL üçün, sağ ayaq AŞAĞI üçün) və ikinci (sol ayaq AŞAĞI SOL üçün, sağ ayaq YUXARI SOL üçün) ayaq izləri düzgündür. Sonuncu (sol ayaq SAĞ üçün, sağ ayaq AŞAĞI üçün) ayaq izi yanlışdır.
Qeyd edək ki, oyunun başlanğıcında sol və sağ ayaq istənilən ox panelində yerləşdirilə bilər. Həmçinin, ilk addımı sol ayaqla və ya sağ ayaqla, istədiyiniz kimi başlaya bilərsiniz.
Bu oyunu mükəmməl oynamaq üçün istedadlı oyunçular arasında "Təbii ayaq izi stili" adlanan oyun tərzi geniş yayılmışdır. "Təbii ayaq izi stili" oyunçuların sol və sağ ayaqla növbə ilə addım atdığı tərzdir. Lakin, oxların ardıcıllığı çətin olduqda, oyunçular bəzən bu tərzi pozmağa məcbur olurlar.
İndi, dostunuz sizin üçün redaktə məlumatı (basılacaq istiqamət oxlarının orijinal ardıcıllığı) yaradıb. Siz bu redaktə məlumatı ilə optimal oynadığınız zaman "Təbii ayaq izi stili"ni neçə dəfə pozmalı olduğunuzu maraqlanırsınız. Başqa sözlə, eyni ayaqla ardıcıl iki oxu basmalı olduğunuz minimum dəfə nə qədərdir?
Giriş verilənləri
Giriş bir neçə datasetdən ibarətdir. Hər bir dataset bir sətirdə istiqamət oxlarının ardıcıllığı ilə müəyyən edilir. İstiqamətlər 1 ilə 9 arasında olan rəqəmlərlə təsvir edilir, 5 istisna olmaqla. Aşağıdakı şəkil rəqəmlərlə istiqamət oxları arasındakı uyğunluğu göstərir.
Siz ardıcıllığın uzunluğunun 1 ilə 100000 arasında olduğunu qəbul edə bilərsiniz. Həmçinin, eyni istiqamətdə olan oxlar ardıcıl olaraq sətirdə görünməyəcək. Girişin sonu tək "#" ilə göstərilir.
Şəkil 3: Rəqəmlərin istiqamət oxlarına uyğunluğu
Çıxış verilənləri
Hər bir dataset üçün, optimal oynadığınız zaman "Təbii ayaq izi stili"ni neçə dəfə pozmalı olduğunuzu bir sətirdə çıxarın.