3707 - forta1

Cerința

Definim forța unui element într-un șir ca fiind valoarea obținută considerând numărul de cifre pe care el le are în comun cu fiecare din celelalte elemente ale șirului și însumând aceste valori. De exemplu în șirul (12131, 1243, 15141) elementul 12131 are forța 6, deoarece 12131 are în comun cu 1243 trei cifre (1, 2 și 3) iar cu 15141 are în comun trei cifre (cele 3 cifre 1). Se dă un șir cu n elemente numere naturale. Să se sorteze elementele din șir în ordine crescătoare a forței, iar acele elemente care au aceeași forță să apară în ordine inversă decât apăreau inițial în șir.

Date de intrare

Fișierul de intrare forta.in conține pe prima linie n, numărul de elemente din șir, iar pe a doua linie n numere naturale separate prin câte un spațiu, reprezentând elementele șirului.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect." Fișierul de ieșire forta.out va conține pe prima linie, separate prin câte un spațiu, elementele șirului în ordinea cerută. În cazul în care datele nu respectă restricțiile, se va afișa: "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări

• 1 ≤ n ≤ 1000
• elementele șirului sunt numere naturale mai mici sau egale cu 1018
• pentru teste în valoare de 30 de puncte elementele șirului vor avea forțe distincte

Exemple

Exemplul 1

forta.in

4

123 121 12314 1234

ecran

Datele sunt introduse corect.

forta.out

121 123 1234 12314

Exemplul 2

forta.in

5

2 3 5 7 11

ecran

Datele sunt introduse corect.

forta.out

11 7 5 3 2

Exemplul 3

forta.in

4

-3 2 3 5

ecran

Datele nu corespund restricțiilor impuse.

forta.out

Rezolvare

# 3707 - forta1
def validare_date(numar_elemente, valori, distincte=False):
    if numar_elemente <= 0 or not all(isinstance(x, int) and x > 0 and x <= 10 ** 18 for x in valori):
        return False
    if distincte and len(set(valori)) != numar_elemente:
        return False
    return True


def rezolvare_problema(numar_elemente, valori):
    class Forta:
        def __init__(self, valoare, frecventa, pozitie):
            self.valoare = valoare
            self.frecventa = frecventa
            self.pozitie = pozitie

    def contor(nr1, nr2):
        frecventa1, frecventa2, cnt = [0] * 10, [0] * 10, 0
        while nr1:
            frecventa1[nr1 % 10] += 1
            nr1 //= 10
        while nr2:
            frecventa2[nr2 % 10] += 1
            nr2 //= 10
        for i in range(10):
            if frecventa1[i] and frecventa2[i]:
                cnt += min(frecventa1[i], frecventa2[i])
        return cnt

    forte = [Forta(valoare=valori[i], frecventa=0, pozitie=i) for i in range(numar_elemente)]
    for i in range(numar_elemente - 1):
        for j in range(i + 1, numar_elemente):
            suma_comuna = contor(forte[i].valoare, forte[j].valoare)
            forte[i].frecventa += suma_comuna
            forte[j].frecventa += suma_comuna

    for i in range(numar_elemente - 1):
        for j in range(i + 1, numar_elemente):
            if forte[i].frecventa > forte[j].frecventa:
                forte[i], forte[j] = forte[j], forte[i]
            elif forte[i].frecventa == forte[j].frecventa:
                if forte[i].pozitie < forte[j].pozitie:
                    forte[i], forte[j] = forte[j], forte[i]

    return [forta.valoare for forta in forte]


if __name__ == "__main__":
    with open("forta.in", "r") as fin:
        numar_elemente = int(fin.readline())
        valori = list(map(int, fin.readline().split()))

    if not validare_date(numar_elemente, valori, distincte=True):
        print("Datele nu corespund restricțiilor impuse.")
        exit(0)

    print("Datele sunt introduse corect.")
    rezultat = rezolvare_problema(numar_elemente, valori)
    with open("forta.out", "w") as fout:
        fout.write(" ".join(map(str, rezultat)))

Explicatie

validare_date(n, v, distincte=False): Această funcție primește două argumente de intrare, numărul n și lista de numere întregi v, și returnează True dacă acestea sunt valide și False altfel. Verificările includ verificarea ca n să fie un număr întreg pozitiv și ca fiecare element din lista v să fie un număr întreg pozitiv mai mic sau egal cu 10^18. Argumentul opțional distincte specifică dacă toate elementele din lista v trebuie să fie distincte sau nu.

rezolvare_problema(n, v): Această funcție primește două argumente de intrare, numărul n și lista de numere întregi v, și rezolvă problema descrisă în enunțul problemei. Funcția construiește o listă de obiecte Forta pentru fiecare element din lista v, fiecare obiect conținând valoarea elementului val, numărul de perechi de cifre comune cu alte numere din listă fr, și poziția sa în lista poz. Apoi, funcția calculează numărul de perechi de cifre comune pentru fiecare pereche posibilă de numere din listă și actualizează câmpul fr pentru fiecare obiect Forta. La final, lista de obiecte Forta este sortată în ordinea descrescătoare a valorii fr și a poziției poz, și valorile val ale obiectelor sunt extrase într-o listă separată, care este returnată de funcție.

main(): Această funcție este punctul de intrare în program și se ocupă de citirea datelor din fișierul de intrare, apelarea funcției validare_date() pentru a verifica dacă datele sunt valide, apelarea funcției rezolvare_problema() pentru a rezolva problema descrisă în enunțul problemei și afișarea rezultatului în fișierul de ieșire. Dacă datele nu sunt valide, programul se va termina cu exit(0).