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

<syntaxhighlight lang="python"> 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()

</syntaxhighlight>