2136 - Peste

Cerința

Ursul: Bună, cumătră! Da cât peşte ai? Dă-mi şi mie, că tare mi-i poftă!

Vulpea: Ia mai pune-ţi pofta-n cui. Dacă vrei pește, du-te şi-ţi înmoaie coada-n baltă şi vei avea ce să mănânci.

Ursul: Învaţă-mă, te rog, cumătră, că eu nu ştiu cum se prinde peştele.

Vulpea: Alei, cumetre! da’ nu ştii că nevoia te-nvaţă ce nici nu gândeşti? Du-te deseară la baltă și bagă-ţi coada-n apă. Stai pe loc, fără să te mişti, până spre ziuă. Între timp, ia foaia aceasta pe care am scris N numere naturale și până dimineață trebuie să procedezi în felul următor:

• elimini exact două cifre alăturate din fiecare număr scris pe foaie, astfel încât, celelalte cifre rămase după eliminare să formeze, de la stânga la dreapta, cel mai mare număr posibil (de exemplu, din numărul 77196, elimini cifrele 7 și 1 pentru a obține cel mai mare număr posibil 796).
• toate cele N numere obținute la pasul anterior, le lipești unul după altul, în ce ordine vrei tu. Uitându-te de la stânga la dreapta la cifrele numerelor lipite, observi că s-a format un nou număr X. Ai grijă cum procedezi, căci până dimineață, atâta pește se va prinde de coada ta cât vei obține tu valoarea lui X.

Ajutați-l pe urs să prindă cât mai mult pește posibil. Scrieți un program care citește N numere naturale și determină:

1. Cel mai mare număr de eliminări efectuate cu aceleași două cifre alăturate.
2. Cel mai mare număr natural X determinat astfel încât ursul să prindă cât mai mult pește.

Date de intrare

Fișierul de intrare peste.in conține pe prima linie numărul natural P care poate avea valoarea 1 sau 2 și reprezintă numărul cerinței. Cea de-a doua linie conține un număr natural N cu semnificaţia din enunţ, iar pe următoarele N linii, cele N numere scrise pe foaia ce i-a dat-o vulpea ursului, câte un număr natural pe fiecare linie a fișierului.

Date de ieșire

Pe ecran se va afișa mesajul: "Datele de intrare corespund restricțiilor impuse."

Pe următorul rând se va afișa un singur număr natural determinat conform cerinței problemei.

În cazul în care datele introduse de la tastatură nu îndeplinesc cerințele enunțate, pe ecran se va afișa mesajul "Datele de intrare nu corespund restricțiilor impuse."

Restricții și precizări

• 1 ≤ n ≤ 100, fiecare dintre cele N numere au cel puțin 3 și cel mult 18 cifre;

Exemplu 1

Intrare

1

4

1791

802

777

77196

Ieșire

Datele de intrare corespund restricțiilor impuse.

2

Explicație

Se va rezolva cerința 1 și în fișier sunt patru numere cu care vom proceda astfel:

• din 1791 eliminăm cifrele 1 și 7 iar numărul rezultat este 91
• din 802 eliminăm cifrele 0 și 2 iar numărul rezultat este 8
• din 777 eliminăm cifrele 7 și 7 iar numărul rezultat este 7
• din 77196 eliminăm 7 și 1 iar numărul rezultat este 796

S-au efectuat două eliminări cu aceleași două cifre alăturate: 1 și 7.

Exemplu 2

Intrare

2

4

1791

802

777

77196

Ieșire

Datele de intrare corespund restricțiilor impuse.

9187967

Explicație

Cu aceleași patru numere din exemplul precedent, vom rezolva cerința 2.

În urma eliminărilor efectuate s-au obținut numerele: 91 8 7 796

Cel mai mare număr posibil, obținut prin lipirea acestor numere este 9187967.

Exemplu 3

Intrare

2 4

22

802

777

123456196

Ieșire

Datele de intrare nu corespund restricțiilor impuse.

Rezolvare

#2136 Peste
def conditii(nums):
    if not 1 <= len(nums) <= 100:
        return False

    for nr in nums:
        if not 3 <= len(str(nr)) <= 18:
            return False

    return True


def inlatura(num):
    # list() transformă un string într-o listă de caractere
    cifre = list(num)
    nr_max = 0
    cifre_sterse = []

    # Iterăm peste perechi de cifre adiacente și le eliminăm pentru a găsi numărul maxim
    for i in range(len(cifre)-1):
        # Identificăm cifrele adiacente de eliminat și le stocăm într-o listă
        stergere = [min(cifre[i], cifre[i + 1]), max(cifre[i], cifre[i + 1])]
        # Creăm o nouă listă, excluzând cifrele eliminate
        # Pentru fiecare cifră din listă, dacă indicele ei nu este i sau i+1, o adăugăm în noua listă
        cifre_ramase = [cif for idx, cif in enumerate(cifre) if idx not in [i, i + 1]]
        # Convertim cifrele rămase într-un număr întreg pentru a găsi numărul maxim
        nr_obtinut = int(''.join(cifre_ramase))
        # Dacă numărul maxim obținut este mai mare decât numărul maxim anterior,
        # actualizăm cifrele stocate și numărul maxim
        if nr_obtinut > nr_max:
            cifre_sterse = stergere
            nr_max = nr_obtinut

    return cifre_sterse, nr_max


def nr_eliminari(cifre_eliminate):
    # Găsim cifra care a fost eliminată de cele mai multe ori
    return max(
        set([elem for sublist in cifre_eliminate for elem in sublist]),
        key=cifre_eliminate.count
    )


def cel_mai_mare(numere_maxime):
    # Sortăm în ordine descrescătoare și le concatenăm
    numere_sortate = sorted(numere_maxime, reverse=True)
    result = ''.join(numere_sortate)
    return result


def peste(p, numere):
    cifre_eliminate = []
    numere_maxime = []

    # Pentru fiecare număr, eliminăm cifrele adiacente și găsim numărul maxim în urma înlăturării
    for nr in numere:
        cifre_sterse, nr_maxim = inlatura(nr)
        # Adăugăm cifrele eliminate și numărul maxim în listele separate
        cifre_eliminate.append(cifre_sterse)
        numere_maxime.append(str(nr_maxim))

    # p este cerința problemei
    if p == 1:
        print(nr_eliminari(cifre_eliminate))
    if p == 2:
        print(cel_mai_mare(numere_maxime))


if __name__ == "__main__":
    p = int(input())
    n = int(input())
    numere = []
    for i in range(n):
        numere.append(input())

    if not conditii(numere):
        print("Datele de intrare nu corespund restricțiilor impuse.")
    else:
        print("Datele de intrare corespund restricțiilor impuse.")
        peste(p, numere)