2931 - Parap

Cerința

Se dau N numere naturale a1,a2…an

. O pereche (a[j],a[k]) cu 1≤j<k≤N se numește pereche specială dacă are proprietatea că din a[j] și a[k] prin “lipire” se formează un număr X în care cifrele conținute apar de număr par de ori. De exemplu numerele 123 şi 21223 dacă se lipesc produc numărul 12321223 în care 1 apare de 2 ori, 2 apare de 4 ori și 3 apare de 2 ori.

Să se determine numărul perechilor speciale.

Date de intrare

Pe primul rând al fișierului text parap.in se află numărul natural N reprezentând numărul de elemente ale șirului dat. Pe al doilea rând, separate prin câte un spațiu se află elementele șirului dat.

Date de ieșire

Pe primul rând în fișierul de ieșire parap.out se va scrie un număr natural reprezentând numărul perechilor speciale.

Restricții și precizări

• 2 ≤ N ≤ 100.000
• 1 ≤ a[k] ≤ 1018

Exemplu:

parapin.txt

10

4 1 13 5 42 2 1 2 112 212

parapout.txt

6

Explicație

Perechile speciale sunt (1,1),(1,212),(2,2),(2,112),(1,212),(2,112).

Rezolvare

def validate_input(N, values):
    if not (2 <= N <= 100000):
        print("Eroare: N trebuie să fie între 2 și 100000.")
        return False

    for val in values:
        if not (1 <= val <= 10**18):
            print(f"Eroare: Valoarea {val} nu este în intervalul permis.")
            return False

    return True
def trans(x):
    w = [0] * 12
    sol = 0
    p = 1

    while x != 0:
        w[x % 10] += 1
        x //= 10

    for i in range(10):
        sol += p * (w[i] % 2)
        p *= 2
        w[i] = 0

    return sol

def main():
    with open("parapin.txt", "r") as in_file, open("parapout.txt", "w") as out_file:
        n = int(in_file.readline().strip())
        v = [0] * (n + 1)
        vf = [0] * 10002
        sol = 0

        numbers = map(int, in_file.readline().split())

        for i in range(1, n + 1):
            x = next(numbers)
            v[i] = trans(x)
            sol += vf[v[i]]
            vf[v[i]] += 1

        out_file.write(str(sol))

if __name__ == "__main__":
    main()