1076 - Grupe
Enunț
Se consideră un tablou bidimensional cu m linii, n coloane şi elemente numere naturale. Pentru fiecare element se determină numărul de divizori pozitivi. Se formează apoi grupe cu elementele tabloului care au acelaşi număr de divizori, grupe notate G1, G2, …, Gk. Se ordonează descrescător grupele după numărul de elemente ce le conţin. Se ştie că o grupă G1 se află în faţa unei alte grupe G2 dacă G1 are mai multe elemente decât G2 sau, în cazul în care cele două grupe conţin acelaşi număr de elemente, numărul de divizori ai elementelor din grupa G1 este mai mare decât numărul de divizori ai elementelor din grupa G2. După ordonarea descrescătoare a grupelor, notăm prima grupă cu A şi a doua grupă cu B. În cazul în care toate elementele vor avea acelaşi număr de divizori, va exista o singură grupă, grupa A.
Cerința
Scrieţi un program care citeşte m, n, elementele tabloului şi afişează:
a) numărul de divizori pozitivi pentru grupa A, numărul de elemente din grupă şi cea mai mare valoare din grupă;
b) numărul de divizori pozitivi pentru grupa B, numărul de elemente din grupă şi cea mai mare valoare din grupă; în cazul în care nu există grupa a doua, se va afişa de trei ori valoarea 0.
Date de intrare
Fișierul de intrare grupein.txt conține pe prima linie valorile lui m şi n separate printr-un spaţiu, iar pe celelalte m linii câte n elemente separate două câte două printr-un spaţiu, reprezentând elementele tabloului.
Date de ieșire
Fișierul de ieșire grupeout.txt va conține:
- pe prima linie valoarea numărului de divizori pozitivi din grupa A, numărul de elemente din grupa A şi cea mai mare valoare din grupa A, valori separate două câte două printr-un singur spaţiu;
- pe a doua linie valoarea numărului de divizori pozitivi din grupa B, numărul de elemente din grupa B şi cea mai mare valoare din grupa B, valori separate două câte două printr-un singur spaţiu.
Restricții și precizări
- 1 ⩽ n, m ⩽ 100
- elementele tabloului bidimensional iniţial sunt mai mici sau egale decât 100.000 şi mai mari decât 1;
- o grupă poate fi compusă dintr-un singur element.
Exemplul 1
- Intrare
- grupein.txt
- 2 3
- 16 2 4
- 10 6 5
- Ieșire
- Datele de intrare corespund restricțiilor impuse
- grupeout.txt
- 4 2 10
- 2 2 5
Explicație
Numărul divizorilor pentru fiecare element al tabloului: 5 divizori (pentru valoarea 16), 2 divizori (pentru valoarea 2), 3 divizori (pentru valoarea 4), 4 divizori (pentru valoarea 10), 4 divizori (pentru valoarea 6) şi 2 divizori (pentru valoarea 5).
Se pot forma grupele: cu 2 divizori (elementele 2, 5), cu 4 divizori (elementele 10, 6), cu 3 divizori (elementul 4) şi cu 5 divizori (elementul 16). După ordonarea descrescătoare a grupelor, grupele cu cele mai multe elemente sunt cele care conţin 2 elemente: (10, 6), respectiv (2, 5). Pentru că elementele 10 şi 6 au 4 divizori, ele vor face parte din grupa A, iar 2 şi 5, având doar 2 divizori fiecare, vor face parte din grupa B. Deci grupa A are 4 divizori, 2 elemente şi cel mai mare element din grupă este 10, iar grupa B are 2 divizori, 2 elemente şi cel mai mare element din grupă este 5.
Exemplul 2
- Intrare
- grupein.txt
- 2 3
- 2 15 4
- 10 6 5
- Ieșire
- Datele de intrare corespund restricțiilor impuse
- 4 3 15
- 2 2 5
Explicație
Numărul divizorilor pentru fiecare element al tabloului: 2 divizori (pentru valoarea 2), 4 divizori (pentru valoarea 15), 3 divizori (pentru valoarea 4), 4 divizori (pentru valoarea 10), 4 divizori (pentru valoarea 6) şi 2 divizori (pentru valoarea 5).
După ordonarea descrescătoare a grupelor, grupa cu cele mai multe elemente este cea formată din elementele 10, 6, 15, fiecare element având exact 4 divizori. Aceasta va fi grupa A. Grupa B va fi cea formată din două elemente, celelaltă grupă având un singur element. Deci grupa A are 4 divizori, 3 elemente şi cel mai mare element din grupă este 15, iar grupa B are 2 divizori, 2 elemente şi cel mai mare element din grupă este 5.
Exemplul 3
- Intrare
- grupein.txt
- 2 101
- 16 2 4
- 10 6 5
- Ieșire
- Datele de intrare NU corespund restricțiilor impuse
Rezolvare
#1076 - Grupe
def validare_input(m, n, elemente):
if not (0 < m < 101 and 0 < n < 101):
return False
if len(elemente) != m:
return False
for linie in elemente:
if len(linie) != n:
return False
for element in linie:
if not (1 < element <= 100000):
return False
return True
def numara_divizorii(numar):
divizori = 0
for i in range(1, numar + 1):
if numar % i == 0:
divizori += 1
return divizori
def main():
with open("grupein.txt", "r") as fisier:
m, n = map(int, fisier.readline().split())
elemente = [list(map(int, fisier.readline().split())) for _ in range(m)]
if validare_input(m, n, elemente):
print("Datele de intrare corespund restricțiilor impuse")
grupe = {}
for linie in elemente:
for element in linie:
divizori = numara_divizorii(element)
if divizori not in grupe:
grupe[divizori] = []
grupe[divizori].append(element)
grupe_sortate = sorted(grupe.items(), key=lambda x: (len(x[1]), max(x[1])), reverse=True)
grupa_a = grupe_sortate[0]
grupa_b = grupe_sortate[1] if len(grupe_sortate) > 1 else (0, [])
with open("grupeout.txt", "w") as fisier_iesire:
fisier_iesire.write(f"{grupa_a[0]} {len(grupa_a[1])} {max(grupa_a[1])}\n")
fisier_iesire.write(f"{grupa_b[0]} {len(grupa_b[1])} {max(grupa_b[1])}\n")
else:
print("Datele de intrare NU corespund restricțiilor impuse")
exit(0)
if __name__ == "__main__":
main()
