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

#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))