2733 - nrapp

Cerința

Se dă un număr natural N si un șir v de N numere naturale. Sa se răspundă la Q întrebări de tipul:

D y: Care este cea mai mică poziție x, unde x > y, pentru care v[x] < v[y]? Dacă nu există o astfel de poziție, răspunsul acestei întrebări va fi N + 1. S y: Care este cea mai mare poziție x, unde x < y, pentru care v[x] < v[y]? Dacă nu există o astfel de poziție, răspunsul acestei întrebări va fi 0.

Date de intrare

Fișierul de intrare nrappin.txt conține pe prima linie numărul natural N, iar pe a doua linie N numere naturale separate prin spații. A treia linie va conține numărul natural nenul Q și apoi Q întrebări precum cele descrise anterior.

Date de ieșire

Fișierul de ieșire nrappout.txt va conține Q linii, anume răspunsul pentru fiecare întrebare în parte.

Restricții și precizări

• 1 ≤ N ≤ 100.000
• 1 ≤ v[i] ≤ 1.000.000

Exemplul 1:

nrappin.txt

8
1 3 6 5 2 1 9 6
8
S 1
D 2
D 3
S 4
S 5
D 6
D 7
D 8

nrappout.txt

Datele de intrare corespund restrictiilor impuse
0
5
4
2
1
9
8
9

Exemplul 2:

nrappin.txt

nrapp

nrappout.txt

Datele de intrare nu corespund restrictiilor impuse

Rezolvare

def validare(n, sir_v, q, intrebari, file_output):           # functia de validare a datelor de intrare
    if not 1 <= n <= 100000:
        raise ValueError
    for val in sir_v:
        if not 1 <= val <= 1000000:    # fiecare element trebuie sa fie numar intreg intre 1 si 1.000.000
            raise ValueError
    if q < 1:
        raise ValueError
    for intrebare in intrebari:
        if len(intrebare) != 2 or not isinstance(intrebare[1], int):
            raise ValueError
    file_output.write("Datele de intrare corespund restrictiilor impuse\n")


def solve(n, sir_v, intrebari):                     # functia de rezolvare
    raspunsuri = []
    for intrebare in intrebari:
        if intrebare[0] == 'D':
            y = intrebare[1]
            raspuns = n + 1
            for x in range(y + 1, n + 1):
                if sir_v[x - 1] < sir_v[y - 1]:
                    raspuns = x
                    break
            raspunsuri.append(raspuns)
        elif intrebare[0] == 'S':
            y = intrebare[1]
            raspuns = 0
            for x in range(y - 1, 0, -1):
                if sir_v[x - 1] < sir_v[y - 1]:
                    raspuns = x
                    break
            raspunsuri.append(raspuns)
    return raspunsuri


if __name__ == '__main__':
    file_in = open('nrappin.txt', 'r')
    file_out = open('nrappout.txt', 'w')

    try:
        N = int(file_in.readline())
        v = list(map(int, file_in.readline().split()))
        Q = int(file_in.readline())
        queries = []
        for _ in range(Q):
            query = file_in.readline().split()
            queries.append((query[0], int(query[1])))

        validare(N, v, Q, queries, file_out)
        answers = solve(N, v, queries)

        for answer in answers:
            file_out.write(str(answer) + '\n')

    except ValueError:
        file_out.write("Datele de intrare nu corespund restrictiilor impuse")
    except IndexError:
        file_out.write("Datele de intrare nu corespund restrictiilor impuse")