4084 - pseudocmp

Cerința

Àles a primit ca temă următoarea problemă: “Fiind dat un șir A cu N numere naturale distincte, să se calculeze suma cifrelor fiecărui element al șirului”.

După ce și-a terminat tema, acesta observă că sunt mai multe perechi de indici (i, j) pentru care dacă A[i] < A[j] atunci S[i] > S[j], unde S[i] reprezintă suma cifrelor lui A[i]. El le va numi pe acestea perechi speciale de indici. Terminând prea repede tema, Àles primește o temă suplimentară cu două cerințe:

Determină două numere aflate în șirul A, pentru care indicii corespunzători formează o pereche specială. Câte perechi speciale de indici (i, j) se găsesc în şirul A? Ajutați-l pe Àles să rezolve tema suplimentară.

Date de intrare

Pe prima linie a fișierului pseudocmp.in se găsesc două numere naturale: T și N. Pe următoarea linie se găsesc N numere naturale, separate printr-un spațiu, reprezentând valorile din șirul A. Numărul T reprezintă numărul cerinței.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran: "Datele sunt introduse corect.", Pe prima linie a fișierului pseudocmp.out:

Dacă T = 1, se găsesc două numere naturale x, y, cu x < y, separate printr-un spațiu, reprezentând răspunsul pentru cerința 1 dacă există soluție sau -1, dacă nu există soluție. Dacă există mai multe soluții, se acceptă oricare dintre acestea. Dacă T = 2, se găsește un singur număr natural, reprezentând răspunsul la cerința 2. Î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 ≤ 100.000
• 1 ≤ A[i] ≤ 1.000.000, pentru 1 ≤ i ≤ N

Exemple

Exemplul 1

pseudocmp.in

1 6

213 123 523 51 99 92

ecran

Datele sunt introduse corect.

pseudocmp.out

99 123

Exemplul 2

pseudocmp.in

1 5

6 5 2 1 3

ecran

Datele sunt introduse corect.

pseudocmp.out

-1

Exemplul 3

pseudocmp.in

1 5

60000000 5 2 1 3

ecran

Datele nu corespund restricțiilor impuse.

Rezolvare

# 4084 - pseudocmp
def valideaza_date(T, N, A):
    if T != 1 and T != 2:
        return False
    if not (1 <= N <= 100000):
        return False
    if not all(1 <= val <= 1000000 for val in A):
        return False
    return True


def rezolva_cerinta1(n, v):
    v.sort(key=lambda x: x['val'])
    for i in range(1, n):
        if v[i]['sumcif'] < v[i - 1]['sumcif']:
            return v[i - 1]['val'], v[i]['val']
    return -1


def rezolva_cerinta2(n, v):
    f = [0] * 60
    cnt = 0
    for i in range(n):
        s = v[i]['sumcif']
        for j in range(s + 1, 60):
            cnt += f[j]
        f[s] += 1
    return cnt


if __name__ == '__main__':
    with open("pseudocmp.in", "r") as fisier_intrare:
        T, N = map(int, fisier_intrare.readline().strip().split())
        A = list(map(int, fisier_intrare.readline().strip().split()))

    if valideaza_date(T, N, A):
        print("Datele sunt introduse corect.")
        v = []
        for valoare in A:
            suma_cifre = sum(map(int, str(valoare)))
            v.append({'val': valoare, 'sumcif': suma_cifre})

        if T == 1:
            rezultat = rezolva_cerinta1(N, v)
        else:
            rezultat = rezolva_cerinta2(N, v)

        with open("pseudocmp.out", "w") as fisier_iesire:
            if rezultat == -1:
                fisier_iesire.write(str(rezultat))
            else:
                fisier_iesire.write("{}\n".format(rezultat))
    else:
        print("Datele nu corespund restricțiilor impuse.")

Explicatie

valideaza_date(T, N, A): Această funcție validează datele de intrare în funcție de constrângerile date. Are trei parametri: T (valoarea T din intrare), N (valoarea N din intrare) și A (lista de valori din intrare). Funcția verifică dacă T este fie 1, fie 2, dacă N se află în intervalul 1 până la 100.000 și dacă toate valorile din A se află în intervalul 1 până la 1.000.000. Dacă una dintre condiții nu este îndeplinită, funcția returnează False, indicând că datele sunt invalide. În caz contrar, returnează True, indicând că datele sunt valide.

rezolva_cerinta1(n, v): Această funcție rezolvă problema pentru T = 1. Are doi parametri: n (lungimea listei de intrare v) și v (lista de dicționare care conține valorile și suma cifrelor lor). Funcția sortează lista v în funcție de valorile din ordine crescătoare. Apoi, iterează prin lista sortată și verifică dacă suma cifrelor valorii curente este mai mică decât suma cifrelor valorii anterioare. Dacă este, returnează o pereche de valori formată din valoarea anterioară și valoarea curentă. Dacă nu se găsește nicio pereche de acest fel, returnează -1.

rezolva_cerinta2(n, v): Această funcție rezolvă problema pentru T = 2. Are doi parametri: n (lungimea listei de intrare v) și v (lista de dicționare care conține valorile și suma cifrelor lor). Funcția inițializează o listă f cu 60 de zerouri. Apoi, iterează prin lista v și actualizează variabila cnt numărând numărul de elemente cu sume diferite de cifre care apar după elementul curent. Pentru aceasta, folosește lista f pentru a stoca frecvența fiecărei sume de cifre întâlnite până în acel moment. Adaugă frecvențele sumelor de cifre mai mari decât suma cifrelor elementului curent la variabila cnt. În cele din urmă, returnează valoarea totală a variabilei cnt.

Această secțiune a codului verifică dacă datele de intrare sunt valide folosind funcția valideaza_date. Dacă datele sunt valide, afișează mesajul "Datele sunt introduse corect." Apoi, se construiește lista v care conține dicționare cu valorile și suma cifrelor asociate din lista A. În funcție de valoarea lui T, se apelează funcția rezolva_cerinta1 sau rezolva_cerinta2 și rezultatul este stocat în variabila rezultat. În cele din urmă, rezultatul este scris în fișierul de ieșire "pseudocmp.out", urmând formatarea specificată. Dacă rezultatul este -1, se va scrie -1 în fișierul de ieșire, în caz contrar, se va scrie rezultatul urmat de un caracter newline pentru a crea o nouă linie în fișierul de ieșire.