4100 - Bipatrat

Sursa: [1]

---

Cerinţa

Fiind dată o secvență de numere naturale, să se verifice dacă numerele respective sunt bipătrate, iar pentru cele ce îndeplinesc condiția să se afișeze în ordine crescătoare toate pătratele perfecte care se pot obține prin inserarea unei cifre.

Date de intrare

Fișierul de intrare bipatrat.in conține mai multe numere naturale, câte un număr pe o linie.

Date de ieșire

Fișierul de ieșire bipatrat.out va conține pe linia linie cifra 0, dacă numărul scris pe linia linie în fișierul de intrare nu este bipătrat, iar în caz contrar, va conține o succesiune de numere naturale separate prin câte un spațiu, scrise în ordine strict crescătoare, reprezentând pătratele perfecte care se pot obține din numărul aflat pe linia linie în fișierul de intrare, prin inserarea unei cifre.

Restricţii şi precizări

• În fişierul de intrare sunt maximum 2000 de numere de cel mult 13 cifre.
• Inserarea la începutul numărului se poate realiza doar dacă cifra inserată este diferită de 0.

Exemple

Exemplul 1

bipartit.in

225

144

34

49

16

Ecran

Datele sunt introduse corect.

bipartit.out

1225 2025 4225 7225

1444

0

0

169 196

Explicație

225 este pătrat perfect și în urma unei inserări se pot obține următoarele pătrate perfecte: 1225, 2025, 4225 și 7225, deci 225 este bipătrat. Similar, 144 este bipătrat, deoarece 1444 este pătrat perfect. 34 nu este pătrat perfect, deci nici bipătrat. 49 este pătrat perfect, dar nu este bipătrat. 16 este explicat în enunț.

Rezolvare

<syntaxhighlight lang="python" line>

1. 4100

import math

def este_bipatrat(n):

   # Verificăm dacă n este pătrat perfect
   if int(math.sqrt(n))**2 != n:
       return False

   # Obținem lista de numere obținute prin inserarea unei cifre în n
   nums = []
   str_n = str(n)
   for i in range(len(str_n)+1):
       for j in range(10):
           if i == 0 and j == 0:
               continue
           new_num = int(str_n[:i] + str(j) + str_n[i:])
           if int(math.sqrt(new_num))**2 == new_num:
               nums.append(new_num)

   # Verificăm dacă numerele obținute sunt și ele pătrate perfecte
   for num in nums:
       if int(math.sqrt(num))**2 != num:
           return False

   return True

def patrat_perfect(n):

   # Obținem lista de numere obținute prin inserarea unei cifre în n
   nums = []
   str_n = str(n)
   for i in range(len(str_n)+1):
       for j in range(10):
           if i == 0 and j == 0:
               continue
           new_num = int(str_n[:i] + str(j) + str_n[i:])
           if int(math.sqrt(new_num))**2 == new_num:
               nums.append(new_num)

   # Obținem lista de pătrate perfecte din nums
   perfect_squares = []
   for num in nums:
       if int(math.sqrt(num))**2 == num:
           perfect_squares.append(num)

   # Returnăm lista sortată în ordine crescătoare
   return sorted(perfect_squares)

if __name__ == "__main__":

   # Deschidem fișierele de intrare și de ieșire
   with open("bipatrat.in", "r") as fin, open("bipatrat.out", "w") as fout:
       # Citim numărul de linii din fișierul de intrare
       n = int(fin.readline())

       # Parcurgem liniile din fișierul de intrare
       for i in range(n):
           # Citim numărul de pe linia curentă
           num = int(fin.readline())

           # Verificăm dacă numărul este bipătrat
           if este_bipatrat(num):
               # Obținem lista de pătrate perfecte
               perfect_squares = patrat_perfect(num)

               # Scriem lista în fișierul de ieșire
               for square in perfect_squares:
                   fout.write(str(square) + " ")
               fout.write("\n")
           else:
               fout.write("0\n")

</syntaxhighlight>

Explicație rezolvare

   În primul rând, programul definește o funcție numită este_bipatrat(n) care primește un număr n și verifică dacă acesta este bipătrat. Mai întâi, funcția verifică dacă n este pătrat perfect prin compararea pătratului radicalului său cu n. Dacă n nu este pătrat perfect, atunci funcția returnează False.În continuare, funcția obține o listă de numere obținute prin inserarea unei cifre în n. Pentru aceasta, convertim numărul n într-un șir de caractere, apoi parcurgem fiecare poziție din șir și încercăm să inserăm fiecare cifră posibilă. Excepție facem pentru cazul în care prima cifră este 0, pentru a evita apariția unor numere cu zero în față. Dacă noul număr obținut prin inserarea cifrei este pătrat perfect, îl adăugăm la lista nums.În final, verificăm dacă fiecare număr din lista nums este pătrat perfect. Dacă există un număr care nu este pătrat perfect, atunci funcția returnează False. Altfel, funcția returnează True.Următoarea funcție definită în program este patrat_perfect(n), care primește un număr n și returnează o listă cu toate pătratele perfecte care pot fi obținute prin inserarea unei cifre între cifrele lui n. Funcția obține lista nums de numere obținute prin inserarea unei cifre în n folosind aceeași metodă ca în funcția is_bipatrat(). Apoi, funcția parcurge lista nums și adaugă într-o altă listă numerele care sunt pătrate perfecte. În final, lista de pătrate perfecte este sortată în ordine crescătoare și returnată.În main() se deschid fișierele de intrare și de ieșire. Se citește numărul de linii din fișierul de intrare, apoi se parcurg liniile și se citește numărul de pe fiecare linie. Pentru fiecare număr citit, programul verifică dacă este bipătrat prin apelarea funcției este_bipatrat(). Dacă numărul este bipătrat, se obține lista de pătrate perfecte folosind funcția patrat_perfect() și aceasta este scrisă în fișier.