1516 - Bosumflat

Sursa: [1]

---

Cerinţa

Vrăjitorul informatician Arpsod a făcut un farmec asupra unui șir de N numere naturale, fiecare număr având exact 8 cifre (doar vrăjitorul știe de ce a ales cifra 8). În urma farmecului, numerele au început să prindă sentimente. Un număr X se numește bosumflat dacă există un alt număr Y, printre cele N, cu proprietatea că, numărul format din cifrele de pe poziții impare ale lui X este strict mai mic decât numărul format din cifrele de pe poziții pare ale lui Y și numărul format din cifrele de pe poziții pare ale lui X este strict mai mare decât numărul cifrele de pe poziții impare ale lui Y. Vom defini gradul de bosumflare al unui număr X ca fiind egal cu numărul de numere dintre cele N, care îl bosumflă pe X. Pentru că vrăjitorul este prea ocupat cu alți bosumflați, vă roagă pe voi să determinați gradul de bosumflare pentru fiecare dintre cele N numere. Cunoscându-se N, numărul de numere precum și numerele efective, determinați gradul de bosumflare pentru fiecare număr în parte.

Date de intrare

Pe prima linie a fișierului bosumflat.in se găsește numărul natural N. Pe cea de-a doua linie se găsesc N numere naturale (nu neapărat distincte), fiecare având exact 8 cifre.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe prima linie a fișierului bosumflat.out se vor afișa N numere naturale separate prin spațiu cu semnificația că al i-lea număr afișat reprezintă gradul de bosumflare al celui de-al i-lea număr din șirul inițial. În caz contrar, pe ecran se va afișa: "Datele nu au fost introduse corect."

Restricţii şi precizări

• 2 ≤ N ≤ 5000
• Cele N numere sunt naturale și au exact 8 cifre
• Dacă un număr nu este bosumflat atunci acesta are gradul de bosumflare 0.
• Se garantează că primele două cifre ale fiecărui număr sunt nenule.

Exemple

Exemplul 1

bosumflat.in

5

15629013 29032000 19970808 33331111 86000000

Ecran

Datele sunt introduse corect.

bosumflat.out

3 4 4 3 2

Rezolvare

<syntaxhighlight lang="python" line>

1. 1516

def verificare_restricții(p, n, cifre):

   if p not in (1, 2):
       return False
   if not (2 <= n <= 10**9):
       return False
   for cifra in cifre:
       if cifra not in (1, 2, 3):
           return False
   return True

def maxim_cifre_1_consecutive(n, cifre):

   max_consecutive = 0
   consecutive = 0
   for cifra in cifre:
       if cifra == 1:
           consecutive += 1
           max_consecutive = max(max_consecutive, consecutive)
       else:
           consecutive = 0
   return max_consecutive

def numar_babilonian_to_decimal(n, cifre):

   numar = 0
   putere = 1
   for i in range(n-1, -1, -1):
       numar += cifre[i] * putere
       putere *= 60 if i > 0 and cifre[i-1] == 2 else 1
   return numar

if __name__ == '__main__':

   with open("babilon.in") as f:
       p = int(f.readline().strip())
       n = int(f.readline().strip())
       cifre = list(map(int, f.readline().strip().split()))

   if verificare_restricții(p, n, cifre):
       print("Datele sunt introduse corect.")
       if p == 1:
           rezultat = maxim_cifre_1_consecutive(n, cifre)
           with open("babilon.out", "w") as g:
               g.write(str(rezultat))
       else:
           rezultat = numar_babilonian_to_decimal(n, cifre)
           with open("babilon.out", "w") as g:
               g.write(str(rezultat))
   else:
       print("Datele nu au fost introduse corect.")

</syntaxhighlight>

Explicație rezolvare

Acest cod implementează o funcție numită este_bosumflat care primește două numere întregi x și y și returnează adevărat dacă x este bosumflat în raport cu y, și fals în caz contrar.

Pentru a determina dacă x este bosumflat în raport cu y, se extrag cifrele impare ale lui x și cifrele pare ale lui y în variabila x_impare, respectiv y_pare. De asemenea, se extrag cifrele pare ale lui x și cifrele impare ale lui y în variabilele x_pare și, respectiv, y_impare. Apoi, se compară x_impare cu y_pare și x_pare cu y_impare, iar funcția returnează adevărat dacă ambele comparații sunt adevărate.

În continuare se citește fișierul bosumflat.in pentru a obține numărul n și n numere întregi stocate în lista numere. Se verifică dacă datele de intrare respectă restricțiile impuse (n între 2 și 5000 și numărul de elemente din lista numere este n). Pentru fiecare număr din lista numere, se calculează gradul de bosumflare prin parcurgerea tuturor perechilor posibile de numere și numărând câte dintre aceste perechi sunt bosumflate. Rezultatele sunt stocate în lista grad_bosumflare. Apoi, rezultatele sunt scrise în fișierul bosumflat.out și se afișează un mesaj de confirmare că datele de intrare au fost introduse corect.