2430 - zebra

Enunț

Oleg ține un istoric al vieții sale. O zi rea este notata cu 0, iar una bună este notată cu 1. Oleg numește un subșir zebră, un subșir care începe și se termină cu o zi rea și nu conține două zile de același fel pe poziții alăturate. De exemplu 0101, 001 și 0110 nu sunt subșiruri zebra, dar 010, 0 și 01010 sunt subșiruri zebră.

Cerința

Să se determine o împărțire a unui șir în subșiruri zebră.

Date de intrare

Programul citește de la tastatură un șir de caractere format din 0 și 1.

Date de ieșire

Programul va afișa pe ecran S, numărul de subșiruri, iar apoi, pe următoarele S linii numărul de zile componente ale fiecărui subșir și pozițiile din șirul inițial la care se află acestea. Dacă șirul nu se poate împărții în subșiruri zebră, atunci se va afișa -1.

Restricții și precizări

• Inputul conține cel mult 200.000 de caractere.
• Orice împărțire în subșiruri zebră este acceptată.

Exemplu 1:

Intrare

0010100

Ieșire

3

3 1 3 4

3 2 5 6

1 7

Exemplu 2:

Intrare

111

Ieșire

-1

Rezolvare

<syntaxhighlight lang="python"> def validate_input(sir):

   if len(sir) > 200000:
       print("Inputul depășește limita de 200.000 de caractere.")
       return False
   return True

def gaseste_subsiruri_zebra(sir):

   n = len(sir)
   subSiruri = []

   i = 0
   while i < n:
       # Găsirea primei zi rele
       while i < n and sir[i] == '1':
           i += 1

       if i == n:
           break  # Am ajuns la finalul șirului, nu mai avem subșiruri zebră

       start = i
       ziua_curenta = 0
       while i < n and sir[i] == '0':
           ziua_curenta += 1
           i += 1

       if i == n:
           break  # Am ajuns la finalul șirului, ultima zi a fost bună

       # Verificăm dacă următoarea zi este rea
       if i < n and sir[i] == '1':
           subSiruri.append((ziua_curenta, start + 1, i))

   if not subSiruri:
       return -1

   return subSiruri

1. Citirea datelor de intrare

sir = input().strip()

1. Găsirea subșirurilor zebră

rezultat = gaseste_subsiruri_zebra(sir)

1. Afișarea rezultatelor

if rezultat == -1:

   print(-1)

else:

   print(len(rezultat))
   for subSir in rezultat:
       print(*subSir)

</syntaxhighlight>