Editing 2447 - Forus

Sursa: [https://www.pbinfo.ro/probleme/2447/forus]
----
== Cerinţa ==
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
<br>
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 ==
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 == 
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 ==
* '''2 ≤ N ≤ 30'''
* '''1 ≤ numărul natural de pe carton < 1 000 000 000''';

== Exemple ==
===Exemplul 1===
; forus.in
: 1
: 5
: 1234 25082 543 52 150
; Ecran
: Datele sunt introduse corect.
; forus.out
: 3
===Exemplul 2===
; forus.in
: 2
: 5
: 51 1234 50822 345 150
; Ecran
: Datele sunt introduse corect.
; forus.out
: 15 2341 25082 453 501


== Rezolvare == 
<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 ==
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.<br><br> 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).<br><br> 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ă.<br><br>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.<br><br>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'''.<br><br>  Î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'''.