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: Sn = Sn-1 AT(Sn-1 ) AT(Sn-1 ) Sn-1 .
Se dau n numere naturale: k1 , k2 , k3 ... kn. Pentru fiecare număr ki se determină caracterul de pe poziția ki dintr-un element al șirului S care are cel puțin ki 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 ki, 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 261;
- 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
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")
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.
