1437 - Fractii 4: Difference between revisions

From Bitnami MediaWiki
Pagină nouă: == Enunţ == Se dă un șir de n fracții. Fiecare fracție este dată printr-o pereche de numere reprezentând numărătorul și numitorul fracției. De exemplu '''2010 34''' reprezintă fracția '''2010/34'''. O fracție poate fi ireductibilă sau se poate simplifica. În exemplul precedent, '''2010/34''' se simplifică prin '''2''' și rezultă '''1005/17'''. == Cerinţa == Să se afișeze, pentru fiecare fracție: 1) Prin câte moduri distincte se poate simplifica. 2) Fr...
 
Line 9: Line 9:
În fișierul de intrare '''fractii4.in''' pe prima linie se găsesc numerele '''P''' și '''n''', iar pe următoarele '''n''' linii se găsesc '''n''' perechi de numere, reprezentând numărătorul și numitorul fiecărei fracții, separate printr-un spațiu.
În fișierul de intrare '''fractii4.in''' pe prima linie se găsesc numerele '''P''' și '''n''', iar pe următoarele '''n''' linii se găsesc '''n''' perechi de numere, reprezentând numărătorul și numitorul fiecărei fracții, separate printr-un spațiu.
== Date de iesire ==
== Date de iesire ==
Pe fiecare din cele '''n''' linii ale fișierului '''fractii4.out''' se găsesc, pentru fiecare fracție, în ordinea dată în fișierul de intrare:
Dacă datele sunt introduse corect, în fișier se va afișa:''' "Datele sunt introduse corect."''', apoi pe fiecare din cele '''n''' linii ale fișierului '''fractii4.out''' se găsesc, pentru fiecare fracție, în ordinea dată în fișierul de intrare:
1) Dacă '''P = 1''', numărul de simplificări distincte posibile. Dacă nu este posibilă nicio simplificare (fracția este ireductibilă) se va afișa -1.
2) Dacă '''P = 2''' , fracția ireductibilă, numărătorul și numitorul fiind separați prin /. În cazul în care datele nu respectă restricțiile, se va afișa în fișier: '''"Datele nu corespund restricțiilor impuse."'''.


1) Dacă '''P = 1''', numărul de simplificări distincte posibile. Dacă nu este posibilă nicio simplificare (fracția este ireductibilă) se va afișa -1.
2) Dacă '''P = 2''' , fracția ireductibilă, numărătorul și numitorul fiind separați prin /.
== Restricții și precizări ==
== Restricții și precizări ==
* n ⩽  100 000
* n ⩽  100 000

Revision as of 20:30, 9 April 2023

Enunţ

Se dă un șir de n fracții. Fiecare fracție este dată printr-o pereche de numere reprezentând numărătorul și numitorul fracției. De exemplu 2010 34 reprezintă fracția 2010/34. O fracție poate fi ireductibilă sau se poate simplifica. În exemplul precedent, 2010/34 se simplifică prin 2 și rezultă 1005/17.

Cerinţa

Să se afișeze, pentru fiecare fracție:

1) Prin câte moduri distincte se poate simplifica. 2) Fracția ireductibilă.

Date de intrare

În fișierul de intrare fractii4.in pe prima linie se găsesc numerele P și n, iar pe următoarele n linii se găsesc n perechi de numere, reprezentând numărătorul și numitorul fiecărei fracții, separate printr-un spațiu.

Date de iesire

Dacă datele sunt introduse corect, în fișier se va afișa: "Datele sunt introduse corect.", apoi pe fiecare din cele n linii ale fișierului fractii4.out se găsesc, pentru fiecare fracție, în ordinea dată în fișierul de intrare: 1) Dacă P = 1, numărul de simplificări distincte posibile. Dacă nu este posibilă nicio simplificare (fracția este ireductibilă) se va afișa -1. 2) Dacă P = 2 , fracția ireductibilă, numărătorul și numitorul fiind separați prin /. În cazul în care datele nu respectă restricțiile, se va afișa în fișier: "Datele nu corespund restricțiilor impuse.".

Restricții și precizări

  • n ⩽ 100 000
  • 0 < numitor, numărător < 2 000 000
  • P este 1 sau 2

Exemplul 1

fractii4.in
11 4
8 4
3 2
1 6
12 6
fractii4.out
Datele introduse corespund restricțiilor impuse.
2
-1
-1
3

Explicație

Pentru acest test 'P = 1, deci se va rezolva doar cerinţa 1). Prima fracție se poate simplifica prin 2 moduri: prin 2 și 4. A doua este ireductibilă, deci se va afișa -1. A treia este ireductibilă, deci se va afișa -1. A patra se poate simplifica prin 3 moduri: 2, 3 și 6.

Exemplul 2

fractii4.in
12 3
22 6
11 4
125 25
fractii4.out
11/3
11/4
5/1

Explicație

Pentru acest test P = 2, deci se va rezolva doar cerinţa 2). Prima fracție se simplifică prin 2. A doua fracție este ireductibilă, deci va fi afișată fără schimbare. Ultima fracție poate fi redusă prin 25 și devine ireductibilă. Chiar dacă numitorul este 1, acesta va fi afișat.

Rezolvare

<syntaxhighlight lang="python" line> import math

def prim(n):

   if n == 0 or n == 1:
       return 0
   if n == 2:
       return 1
   if n % 2 == 0:
       return 0
   else:
       for i in range(3, int(math.sqrt(n))+1, 2):
           if n % i == 0:
               return 0
   return 1

def prime(a, b):

   if b == 0:
       return a
   else:
       return prime(b, a % b)

def validare_date(n, p):

   if n <= 100000 and p in [1, 2]:
       return True
   else:
       return False

if __name__ == '__main__':

   fin = open("fractii4.in", "r")
   fout = open("fractii4.out", "w")
   p, n = map(int, fin.readline().split())
   if validare_date(n, p):
       print("\nDatele de intrare corespund restrictiilor impuse.\n")
       for i in range(n):
           a, b = map(int, fin.readline().split())
           x, y = a, b
           if p == 1:
               if prim(a) == 0 and prim(b) == 0 and prime(a, b) == 1:
                   d = 0
                   d1 = prime(a, b)
                   for j in range(1, int(math.sqrt(d1))+1):
                       if d1 % j == 0:
                           d += 2
                           if j * j == d1:
                               d -= 1
                   fout.write(str(d-1) + '\n')
               else:
                   fout.write("-1\n")
           else:
               t = prime(a, b)
               fout.write(str(x//t) + '/' + str(y//t) + '\n')
       fin.close()
       fout.close()
   else:
       print("Datele de intrare nu corespund restrictiilor impuse.")

</syntaxhighlight>