1992 - PlatouAT

Cerința

Se definește operația AT un procedeu prin care se schimbă caracterul 'A' în 'T' și caracterul 'T' în 'A'. Operația poate fi modelată ca o funcție astfel: AT(A) = T și AT(T) = A. Operația se generalizează pentru orice secvență de caractere formată din literele A și T. De exemplu, dacă se aplică operația AT pentru secvența AAATTA, se va obține TTTAAT. Notăm AT(AAATTA) = TTTAAT.

Considerăm șirul infinit S, definit după următoarea regulă:

• S1 = ATTA
• S2 = ATTATAATTAATATTA
• S3 = ATTATAATTAATATTATAATATTAATTATAATTAATATTAATTATAATATTATAATTAATATTA

În general: S_n = S_n-1 AT(S_n-1 ) AT(S_n-1 ) S_n-1 .

Se dau n numere naturale: k₁ , k₂ , k₃ ... k_n. Pentru fiecare număr k_i se determină caracterul de pe poziția k_i dintr-un element al șirului S care are cel puțin k_i caractere. Cu aceste caractere se construiește un nou șir V.

Să se determine un număr L cu toți biții setați, reprezentând lungimea maximă a unei secvențe maximale de caractere 'T' din șirul V. Dacă în șirul V nu există nicio astfel de secvență se va afișa mesajul NU EXISTA.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi cele n numere naturale de forma k_i, separate prin spații.

Date de ieșire

Programul va afișa pe ecran numărul L cerut sau mesajul NU EXISTA, alături de un mesaj de confirmare a datelor ("Input valid" sau "Input invalid" după caz).

Restricții și precizări

• L ⩽ N ⩽ 1.111.111;
• cele n numere citite vor fi mai mici decât 2⁶¹;
• un număr natural are toți biții setați dacă reprezentarea sa binară conține numai cifre 1;
• pentru un șir dat, o secvență de elemente cu o anumită proprietate este maximală dacă la secvență nu se mai pot adăuga elemente cu acea proprietatea. De exemplu, în șirul qweauaiopaert secvența de vocale eauaio este maximală, dar secvența eaua nu este maximală pentru că la ea se mai pot adăuga alte vocale.

Exemple

Exemplul 1:

Intrare

5

1 2 2 2 1

Ieșire

Input valid

3

Explicație S-a format șirul V : ATTTA, cea mai lunga secvență de elemente T are lungimea 3, iar 3 este un număr cu toți biții setați.

Exemplul 2:

Intrare

20

1 2 1 2 2 2 1 2 2 2 2 2 2 2 1 1 1 1 1 1

Ieșire

Input valid

7

Explicație S-a format șirul V : ATATTTATTTTTTTAAAAAA, lungimile secvențelor sunt : 1, 3, 7, toate aceste numere au biții setați, însă, cea mai lungă secvență este de 7 T-uri.

Exemplul 3:

Intrare

6

1 2 3 2 3 1

Ieșire

Input valid

NU EXISTA

Explicație S-a format șirul V : ATTTTA, cea mai lungă secvență de elemente T are lungimea 4, iar 4 NU este un număr cu toți biții setați.

Exemplul 4:

Intrare

15

6 3 2 3 4 3 3 2 3 2 2 3 2 1 1

Ieșire

Input valid

3

Explicație S-a format șirul V : ATTTATTTTTTTTAA, cea mai lungă secvență de elemente T are lungimea 8, dar 8 NU este un număr cu toți biții setați. Cea mai lungă secvență de elemente T, de lungime L, L fiind un număr cu toți biții setați, este TTT și are lungime 3.

Rezolvare

<syntaxhighlight lang="python"> def all_bits(x):

   return (x and not (x & (x-1))) # verifica daca toate bitii lui x sunt setati la 1

def validate_input(x):

   return x < 2**61 and all_bits(x)

def get_secv(x):

   secv = 1
   while secv < x: # caut lungimea sirului, putere de 4, care cuprinde pozitia x
       secv <<= 2
   return secv

def reduce_to_first_cadran(x, secv):

   cadran = x // secv + (x % secv != 0) # aflu "cadranul" in care ma aflu, raportat la lungimea secventelor
   if cadran == 1:
       return x, 65 # cazul de baza, nu sufera transformari
   elif cadran == 2 or cadran == 3:
       x -= (cadran - 1) * secv # reduc x ul in primul cadran
       return x, 149 - 65 # se schimba valoarea
   else:
       x -= 3 * secv # reduc x ul in primul cadran
       return x, 65

def process_input(n):

   for i in range(n):
       x = int(input())
       if validate_input(x):
           print("Input valid")
           secv = get_secv(x)
           x, c = reduce_to_first_cadran(x, secv)
           yield x, secv, c
       else:
           print("Input invalid")

if __name__ == '__main__':

   n = int(input())
   lmax = 0
   l = 0
   start = False

   for x, secv, c in process_input(n):
       if x == 2 or x == 3:
           c = 149 - c
       if c == ord('T'):
           if not start:
               start = True
               l = 1
           else:
               l += 1
       else:
           if all_bits(l + 1):
               lmax = max(lmax, l)
           l = 0
           start = False

   if all_bits(l + 1):
       lmax = max(lmax, l)

   if lmax:
       print(lmax)
   else:
       print("NU EXISTA")

</syntaxhighlight>

Explicație cod

Acest cod implementează o funcționalitate care primește un număr n și n valori întregi de la utilizator. Funcția verifică dacă fiecare valoare îndeplinește anumite condiții și, dacă da, efectuează anumite transformări și calculează lungimea celei mai lungi secvențe continue de caractere 'T' în codul ASCII obținut în urma transformărilor.

Funcția all_bits(x) primește un întreg și verifică dacă toți biții sunt setați la 1. Funcția validate_input(x) verifică dacă valoarea introdusă x este mai mică decât 2^61 și toți biții sunt setați la 1. Funcția get_secv(x) calculează cea mai mare putere de 4 mai mică decât valoarea introdusă x.

Funcția reduce_to_first_cadran(x, secv) primește două valori, o valoare întreagă x și o valoare secv și calculează în ce cadran se află x raportat la secv, reducând x la valoarea sa din primul cadran (între 0 și secv). Funcția returnează valoarea x și c, care este un număr în funcție de cadranul în care se află x.

Funcția process_input(n) primește un întreg n și citește n valori întregi de la utilizator. Pentru fiecare valoare, se verifică dacă aceasta îndeplinește condițiile necesare și, în caz afirmativ, se calculează secvența și cadranul corespunzătoare, și se returnează o secvență de trei valori: x, secv și c.

Blocul __main__ primește un întreg n și apelează funcția process_input(n) pentru a procesa valorile introduse. Pentru fiecare valoare x, se aplică anumite transformări și se calculează lungimea celei mai lungi secvențe continue de caractere 'T' în codul ASCII obținut. Lungimea maximă a secvenței este afișată la sfârșitul funcției.

În general, codul este folosit pentru a procesa și transforma date și pentru a calcula anumite valori specifice, cum ar fi lungimea celei mai lungi secvențe de caractere.