2447 - Forus
Sursa: [1]
Cerinţa[edit | edit source]
La ora de educație tehnologică a clasei a V-a profesorul Forus, pasionat de matematică, a adus pentru fiecare dintre cei N elevi câte un carton pe care este scris câte un număr natural nenul. Fiecare elev poate folosi cartonul așa cum l-a primit sau poate să taie o singură dată cartonul între două cifre și să lipească partea stângă la finalul părții drepte. Elevul NU are voie să facă o tăietură în fața cifrei 0, deci niciunul dintre numerele obținute NU poate să înceapă cu cifra 0. Dintre toate numerele pe care le poate obține, elevul îl alege pe cel care are număr minim de divizori, iar dacă poate obține mai multe astfel de numere, îl alege pe cel mai mic dintre ele. La sfârșitul orei, profesorul strânge cartoanele cu numerele alese, în ordinea distribuirii lor. De exemplu, dacă inițial elevul primește cartonul cu numărul 25082 atunci el are doar următoarele trei variante de tăiere și lipire:
- 2 5082 => 50822
- 250 82 => 82250
- 2508 2 => 22508
Scrieţi un program care citeşte numărul natural N și cele N numere scrise pe cartoanele aduse de profesorul Forus, apoi rezolvă următoarele două cerinţe:
1. determină numărul de cartoane pe care elevii au voie să le taie de oriunde (NU conțin cifre în fața cărora NU au voie să taie);
2. determină, în ordinea strângerii cartoanelor, numerele preluate de către profesorul Forus la finalul orei.
Date de intrare[edit | edit source]
Fișierul de intrare forus.in conține pe prima linie un număr natural C reprezentând cerința din problemă care trebuie rezolvată (1 sau 2). A doua linie din fișier conține un număr natural N, reprezentând numărul de elevi, iar a treia linie din fișier conţine N numere naturale, separate prin câte un spațiu, reprezentând numerele scrise pe cartoanele aduse de profesor, în ordinea distribuirii lor.
Date de ieșire[edit | edit source]
Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi: * Dacă C = 1, fişierul de ieşire forus.out conţine pe prima linie un număr natural reprezentând răspunsul la cerinţa 1.
- Dacă C = 2, fişierul de ieşire forus.out conţine pe prima linie N numere naturale, separate prin câte un spațiu, reprezentând răspunsul la cerința 2; numerele sunt scrise în ordinea în care au fost strânse.
În caz contrar, pe ecran se va afișa: "Datele nu au fost introduse corect."
Restricţii şi precizări[edit | edit source]
- 2 ≤ N ≤ 30
- 1 ≤ numărul natural de pe carton < 1 000 000 000;
Exemple[edit | edit source]
Exemplul 1[edit | edit source]
- forus.in
- 1
- 5
- 1234 25082 543 52 150
- Ecran
- Datele sunt introduse corect.
- forus.out
- 3
Exemplul 2[edit | edit source]
- forus.in
- 2
- 5
- 51 1234 50822 345 150
- Ecran
- Datele sunt introduse corect.
- forus.out
- 15 2341 25082 453 501
Rezolvare[edit | edit source]
<syntaxhighlight lang="python" line>
- 2447
def verificare_date(N, cartoane):
if not (1 <= N <= 30):
return False
for c in cartoane:
if not (1 <= c < 1000000000):
return False
if str(c)[0] == '0':
return False
return True
def numar_divizori(n):
divizori = 0
for i in range(1, int(n**0.5) + 1):
if n % i == 0:
divizori += 2 if i != n // i else 1
return divizori
def taie_carton(c):
cartoane = []
for i in range(1, len(str(c))):
if str(c)[i] != '0':
carton = int(str(c)[i:] + str(c)[:i])
if str(carton)[0] != '0':
cartoane.append(carton)
return cartoane
def rezolvare_cerinta1(cartoane):
nr_cartoane = 0
for c in cartoane:
if len(taie_carton(c)) > 0:
nr_cartoane += 1
return nr_cartoane
def rezolvare_cerinta2(cartoane):
rezultat = []
for c in cartoane:
variante = taie_carton(c)
if len(variante) > 0:
min_div = numar_divizori(variante[0])
min_carton = variante[0]
for v in variante:
if numar_divizori(v) < min_div:
min_div = numar_divizori(v)
min_carton = v
elif numar_divizori(v) == min_div and v < min_carton:
min_carton = v
rezultat.append(min_carton)
else:
rezultat.append(c)
return rezultat
if __name__ == '__main__':
with open('forus.in', 'r') as f:
cerinta = int(f.readline())
N = int(f.readline())
cartoane = list(map(int, f.readline().split()))
if verificare_date(N, cartoane):
print("Datele au fost introduse corect.")
if cerinta == 1:
rezultat = rezolvare_cerinta1(cartoane)
with open('forus.out', 'w') as f:
f.write(str(rezultat))
elif cerinta == 2:
rezultat = rezolvare_cerinta2(cartoane)
with open('forus.out', 'w') as f:
f.write(' '.join(map(str, rezultat)))
else:
print('Datele nu au fost introduse corect.')
</syntaxhighlight>
Explicație rezolvare[edit | edit source]
Funcția verificare_date primește două argumente, un număr întreg N și o listă de numere întregi cartoane. Scopul acestei funcții este de a verifica dacă datele de intrare sunt valide, returnând True dacă sunt valide și False în caz contrar. Aceasta verifică mai întâi dacă N este între 1 și 30, apoi verifică fiecare element din lista cartoane pentru a se asigura că este între 1 și 1.000.000.000 și că nu începe cu zero.
Funcția numar_divizori primește un număr întreg n și calculează numărul de divizori ai acestuia. Algoritmul utilizat în această funcție este de a itera prin numerele de la 1 la rădăcina pătrată a lui n și de a verifica dacă fiecare număr divide n. Dacă este adevărat, se adaugă 2 la numărul de divizori (deoarece atât numărul cât și divizorul sunt divizori) sau 1 dacă numărul este pătrat perfect (adică divizorul este egal cu rădăcina pătrată a lui n).
Funcția taie_carton primește un număr întreg c și returnează o listă de toate variantele de numere obținute prin tăierea și lipirea cartonului c. Aceasta începe prin a itera prin cifrele numărului c, începând cu cea de-a doua cifră și obținând toate variantele de numere prin rearanjarea cifrelor. Variantele care încep cu zero sunt excluse din listă.
Funcția rezolvare_cerinta1(cartoane) primește o listă de numere întregi, reprezentând dimensiunile cartoanelor. Funcția calculează numărul de cartoane care pot fi tăiate de oriunde și returnează rezultatul. Se initializează un contor nr_cartoane la zero și se parcurge lista de cartoane folosind un for loop. Pentru fiecare carton c, se apelează funcția taie_carton(c) care returnează o listă cu dimensiunile posibile după tăierea cartonului c. Dacă lista are lungimea mai mare de zero, adică există cel puțin o variantă de dimensiuni diferite de cartonul inițial, se incrementează nr_cartoane. La final, se returnează nr_cartoane.
Funcția rezolvare_cerinta2(cartoane) primește de asemenea o listă de numere întregi, reprezentând dimensiunile cartoanelor. Funcția returnează o listă cu numerele preluate de profesor în ordinea în care au fost strânse. Se parcurge lista de cartoane folosind un for loop. Pentru fiecare carton c, se apelează funcția taie_carton(c) care returnează o listă cu dimensiunile posibile după tăierea cartonului c. Dacă lista are lungimea mai mare de zero, se determină cartonul cu numărul minim de divizori și cu cel mai mic număr, apoi se adaugă la lista rezultat. Pentru a determina cartonul cu numărul minim de divizori, se inițializează min_div cu numărul de divizori ai primei variante, min_carton cu prima variantă de carton și se parcurge lista de variante, comparând numărul de divizori și numărul cartonului curent cu minimul curent. Dacă numărul de divizori al unui carton curent este mai mic decât minimul curent, se actualizează min_div și min_carton. Dacă numărul de divizori este egal cu minimul curent, se compară numărul curent cu cel minim și se actualizează min_carton dacă este mai mic. Dacă lista de variante este goală, adică cartonul inițial nu poate fi tăiat, se adaugă cartonul inițial la lista rezultat. La final, se returnează rezultat.
În funcția principală se citesc datele din fișierul de intrare forus.in, iar dacă acestea nu sunt valide, se va afișa un mesaj de eroare. În caz contrar, în funcție de numărul cerinței din fișierul de intrare, se realizează funcțiile necesare, iar rezultatul va fi afișat în fișierul forus.out.