1963 - OP

Enunț

Șcuțu este un mare matematician. Într-o seară acesta a inventat operația ∆. Operația ∆ se aplică pe 2 numere naturale, astfel:

290 ∆ 345 = 290345
21 ∆ 12 = 2112
456 ∆ 0 = 4560

Mygo și Seba sunt la rândul lor foarte buni informaticieni. Aceștia au un vector A cu N elemente, numere naturale, indexate de la 1. Ei vor construi un nou vector V, acesta la rândul său indexat de la 1, ce conține fiecare valoare A[i] ∆ A[j] (1 ≤ i, j ≤ N) pe care îl vor sorta crescător.

Cerința

Acum Șcuțu le va pune celor 2 câte două întrebări:

1. Câte valori din V sunt mai mici sau egale cu X ?
2. Pentru X dat, ce valoare se află pe poziția X ?

Să se răspundă la cele 2 întrebări.

Date de intrare

Fișierul de intrare opin.txt conține pe prima linie numărul t, având valoarea 1 sau 2, reprezentând tipul întrebării la care se cere răspunsul. Pe a doua linie linie se află numărul N și X iar pe a treia linie se vor afla N numere naturale nenule, reprezentând valorile vectorului A.

Date de ieșire

Fișierul de ieșire opout.txt va conține pe prima linie numărul S, reprezentând răspunsul întrebării.

Restricții și precizări

• 1 ⩽ N ⩽ 100.000
• numerele de pe a treia linie a fișierului de intrare vor fi mai mici decât 1.000.000.000

Exemplul 1

Intrare

opin.txt

1

3 23

1 2 4

Ieșire

Datele de intrare corespund restricțiilor impuse

opout.txt

5

Explicație

V = {11, 12, 14, 21, 22, 24, 41, 42, 44}. Sunt 5 numere mai mici decât 23.

Exemplul 2

Intrare

opin.txt

2

3 6

1 2 4

Ieșire

Datele de intrare corespund restricțiilor impuse

opout.txt

24

Explicație

V = {11, 12, 14, 21, 22, 24, 41, 42, 44}. Pe poziția 6 se află numărul 24.

Exemplul 3

Intrare

opin.txt

3

3 6

1 2 4

Ieșire

Datele de intrare NU corespund restricțiilor impuse

Rezolvare

<syntaxhighlight lang="python" line>

1. 1963 - Op

def valideaza_input(t, n, a):

   if t not in [1, 2]:
       return False
   if not 1 <= n <= 100000:
       return False
   if not all(0 < ai < 1000000000 for ai in a):
       return False
   return True

def calculeaza_v(n, a):

   v = []
   for i in range(n):
       for j in range(n):
           v.append(int(str(a[i]) + str(a[j])))
   return sorted(v)

def numara_valori_mai_mici_sau_egale_cu_x(v, x):

   count = 0
   for value in v:
       if value <= x:
           count += 1
   return count

def gaseste_valoare_pe_pozitia_x(v, x):

   return v[x - 1]

if __name__ == "__main__":

   rezultat = 0
   with open("opin.txt", "r") as file:
       t = int(file.readline().strip())
       n, x = map(int, file.readline().strip().split())
       a = list(map(int, file.readline().strip().split()))

   if valideaza_input(t, n, a):
       print("Datele de intrare corespund restricțiilor impuse")
       if t == 1:
           v = calculeaza_v(n, a)
           rezultat = numara_valori_mai_mici_sau_egale_cu_x(v, x)
       elif t == 2:
           v = calculeaza_v(n, a)
           rezultat = gaseste_valoare_pe_pozitia_x(v, x)
   else:
       print("Datele de intrare NU corespund restricțiilor impuse")
       exit(0)

   with open("opout.txt", "w") as output_file:
       output_file.write(str(rezultat))

</syntaxhighlight>